Prove that there are infinitely many positive integers which can't be expressed as where and are positive integers.
For positive integer expression denotes the number of positive divisors of .
Solution
If is a square of an integer, any its power is also square of an integer.
If is not a perfect square, number of its positive divisors is even. We can prove this by pairing divisors of as and . A divisor won't be paired with itself because that would imply .
This proves that is even and hence is a perfect square for every positive integer .
The extension in the problem is hence a sum of two squares. Every number of the form 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.