HMMT 二月 2025 · ALGNT 赛 · 第 6 题

HMMT February 2025 — ALGNT Round — Problem 6

Let r be the remainder when 2017 − 1 is divided by 2025!. Compute . (Note that 2017 is 2025! prime.)

解析

Let r be the remainder when 2017 − 1 is divided by 2025!. Compute . (Note that 2017 is 2025! prime.) Proposed by: Srinivas Arun 1311 Answer: 2017 2025! k Solution: Let N = 2017 . Let p be a prime dividing 2025! other than 2017. Let p be the largest k k − 1 k power of p dividing 2025!. Clearly, φ ( p ) = ( p − 1) p divides 2025! and gcd(2017 , p ) = 1, so by Euler’s Totient Theorem, k N ≡ 1 (mod p ) . Repeating for all such primes p , we obtain N ≡ 1 (mod 2025! / 2017) . 2025! 2025! Therefore, | N − 1, so r = s for some 0 ≤ s < 2017. Also, since N ≡ 0 (mod 2017), we have 2017 2017 2025! r = s ≡ − 1 (mod 2017). 2017 By Wilson’s, 2025! = 2016!(2018)(2019) . . . (2025) ≡ − 8! ≡ 20 (mod 2017) . 2017 Therefore, s is negative the inverse of 20 (mod 2017), which is 1311. Our answer is r (2025! / 2017)(1311) 1311 = = . 2025! 2025! 2017