Maths Olympiad Prep

Library / /1 of 27

Number theory Difficulty 5.0 AIME, harder Prove it North Macedonia

Prove that there are infinitely many positive integers which can't be expressed as ad(a)+bd(b)a^{d(a)} + b^{d(b)} where aa and bb are positive integers.
For positive integer aa expression d(a)d(a) denotes the number of positive divisors of aa.

Solution

If aa is a square of an integer, any its power is also square of an integer.
If aa is not a perfect square, number of its positive divisors is even. We can prove this by pairing divisors of aa as dd and ad\frac{a}{d}. A divisor dd won't be paired with itself because that would imply a=d2a = d^2.
This proves that d(a)d(a) is even and hence ad(a)a^{d(a)} is a perfect square for every positive integer aa.
The extension in the problem is hence a sum of two squares. Every number of the form 4t+34t+3 can't be written as a sum of two squares because 0 and 1 are the only quadratic residues modulo 4, so it is impossible for a sum of two squares to give remainder 3 modulo 4.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.