PUMaC 2015 · 数论（B 组） · 第 7 题
PUMaC 2015 — Number Theory (Division B) — Problem 7
题目详情
- [ 7 ] What is the smallest positive integer n such that 20 ≡ n (mod 29)?
解析
- [ 7 ] What is the smallest positive integer n such that 20 ≡ n (mod 29)? Solution: 28 By Fermat’s Little Theorem, a ≡ 1 (mod 29) for all positive integers a that are not multiples 14 15 of 29. It follows that a ≡ ± 1 (mod 29), so a ≡ ± a (mod 29) for all such a . Thus, if 15 14 28 a ≡ 20 (mod 29), then ± a ≡ 20 (mod 29). We know that 9 = 3 ≡ 1 (mod 29), so 15 14 14 28 9 ≡ 9 (mod 29). Next we try a = 20, and we find that 20 ≡ 49 ≡ 7 ≡ 1 (mod 29), 15 and so 20 ≡ 20 (mod 29). Therefore, the smallest such a is 20 . Author: Heesu Hwang