HMMT 二月 2013 · 团队赛 · 第 9 题

英文解析

9. [ 35 ] Let m be an odd positive integer greater than 1. Let S be the set of all non-negative integersmless than m which are of the form x + y , where xy − 1 is divisible by m . Let f ( m ) be the number ofelements of S .
   Team Roundm
   (a) Prove that f ( mn ) = f ( m ) f ( n ) if m, n are relatively prime odd integers greater than 1.
   (b) Find a closed form for f ( p ), where k > 0 is an integer and p is an odd prime.k
   ∗
   Answer: N/A For a positive integer n , let Z /n Z denote the set of residues modulo n and ( Z /n Z )
   denote the set of residues modulo n that are relatively prime to n . Then, rephrased, S is the set ofm − 1 ∗
   residues modulo m of the form x + x , where x ∈ ( Z /m Z ) .
   − 1 − 1
   For part (a), suppose a = x + x ∈ S and b = y + y ∈ S . By the Chinese Remainderm n
   ∗ − 1
   Theorem, there exists a residue z ∈ ( Z /mn Z ) such that m | ( x − z ) and n | ( y − z ), and thus z + z ≡
   − 1 − 1 − 1
   x + x (mod m ) and z + z ≡ y + y (mod n ). Therefore, all f ( m ) f ( n ) residues modulo mn whichresult from applying the Chinese Remainder Theorem to an element each of S and S are in S .
   m n mn − 1 ∗ − 1
   Conversely, given z + z ∈ ( Z /mn Z ) , taking z + z modulo m and n gives elements of S and S ,
   m nso indeed f ( mn ) = f ( m ) f ( n ).
   k ∗
   We now proceed to part (b). For each x ∈ ( Z /p Z ) , denote q ( x ) to be the largest non-negative integeri 2
   i ≤ k such that p divides x − 1 (this is clearly well-defined). For a given x , let g ( x ) be the numberk ∗ − 1 − 1 kof y ∈ ( Z /p Z ) such that x + x ≡ y + y (mod p ). Note that this condition is equivalent tok
   ( x − y )( xy − 1) ≡ 0 (mod p ).
   ⌈ k/ 2 ⌉
   First, consider the case in which q ( x ) ≥ k/ 2, in which case we have p | ( x − 1)( x + 1), and because
   ⌈ k/ 2 ⌉ 2 k 2 kp is odd, x ≡ ± 1 (mod p ). Thus, either ( x − 1) ≡ 0 (mod p ) or ( x + 1) ≡ 0 (mod p ), and it − 1 k − 1
   follows that x + x ≡ ± 2 (mod p ) (clearly 2 and − 2 are distinct). Conversely, x + x ≡ ± 2 implies
   ⌈ k/ 2 ⌉
   ( x ± 1) ≡ 0 (mod p ), which in turn implies q ( x ) ≥ k/ 2. It is now clear that there are exactly two − 1
   elements of S corresponding to residues of the form x + x with q ( x ) ≥ k/ 2, and all other elementsmof S come from x with q ( x ) < k/ 2.
   Fix x with q ( x ) < k/ 2; we will compute g ( x ). Suppose ( x − y )( xy − 1) ≡ 0 (mod p ), and saykm
   ′ ′ 2 jx − y, xy − 1 have j, j factors of p , respectively. If j ≤ j , note that x − 1 ≡ xy − 1 ≡ 0 (mod p ), so
   ′ ′
   ′ j 2 j ′
   j ≤ q ( x ). Similarly, if j ≤ j , x ≡ y (mod p ), so x − 1 ≡ xy − 1 ≡ 0 (mod p ), and so j ≤ q ( x ). It
   ′ ′
   follows that min( j, j ) ≤ q ( x ), and thus max( j, j ) ≥ k − q ( x ).
   k − q ( x ) 2 q ( x )
   Suppose p | ( x − y ). Then, xy − 1 ≡ x − 1 ≡ 0 (mod p ) because q ( x ) < k/ 2, so any y withk − q ( x ) k k − q ( x ) − 1
   p | ( x − y ) satisfies ( x − y )( xy − 1) ≡ 0 (mod p ). Now, suppose p | ( xy − 1), that is, y ≡ xk − q ( x ) q ( x ) 2 q ( x ) q ( x )
   (mod p ). Then, xy ≡ 1 (mod p ), and since x ≡ 1 (mod p ), we have x ≡ y (mod p ),
   so again we have ( x − y )( xy − 1) ≡ 0 (mod p ). It follows that the set of y satisfying ( x − y )( xy − 1) ≡ 0 kk k − q ( x ) − 1 k − q ( x ) − 1
   (mod p ) is exactly the set of y with y ≡ x (mod p ) or y ≡ x (mod p ). x, x are distinctk − q ( x ) 2 q ( x )
   residues modulo p , because x − 1 has fewer than k/ 2 factors of p , so it follows that g ( x ) = 2 p .
   − 1 − 1
   In particular, note that these values are distinct for different values of q ( x ) < k/ 2, so x + x ≡ y + yimplies q ( x ) = q ( y ) or q ( x ) , q ( y ) ≥ k/ 2.
   For each integer i with 0 ≤ i < k/ 2, we need to compute the number of x ∈ ( Z /p Z ) with q ( x ) = i .ki 2 i +1 2
   Clearly, this is the number of x with p | x − 1 minus the number of x with p | x − 1. When i = 0,
   i 2 k − 1 k − ithe number of x with p | x − 1 is clearly p ( p − 1), and when i > 0, this number is 2 p , as we havex ≡ ± 1 (mod p ).i
   We can now count the number of elements of S k using casework on the value of q ( x ) where we takep − 1
   x to be such that x + x is a particular element of S . Applying the results from the previous twomparagraphs, our answer is
   ⌈ k/ 2 ⌉− 1
   k − 1 k − i k − i − 1
   ∑
   p ( p − 3) 2 p − 2 p
   2 + + ,
   2 2 pii =1
   where the summand 2 comes from ± 2 ∈ S k , corresponding to all x with q ( x ) > k/ 2, the next summandpcomes from those x with q ( x ) = 0, and each additional summand comes from those x with q ( x ) = i inthe relevant range. We may evaluate the last sum as a geometric series, to obtain the final closed formanswer ofk
   1+( − 1)
   k − 1 k − 1
   p ( p − 3) p − p 2
   2 + + .
   2 p + 1
   Team Round