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

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

Let p be a prime number greater than 5. Prove that there exists a positive integer n such that n n n p divides 20 + 15 − 12 . 1 1 1 3

解析

Let p be a prime number greater than 5. Prove that there exists a positive integer n such that n n n p divides 20 + 15 − 12 . Solution: 1 1 1 I claim that n = p − 3 works. Using the cool “Pythagorean triple” + = , we 2 2 2 20 15 12 p − 1 p − 1 p − 1 p − 1 p − 1 p − 1 20 15 12 20 − 1 15 − 1 12 − 1 p − 3 p − 3 p − 3 have 20 + 15 − 12 = + − = + − = 2 2 2 2 2 2 20 15 12 20 15 12 p − 1 p − 1 p − 1 9(20 − 1)+16(15 − 1) − 25(12 − 1) . 3600 Since we know that this fraction is an integer, to show that it is divisible by p it suffices to check that the numerator is divisible by p and the denominator is not. Since p > 5, p is relatively prime to 12, 15, and 20, so by Fermat’s little theorem we see that p divides the numerator. 4 2 2 Also since p > 5 and 3600 = 2 · 3 · 5 , we see that p does not divide the denominator. We p − 3 p − 3 p − 3 conclude that p divides 20 + 15 − 12 . n n n The intuition for this solution is quite simple: since f ( n ) = 20 + 15 − 12 equals 0 for n = − 2 and f ( n ) mod p is periodic with some period dividing p − 1 for n ≥ 0 (by Fermat’s little theorem), we ought to have f ( − 2 + ( p − 1)) ≡ 0 (mod p ). 1 1 1 3