PUMaC 2012 · 个人决赛（B 组） · 第 1 题

PUMaC 2012 — Individual Finals (Division B) — Problem 1

Let q be a fixed odd prime. A prime p is said to be orange if for every integer a there exists q an integer r such that r ≡ a (mod p ). Prove that there are infinitely many orange primes.

解析

Let q be a fixed odd prime. A prime p is said to be orange if for every integer a there exists q an integer r such that r ≡ a (mod p ). Prove that there are infinitely many orange primes. Solution: We claim that a prime p is orange whenever p 6 ≡ 1 (mod q ). Indeed, for such p , we know that ( p − 1 , q ) = 1, so there exist m, n ∈ Z such that ( p − 1) m + qn = 1. Thus, for every integer ( ) m q q ( p − 1) m + qn p − 1 n n a 6 ≡ 0 (mod p ), we have a = a = a · ( a ) ≡ ( a ) (mod p ) (where the last n step follows by Fermat’s little theorem), so r = a works. For a ≡ 0 (mod p ), we may take r = 0. It remains to show that there are infinitely many primes p 6 ≡ 1 (mod q ). Assume on the contrary that there are only finitely many such primes, and let these primes be p , p , . . . , p . 1 2 k Let N = qp p · · · p − 1. Then N is not divisible by any p , so all prime factors of N must be 1 2 k j congruent to 1 (mod q ), contradicting the fact that N ≡ − 1 (mod q ).