PUMaC 2015 · 数论（B 组） · 第 5 题

PUMaC 2015 — Number Theory (Division B) — Problem 5

[ 5 ] Given that there are 24 primes between 3 and 100, inclusive, what is the number of ordered p − 2 pairs ( p, a ) with p prime, 3 ≤ p < 100, and 1 ≤ a < p such that p | ( a − a )?

解析

[ 5 ] Given that there are 24 primes between 3 and 100, inclusive, what is the number of ordered p − 2 pairs ( p, a ) with p prime, 3 ≤ p < 100, and 1 ≤ a < p such that p | ( a − a )? Solution: p − 1 p − 2 − 1 By Fermat’s Little Theorem, a ≡ 1 (mod p ). This means that a ≡ a (mod p ), so p − 2 − 1 2 0 ≡ a − a ≡ a − a (mod p ) = ⇒ a ≡ 1 (mod p ) . Clearly the only solutions are a = 1 , p − 1, so for each prime p there are exactly two solutions of the form ( p, a ). Hence there are 48 solutions total. Author: Steven Kwon