HMMT 二月 2016 · 代数 · 第 8 题

英文解析

8. Define φ ( n ) as the product of all positive integers less than or equal to n and relatively prime to n .
   !
   Compute the number of integers 2 ≤ n ≤ 50 such that n divides φ ( n ) + 1.
   Proposed by: Alexander Katz
   Answer: 30 − 1 − 1
   Note that, if k is relatively prime to n , there exists a unique 0 < k < n such that kk ≡ 1 (mod n ).
   Hence, if k 6 ≡ 1 (mod n ), we can pair k with its inverse to get a product of 1.2
   2 2 2
   If k ≡ 1 (mod n ), then ( n − k ) ≡ 1 (mod n ) as well, and k ( n − k ) ≡ − k ≡ − 1 (mod n ). Hencethese k can be paired up as well, giving products of -1. When n 6 = 2, there is no k such that k ≡ 12
   2 m
   (mod n ) and k ≡ n − k (mod n ), so the total product (mod n ) is ( − 1) , where m is the number ofk such that k ≡ 1 (mod n ).2
   2 i
   For prime p and positive integer i , the number of solutions to k ≡ 1 (mod p ) is 2 if p is odd, 4 ifp = 2 and i ≥ 3, and 2 if p = i = 2. So, by Chinese remainder theorem, if we want the product to bek k − 1, we need n = p , 2 p , or 4. We can also manually check the n = 2 case to work.
   Counting the number of integers in the allowed range that are of one of these forms (or, easier, doingcomplementary counting), we get an answer of 30.
   (Note that this complicated argument basically reduces to wanting a primitive root.)