PUMaC 2011 · 数论（A 组） · 第 6 题
PUMaC 2011 — Number Theory (Division A) — Problem 6
题目详情
- [ 6 ] Let a and b be positive integers such that a + bz = x + y has no solutions for any integers x, y, z , with b as small as possible, and a as small as possible for the minimum b . Find ab . ∞
解析
- In order to decrease the number of remainders (mod b ) that can be written in the form x + y , we should minimize the number of cubes and fourth powers (mod b ). This happens when b is prime and when 3 , 4 | b − 1, which happens when b = 13. Indeed, for this value of b , the cubic residues are 0 , 1 , 5 , 8 and 12 and the quartic residues are 0 , 1 , 3, and 9. 7 cannot be written as the sum of any cubic-quartic residue pair, so (7 , 13) satisfies the problem’s constraints. Now, I will show that for any b < 13, all residues (mod b ) can be written as a sum of a cubic- quartic residue pair. We can reduce the checking to just prime values of b and powers of primes by the Chinese Remainder Theorem. Therefore, we just need to check b = 1 , 2 , 3 , 4 , 5 , 7 , 8 , 9 , 11. 4 1, 2, and 3 are trivial to check, so just look at 4, 5, 7, 8, 9, 11. For 5, note that x ≡ 1 for 3 − 1 3 nonzero x , so x ≡ x . Everything is invertible (mod 5) (except 0), so x takes on all values 9 − 1 (mod 5). Very similar logic applies for 11, as x ≡ x (mod 11) for all nonzero x , which means that 9th powers take on all values (mod 11) (and therefore implies that the cubes take 4 − 2 4 on all values (mod 11)). For 7, note that x = x (mod 7) for all nonzero x . This means x takes on the values of all squares (which are 0,1,2,4). The cubes equivalent to 1 , 0 , − 1 (mod 7), so just a little bit of checking shows that all residues modulo 7 are covered. 4 Now, we just have to check b = 4 , 8 , 9. 4 is easy to check. By Euler’s Theorem, x ≡ 1 (mod 8) 3 − 1 for all odd residues (mod 8), so x ≡ x and the cubes cover all odd residues mod 8. Since the quartic residues are 0 and 1, we cover everything. Finally, we just need to check b = 9. 4 − 2 For all invertible elements x , x ≡ x , so we cover all squares. The squares (mod 9) are 0, 1, 4, 7. The cubes contain 0, 1, and − 1 so we hit everything. Therefore, (7 , 13) is the solution with smallest b . Thus the answer is 7 · 13 = 91 .