PUMaC 2013 · 数论（B 组） · 第 3 题

PUMaC 2013 — Number Theory (Division B) — Problem 3

[ 4 ] Find the smallest positive integer x such that • x is 1 more than a multiple of 3, • x is 3 more than a multiple of 5, • x is 5 more than a multiple of 7, • x is 9 more than a multiple of 11, and • x is 2 more than a multiple of 13. ( ) n

解析

[ 4 ] Find the smallest positive integer x such that • x is 1 more than a multiple of 3, • x is 3 more than a multiple of 5, 1 • x is 5 more than a multiple of 7, • x is 9 more than a multiple of 11, and • x is 2 more than a multiple of 13. Solution The first four conditions is the same as x ≡ − 2 (mod 1155). By trial, the answer is x = 12703. Alternatively, we have to solve the two equations x ≡ − 2 (mod 1155) and x ≡ 2 (mod 13). Thus we can write x = 1155 y − 2, and substituting this into the second equation, we obtain: 1155 y − 2 ≡ 11 y − 2 ≡ 2 (mod 13) ⇒ − 2 y ≡ 4 (mod 13) ⇒ y ≡ − 2 ≡ 11 (mod 13), so x = 11 · 1155 − 2 = 12703 ( ) n