PUMaC 2020 · 个人决赛（B 组） · 第 2 题

PUMaC 2020 — Individual Finals (Division B) — Problem 2

Prove that there is a positive integer M for which the following statement holds: √ √ n For all prime numbers p , there is an integer n for which p ≤ n ≤ M p and p mod n ≤ . 2020 Note: Here, p mod n denotes the unique integer r ∈ { 0 , 1 , . . . , n − 1 } for which n | p − r . In other words, p mod n is the residue of p upon division by n .

解析

Prove that there is a positive integer M for which the following statement holds: √ √ n For all prime numbers p , there is an integer n for which p ≤ n ≤ M p and p mod n ≤ . 2020 Note: Here, p mod n denotes the unique integer r ∈ { 0 , 1 , . . . , n − 1 } for which n | p − r . In other words, p mod n is the residue of p upon division by n . 2 Solution : We will show that any M > 4040 satisfies the conditions of the problem. 2 First, we will consider primes with p > 4040 . We will show that any M > 4040 works here. √ √ √ √ p p p p Because ≥ 2, there is an integer q in the interval [ , ]. As q is at most , it 2020 4040 2020 2020 √ p divides an integer s in the interval [ p − , p − 1], as the length of this interval is bigger than q . 2020 √ p √ √ √ √ p − p s 1 2020 √ Pick n = . Then, n ≥ = 2020( p − ) ≥ p . Similarly, n ≤ ≤ 4040 p < M p . p q 2020 q 2020 √ p n Finally, p mod n ≤ p − s ≤ ≤ . 2020 2020 2 Now, having proven that any M > 4040 works in case p ≥ 4040 , we can consider the primes 2 2 p ≤ 4040 as well. For them, it suffices to choose M > 4040 as well, because one can just √ pick n = p , and it will satisfy the conditions of the problem: p mod n = 0, n = p ≥ p and √ √ √ √ n = p p ≤ 4040 p ≤ M p . 2 Therefore, any integer M > 4040 satisfies the conditions of this problem. 1 Proposed by Aleksa Milojevi´ c.