PUMaC 2019 · 数论（A 组） · 第 6 题

PUMaC 2019 — Number Theory (Division A) — Problem 6

Let p, q ≤ 200 be prime numbers such that is a square. Find the sum of p + q over all p such pairs.

解析

Let p, q ≤ 200 be prime numbers such that is a square. Find the sum of p + q over all p such pairs. Proposed by: Marko Medvedev Answer: 24 p We have that p | q − 1, hence p | q − 1 by Fermat’s small theorem. Now suppose that p is odd. p q − 1 p Then we have that v ( q − 1) = v ( q − 1) + 1, so we have that p || and furthermore that p p q − 1 p q − 1 q − 1 and are coprime, and hence squares. Then q − 1 is square, and is divisible by p so p ( q − 1) 2 it’s q = ( pm ) + 1 for some integer m . Furthermore since p is odd, q > 2 hence also odd. Then 2 q is of the form q = (2 pm ) +1 for some integer m . Now since we have q ≤ 200 we can check all 2 cases directly (there’s three of them), and get that there are no solutions here. Now suppose 2 2 1 2 that p = 2. Hence q = 2 x + 1. Since ( q − 1)( q + 1) = x , and ( q − 1 , q + 1) = 2, we know 2 that x is even. If x is divisible by 4 then q ≡ 1 (mod 16), so q ≡ 1 (mod 8). Furthermore by looking at modulo 32 it’s clear that q ≡ 1 (mod 16). This eases the search a lot and the only answer here is q = 17 and we can check that his indeed works. Now if x ≡ 2 (mod 4), 2 then q ≡ 3 (mod 4), since the only odd integers dividing x + 1 are of the form 4 k + 1. Then looking at (mod 16) gives q ≡ 3 (mod 16). Again the search is greatly reduced and we get that the only solution is q = 3. In total the solutions are ( p, q ) = (2 , 3) , (2 , 17).