PUMaC 2014 · 加试 · 第 1 题

PUMaC 2014 — Power Round — Problem 1

a are all distinct modulo p , so up to a permutation, the sets { a, 2 a, · · · , ( p −
a } and { 1 , 2 , · · · , p − 1 } are congruent. This means that their products are congruent modulo p , that is, p − 1 ( p − 1)! a ≡ ( p − 1)! (mod p ) . Cancelling (p-1)! from both sides (this is possible because ( p − 1)! is coprime to p − 1 p ), we have the desired equality a ≡ 1 (mod p ) immediately. 2 An important question throughout the process of this Power Round would 2 be whether the congruence x ≡ a (mod p ) has a solution x ∈ Z given an integer a and a prime p . The following concept will be extremely helpful. Definition 3 (Quadratic residue) . Let a and m be integers such that m > 0. 2 We say that a is a quadratic residue mod m if the congruence x ≡ a (mod m ) has a solution. Otherwise we say that a is a quadratic nonresidue . Remark. 0 , 1 , 4 are quadratic residues modulo 5. 0 , 1 , 2 , 4 are quadratic residues modulo 7. 0 , 1 , 4 are quadratic residues modulo 8. The following notation will be useful. Definition 4. Let p be an odd prime and let a be an integer not divisible by p . The Legendre symbol of a with respect to p is defined by { ( ) a 1 if a quadratic residue modulo p = p − 1 otherwise Remark. The Legendre symbol satisfies the following properties. p − 1

解析

暂无解答链接。

No solutions link available.