PUMaC 2019 · 数论（A 组） · 第 8 题
PUMaC 2019 — Number Theory (Division A) — Problem 8
题目详情
- The integer 107 is a prime number. Let p = 107. For an integer a such that p - a let a be the − 1 2 2 − 1 unique integer 0 ≤ a ≤ p − 1 such that p | aa − 1. Find the number of positive integers 2 p − 1 2 2 2 − 1 b , 1 ≤ b ≤ such that there exists an integer a , 0 ≤ a ≤ p − 1 such that p | b − ( a + a ). 2 1
解析
- The number 107 is a prime number. Let p = 107. For a number a such that p - a let a be the − 1 2 2 − 1 unique number 0 ≤ a ≤ p − 1 such that p | aa − 1. Find the number of positive integers 2 p − 1 2 2 2 − 1 b , 1 ≤ b ≤ such that there exists a number a , 0 ≤ a ≤ p − 1 such that p | b − ( a + a ). 2 Proposed by: Igor Medvedev 2 p − 3 p +4 Answer: 2783 ( ) 4 2 Solutions : We work in (mod p ). First note that for 4 | p − 3, − 1 is not a quadratic residue mod 2 2 p . Then note that for p - x , x is a quadratic residue (mod p ) iff − x is not a quadratic residue 3 2 − 1 2 (mod p ). Now we will count the number of values that a + a takes in { 0 , 1 , 2 , . . . , p − 1 } takes 2 − 1 − 1 as a ranges over 0 , 1 , . . . , p − 1. Suppose that for numbers x, y we have that x + x = y + y . 2 This is equivalent to p | ( xy − 1)( x − y ). For x = kp + 1 the value is 2. Similarly for y = kp − 1, the value is − 2, and exactly one of these two is a quadratic residue. For x 6 = ± 1 (mod p ), there − 1 − 1 − 1 exists exactly one y = x , y 6 = x such that x + x = y + y , since we have to have either 2 2 − 1 − 1 p | xy − 1 or p | x − y . Now for x 6 = ± 1 (mod 1), we have that x + x = − ( − x + ( − x ) ), 2 so exactly one of these is a quadratic residue. Then for each of the p − 3 p problems which − 1 − 1 − 1 don’t give − 1 , 0 , 1 (mod p ) we pair up x + x with the corresponding y + y and x + x 2 p − 3 p − 1 with − ( − x + ( − x ) ). Exactly one of these values is counted, so this adds . To this we 4 2 p − 3 p +4 add one for 2 or − 2. The total number is . 4 4