HMMT 二月 2016 · 代数 · 第 8 题

HMMT February 2016 — Algebra — Problem 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.

解析

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 ). 2 Hence, if k 6 ≡ 1 (mod n ), we can pair k with its inverse to get a product of 1. 2 2 2 If k ≡ 1 (mod n ), then ( n − k ) ≡ 1 (mod n ) as well, and k ( n − k ) ≡ − k ≡ − 1 (mod n ). Hence 2 these k can be paired up as well, giving products of -1. When n 6 = 2, there is no k such that k ≡ 1 m 2 (mod n ) and k ≡ n − k (mod n ), so the total product (mod n ) is ( − 1) , where m is the number of 2 k such that k ≡ 1 (mod n ). 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 if p = 2 and i ≥ 3, and 2 if p = i = 2. So, by Chinese remainder theorem, if we want the product to be k 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, doing complementary counting), we get an answer of 30. (Note that this complicated argument basically reduces to wanting a primitive root.)