Maths Olympiad Prep

Library / /781 of 1394

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
Let rr be the remainder when 20172025!12017^{2025!} - 1 is divided by 2025!2025!. Compute r2025!\frac{r}{2025!}. (Note that 20172017 is prime.)

Solution

Solution:
Let N=20172025!N = 2017^{2025!}. Let pp be a prime dividing 2025!2025! other than 20172017. Let pkp^{k} be the largest power of pp dividing 2025!2025!. Clearly, ϕ(pk)=(p1)pk1\phi (p^{k}) = (p - 1)p^{k - 1} divides 2025!2025! and gcd(2017,pk)=1\gcd (2017, p^{k}) = 1, so by Euler's Totient Theorem,
N1(modpk). N \equiv 1 \pmod{p^{k}}.
Repeating for all such primes pp, we obtain
N1(mod2025!/2017). N \equiv 1 \pmod{2025! / 2017}.
Therefore, 2025!2017N1\frac{2025!}{2017} \mid N - 1, so r=2025!2017sr = \frac{2025!}{2017} s for some 0s<20170 \leq s < 2017. Also, since N0N \equiv 0 (mod 20172017), we have r=2025!2017s1r = \frac{2025!}{2017} s \equiv -1 (mod 20172017).
By Wilson's,
2025!2017=2016!(2018)(2019)(2025)8!20(mod2017). \frac{2025!}{2017} = 2016! (2018)(2019)\ldots (2025) \equiv -8! \equiv 20 \pmod{2017}.
Therefore, ss is negative the inverse of 2020 (mod 20172017), which is 13111311. Our answer is
r2025!=(2025!/2017)(1311)2025!=13112017. \frac{r}{2025!} = \frac{(2025! / 2017)(1311)}{2025!} = \frac{1311}{2017}.

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.