HMMT 十一月 2021 · THM 赛 · 第 6 题

HMMT November 2021 — THM Round — Problem 6

Let n be the answer to this problem. a and b are positive integers satisfying 3 a + 5 b ≡ 19 (mod n + 1) 4 a + 2 b ≡ 25 (mod n + 1) Find 2 a + 6 b .

解析

Let n be the answer to this problem. a and b are positive integers satisfying 3 a + 5 b ≡ 19 (mod n + 1) 4 a + 2 b ≡ 25 (mod n + 1) Find 2 a + 6 b . Proposed by: David Vulakh Answer: 96 Solution: Let m = n + 1, so that the conditions become 3 a + 5 b ≡ 19 (mod m ) (1) 4 a + 2 b ≡ 25 (mod m ) (2) 2 a + 6 b ≡ − 1 (mod m ) (3) We can subtract (2) from twice (3) to obtain 10 b ≡ − 27 (mod m ) Multiplying (1) by 2 and replacing 10 b with − 27 gives 6 a − 27 ≡ 38 (mod m ) So 6 a ≡ 65 (mod m ). Multiplying (3) by 30 and replacing 10 b with − 27 and 6 a with 64 gives 650 − 486 ≡ − 30 (mod m ) Therefore 194 ≡ 0 (mod m ), so m | 194. Since the prime factorization of m is 194 = 97 · 2, m must be 1, 2, 97, or 194. Condition (3) guarantees that m is odd, and a, b > 0 guarantees that m = 2 a +6 b +1 6 = 1. So we must have m = 97, so n = 96. A valid solution is a = 27, b = 7.