PUMaC 2012 · 数论（A 组） · 第 8 题
PUMaC 2012 — Number Theory (Division A) — Problem 8
题目详情
- [ 8 ] Find the largest possible sum m + n for positive integers m, n ≤ 100 such that m + 1 ≡ n 2 − 1 m − 1 n a 3 (mod 4) and there exists a prime number p and nonnegative integer a such = m + p . m − 1 1
解析
- [ 8 ] Find the largest possible sum m + n for positive integers m, n ≤ 100 such that m + 1 ≡ n 2 − 1 m − 1 n a 3 (mod 4) and there exists a prime number p and nonnegative integer a such = m + p . m − 1 Solution: We consider two cases: n = 2 and n > 2. When n = 2, then n 2 − 1 m − 1 2 = m + m + 1 . m − 1 Let p = m + 1 , a = 1 , and we are done. k + For n ≥ 3, let n + 1 = 2 q , with k ∈ N and q ∈ Z and 2 6 | q . Because n ( n − 1) n n 2 = (1 + 1) ≥ 1 + n + > n + 1 , 2 we have 0 ≤ k ≤ n − 1. But n n − 1 2 ∏ t m − 1 2 = ( m + 1) , m − 1 t =0 so we have n 2 k m − 1 2 m + 1 | , m − 1 k k 2 n +1 2 q m + 1 | m + 1(= ( m ) + 1) . n 2 − 1 m − 1 n Let d = − m . Then we get n m − 1 4 n n 2 2 m − m m − 1 n +1 n +1 md = − m = − ( m + 1) . n m − 1 m − 1 k k k 2 2 a 2 Therefore m + 1 | md , and from this we have m + 1 | d . If d = p , then p | m + 1, n n n and from 2 | m and thus 2 6 | p . Because p − 1 m ≡ 1 (mod p ) , k +1 2 2 m ≡ ( − 1) ≡ 1 (mod p ) , we have k +1 ( p − 1 , 1 ) m ≡ 1 (mod p ) , but k 2 m ≡ − 1 6 ≡ 1 (mod p ) , k +1 k +1 therefore ( p − 1 , 2 ) = 2 , so we have k +1 p ≡ 1 (mod 2 ) . (1) Note that n n 2 − 2 2 − 1 ∑ m − 1 a n t n 2 3 p = − m = m − m ≡ 1 + m + m (mod m ) . (2) m − 1 t =0 If k > 0, then from (1) we know that p ≡ 1 (mod 4), thus a p ≡ 1 6 ≡ 1 + m (mod 4) , k 2 which is contrary to (2). Therefore, k = 0. From p | m + 1, we have p | m + 1, and because a a m + 1 is a prime number, we have p = m + 1, so p ≡ 1 (mod 8) or p = m + 1 (mod 8), but 2 1 + m + m 6 ≡ 1 , m + 1 (mod 8), which contradicts (2). Therefore, there are no solutions for n ≥ 3, so the only m, n satisfying the conditions are: n = 2 , m = q − 1 , where q is any prime number such that q ≡ 3 (mod 4). All that is left is to determine the largest prime number less than 100 that has a residue of 3 modulo 4. This number is 83, so m = 82 and m + n = 84 . Problem based on China 2010. 5