HMMT 十一月 2013 · 冲刺赛 · 第 19 题

HMMT November 2013 — Guts Round — Problem 19

[ 11 ] Let p, q, r, s be distinct primes such that pq − rs is divisible by 30. Find the minimum possible value of p + q + r + s .

解析

[ 11 ] Let p, q, r, s be distinct primes such that pq − rs is divisible by 30. Find the minimum possible value of p + q + r + s . Answer: 54 The key is to realize none of the primes can be 2, 3, or 5, or else we would have to use one of them twice. Hence p, q, r, s must lie among 7 , 11 , 13 , 17 , 19 , 23 , 29 , . . . . These options give remainders of 1 (mod 2) (obviously), 1 , − 1 , 1 , − 1 , 1 , − 1 , − 1 , . . . modulo 3, and 2 , 1 , 3 , 2 , 4 , 3 , 4 , . . . 2 modulo 5. We automatically have 2 | pq − rs , and we have 3 | pq − rs if and only if pqrs ≡ ( pq ) ≡ 1 (mod 3), i.e. there are an even number of − 1 (mod 3)’s among p, q, r, s . 2 If { p, q, r, s } = { 7 , 11 , 13 , 17 } , then we cannot have 5 | pq − rs , or else 12 ≡ pqrs ≡ ( pq ) (mod 5) is a quadratic residue. Our next smallest choice (in terms of p + q + r + s ) is { 7 , 11 , 17 , 19 } , which works: 2 7 · 17 − 11 · 19 ≡ 2 − 4 ≡ 0 (mod 5). This gives an answer of 7 + 17 + 11 + 19 = 54.