PUMaC 2017 · 数论（A 组） · 第 5 题

PUMaC 2017 — Number Theory (Division A) — Problem 5

Let p ( n ) = n − 6 n − 160. If a is the least odd prime dividing q ( n ) = | p ( n − 30) · p ( n + 30) | , n 2017 ∑ find a . ( a = 3 if q ( n ) = 0.) n n n =1 n

解析

Let x = n − 30; then, we are looking at odd prime factors of p ( x ) p ( x + 60). 2 First we look at p ( x ) (mod 3). We find p ( x ) ≡ x − 1 ≡ 0 ⇐⇒ x 6 ≡ 0 (mod 3). 4 2 Say now that x ≡ 0 (mod 3), i.e. x = 3 y . p ( x ) = p (3 y ) ≡ y + y (mod 5). y ≡ 0 is clearly 4 2 a solution; say temporarily that y 6 ≡ 0, so y ≡ 1; then for 5 | p ( x ), y ≡ − 1 (mod 5), or y ≡ 2 , 3. It takes a little more work to show that when y ≡ ± 1 (mod 5), 7 | p ( x ) p ( x + 60), as it is not always the case that 7 | p ( x ) (as it was with 3 and 5). (In fact, we will show a stronger result 2 2 2 2 – that 7 always divides the product.) Factor: p ( x ) = ( x − 16)( x + 10) ≡ ( x − 2)( x − 4) 2 2 (mod 7), and so p ( x + 60) ≡ (( x + 4) − 2)(( x + 4) − 4). Now, consider the quadratic residues 1 2 2 x x x + 4 ( x + 4) 0 0 4 2 1 1 5 4 2 4 6 1 modulo 7: Note how each line has either a 2 or a 4 in the squared 3 2 0 0 4 2 1 1 5 4 2 4 6 1 3 2 column; this means that 7 always divides the product p ( x ) p ( x + 60) for any integer x . n Thus, we have n ≡ 1 , 2 (mod 3) = ⇒ a = 3; ≡ 0 , ± 2 (mod 5) = ⇒ a = 5; else a = 7. n n n 5 Summing gives 7933 . Problem written by Zack Stier