HMMT 二月 2013 · 团队赛 · 第 9 题
HMMT February 2013 — Team Round — Problem 9
题目详情
- [ 35 ] Let m be an odd positive integer greater than 1. Let S be the set of all non-negative integers m less than m which are of the form x + y , where xy 1 is divisible by m . Let f ( m ) be the number of elements of S . m (a) Prove that f ( mn ) = f ( m ) f ( n ) if m, n are relatively prime odd integers greater than 1. k (b) Find a closed form for f ( p ), where k > 0 is an integer and p is an odd prime.
解析
- [ 35 ] Let m be an odd positive integer greater than 1. Let S be the set of all non-negative integers m less than m which are of the form x + y , where xy − 1 is divisible by m . Let f ( m ) be the number of elements of S . m Team Round (a) Prove that f ( mn ) = f ( m ) f ( n ) if m, n are relatively prime odd integers greater than 1. k (b) Find a closed form for f ( p ), where k > 0 is an integer and p is an odd prime. ∗ 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 of m − 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 Remainder m 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 which result 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 n so 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 integer i 2 i ≤ k such that p divides x − 1 (this is clearly well-defined). For a given x , let g ( x ) be the number k ∗ − 1 − 1 k of y ∈ ( Z /p Z ) such that x + x ≡ y + y (mod p ). Note that this condition is equivalent to k ( 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 k p 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 elements m of S come from x with q ( x ) < k/ 2. m k Fix x with q ( x ) < k/ 2; we will compute g ( x ). Suppose ( x − y )( xy − 1) ≡ 0 (mod p ), and say ′ ′ 2 j x − 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 with k − 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 ≡ x k − 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 ), k so again we have ( x − y )( xy − 1) ≡ 0 (mod p ). It follows that the set of y satisfying ( x − y )( xy − 1) ≡ 0 k 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 distinct k − 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 + y implies q ( x ) = q ( y ) or q ( x ) , q ( y ) ≥ k/ 2. k For each integer i with 0 ≤ i < k/ 2, we need to compute the number of x ∈ ( Z /p Z ) with q ( x ) = i . i 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 − i the number of x with p | x − 1 is clearly p ( p − 1), and when i > 0, this number is 2 p , as we have i x ≡ ± 1 (mod p ). We can now count the number of elements of S k using casework on the value of q ( x ) where we take p − 1 x to be such that x + x is a particular element of S . Applying the results from the previous two m paragraphs, our answer is ⌈ k/ 2 ⌉− 1 k − 1 k − i k − i − 1 ∑ p ( p − 3) 2 p − 2 p 2 + + , i 2 2 p i =1 where the summand 2 comes from ± 2 ∈ S k , corresponding to all x with q ( x ) > k/ 2, the next summand p comes from those x with q ( x ) = 0, and each additional summand comes from those x with q ( x ) = i in the relevant range. We may evaluate the last sum as a geometric series, to obtain the final closed form answer of k 1+( − 1) k − 1 k − 1 2 p ( p − 3) p − p 2 + + . 2 p + 1 Team Round