Maths Olympiad Prep

Library / /17 of 94

Number theory Difficulty 5.2 AIME, harder Prove it Hong Kong

Show that there exist infinitely many squarefree positive integers nn that divide 2005n12005^n - 1. (An integer is squarefree if it contains no factors of the form d2d^2, d>1d > 1.)

Solution

Firstly, note that 20051(mod3)2005 \equiv 1 \pmod{3}. Therefore, 3200513 \mid 2005 - 1. Suppose we have chosen distinct primes p1,p2,,pkp_1, p_2, \dots, p_k such that p1p2pk2005p1p2pk11p_1 p_2 \cdots p_k \mid 2005^{p_1 p_2 \cdots p_{k-1}} - 1, where the exponent of 20052005 is 11 when k=1k=1. Then
2005p1p2pk=(2005p1p2pk1)pk1pk=1(modp1p2pk). 2005^{p_1 p_2 \cdots p_k} = (2005^{p_1 p_2 \cdots p_{k-1}})^{p_k} \equiv 1^{p_k} = 1 \pmod{p_1 p_2 \cdots p_k}.
This shows n=p1p2pkn = p_1 p_2 \cdots p_k satisfies the requirement.
By Zsigmondy's theorem, there exists a prime pkp_k dividing 2005p1p2pk12005^{p_1 p_2 \cdots p_k} - 1 but not 2005p1p2pk112005^{p_1 p_2 \cdots p_{k-1}} - 1. This shows pkp_k is different from p1,p2,,pk1p_1, p_2, \dots, p_{k-1}. Therefore, we have
p1p2pk+12005p1p2pk1. p_1 p_2 \cdots p_{k+1} \mid 2005^{p_1 p_2 \cdots p_k} - 1.

By induction, we can find an infinite sequence of distinct primes pjp_j such that n=p1p2pkn = p_1 p_2 \cdots p_k satisfies the requirement for any kZ+k \in \mathbb{Z}^+. So we are done.

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.