Maths Olympiad Prep

Library / China Hong Kong Mathematical Olympiad /17 of 89

China Hong Kong Mathematical Olympiad

Number theory Difficulty 5.2 AIME, harder Prove it Hong Kong

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

Solution

Firstly, note that 2005≡1(mod3)2005 \equiv 1 \pmod{3}. Therefore, 3∣2005−13 \mid 2005 - 1. Suppose we have chosen distinct primes p1,p2,…,pkp_1, p_2, \dots, p_k such that p1p2⋯pk∣2005p1p2⋯pk−1−1p_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
2005p1p2⋯pk=(2005p1p2⋯pk−1)pk≡1pk=1(modp1p2⋯pk). 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=p1p2⋯pkn = p_1 p_2 \cdots p_k satisfies the requirement.
By Zsigmondy's theorem, there exists a prime pkp_k dividing 2005p1p2⋯pk−12005^{p_1 p_2 \cdots p_k} - 1 but not 2005p1p2⋯pk−1−12005^{p_1 p_2 \cdots p_{k-1}} - 1. This shows pkp_k is different from p1,p2,…,pk−1p_1, p_2, \dots, p_{k-1}. Therefore, we have
p1p2⋯pk+1∣2005p1p2⋯pk−1. 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=p1p2⋯pkn = p_1 p_2 \cdots p_k satisfies the requirement for any k∈Z+k \in \mathbb{Z}^+. So we are done.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.