Maths Olympiad Prep

Library / /36 of 61

Number theory Difficulty 6.4 National olympiad Prove it Belarus

A positive integer is called nice if it is equal to the sum of the squares of its three distinct divisors. (A divisor may be equal to 11 or to the number itself.)

a) Prove that any nice number is divisible by 33.

b) Are there infinitely many nice numbers?

Solution

a) Let NN be a nice number, i.e. N=d12+d22+d32N = d_1^2 + d_2^2 + d_3^2, where d1,d2,d3d_1, d_2, d_3 are distinct divisors of NN. If some divisor of NN is divisible by 33, then NN is divisible by 33.

So we suppose that d1,d2,d3d_1, d_2, d_3 are not divisible by 33. Then their squares are congruent to 11 modulo 33, i.e. d12=3k1+1d_1^2 = 3k_1 + 1, k1Nk_1 \in \mathbb{N}, i=1,2,3i = 1, 2, 3. Therefore
N=d12+d22+d32=3(k1+k2+k3)+3, N = d_1^2 + d_2^2 + d_3^2 = 3(k_1 + k_2 + k_3) + 3,
and so NN is divisible by 33.

b) There exists a nice number NN'. For example, if N=30N = 30 and its divisors are d1=1d_1 = 1, d2=2d_2 = 2, d3=5d_3 = 5, then
d12+d22+d32=12+22+52=1+4+25=30=N, d_1^2 + d_2^2 + d_3^2 = 1^2 + 2^2 + 5^2 = 1 + 4 + 25 = 30 = N,
i.e. NN is nice.

Consider N(p)=Np2N(p) = Np^2, where pp is some positive integer and p>1p > 1. If d1,d2,d3d_1, d_2, d_3 are distinct divisors of NN, then it is obvious that d1p,d2p,d3pd_1p, d_2p, d_3p are distinct divisors of N(p)N(p), and
N(p)=Np2=[N=d12+d22+d32]=(d12+d22+d32)p2=(d1p)2+(d2p)2+(d3p)2. N(p) = Np^2 = [N = d_1^2 + d_2^2 + d_3^2] = (d_1^2 + d_2^2 + d_3^2)p^2 = (d_1p)^2 + (d_2p)^2 + (d_3p)^2.
From this equality it follows that N(p)N(p) is nice too. Since any positive integer can be used as pp, there are infinitely many nice numbers N(p)N(p).

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.