Maths Olympiad Prep

Library / /39 of 74

, 2016

Number theory Difficulty 5.6 AIME, harder Prove it Slovenia

Let
N=2152015. N = 2^{15} \cdot 2015.
How many divisors of N2N^2 are strictly smaller than NN and do not divide NN?

Solution

A number with prime factorization p1α1p2α2pkαkp_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} has
τ(p1α1p2α2pkαk)=(α1+1)(α2+1)(αk+1) \tau(p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}) = (\alpha_1 + 1)(\alpha_2 + 1) \dots (\alpha_k + 1)
divisors. The number NN can be factored as N=21551331N = 2^{15} \cdot 5 \cdot 13 \cdot 31, so
τ(N)=(15+1)(1+1)(1+1)(1+1)=27=128 \tau(N) = (15 + 1) \cdot (1 + 1) \cdot (1 + 1) \cdot (1 + 1) = 2^7 = 128
and τ(N2)=(215+1)(21+1)(21+1)(21+1)=3133=837. \text{and } \tau(N^2) = (2 \cdot 15 + 1) \cdot (2 \cdot 1 + 1) \cdot (2 \cdot 1 + 1) \cdot (2 \cdot 1 + 1) = 31 \cdot 3^3 = 837.
If dd divides N2N^2 then N2d\frac{N^2}{d} also divides N2N^2, so all divisors can be sorted into pairs (d,N2d)(d, \frac{N^2}{d}), omitting the number NN, which would otherwise be paired with itself. In each pair exactly one divisor is smaller than NN and one is greater than NN. This implies that the number of divisors of N2N^2 which are strictly smaller than NN is equal to the number of pairs, which is
τ(N2)12. \frac{\tau(N^2) - 1}{2}.

Each divisor of NN also divides N2N^2, so we have to subtract the number of divisors of NN smaller than NN. The number of divisors of N2N^2 which are smaller than NN and do not divide NN is therefore equal to
τ(N2)12(τ(N)1)=8362127=291. \frac{\tau(N^2) - 1}{2} - (\tau(N) - 1) = \frac{836}{2} - 127 = 291.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.