PUMaC 2020 · 数论（A 组） · 第 8 题
PUMaC 2020 — Number Theory (Division A) — Problem 8
题目详情
- What is the smallest integer a such that, for every positive integer n , there exists a sequence 0 of positive integers a , a , ..., a , a such that the first n − 1 are all distinct, a = a , and for 0 1 n − 1 n 0 n a i +1 0 ≤ i ≤ n − 1, a ends in the digits 0 a when expressed without leading zeros in base 10? i i 1
解析
- What is the smallest integer a such that, for every positive integer n , there exists a sequence 0 a i +1 of distinct positive integers a , a , ..., a , a such that a = a , and for 0 ≤ i ≤ n − 1, a 0 1 n − 1 n 0 n i ends in the digits 0 a when expressed without leading zeros in base 10? i Proposed by: Austen Mazenko Answer: 7 a 1 Evidently, a must be relatively prime to 10. First, we note that a 6 = 3; if it were, then 3 ≡ 3 0 0 (mod 100), and since ord (3) = 20 we need a ≡ 1 (mod 20). Furthermore, if a has k digits, 100 1 1 3 k +1 k +1 k +1 we need a ≡ a (mod 10 ), so ( a − 1)( a +1) ≡ 0 (mod 10 ). Thus, a ≡ 1 (mod 5 ), 1 1 1 1 1 which combined with a ≡ 1 (mod 4) means ν ( a + 1) = 1. But, ν (( a − 1)( a + 1)) ≥ k + 1 1 2 1 2 1 1 k k +1 k so ν ( a − 1) ≥ k . In particular, a − 1 ≥ 2 · 5 = 5 · 10 , so a has more than k digits, 2 1 1 1 contradiction. 8 Now we claim that a = 7 works. If n = 2, then pick a = 2 · 5 − 1 = 781249. First, 0 1 781249 2 ord (7) = 4, and since 781249 ≡ 1 (mod 4) we have 7 ≡ 7 (mod 100). Then, 781249 ≡ 100 8 8 2 8 8 7 8 2 · 5 · (2 · 5 − 2) + 1 ≡ 2 · 5 · (5 − 1) ≡ 1 (mod 10 ) since ν (5 − 1) = 2 + 3 + 1 − 1 = 5 by 2 6 2 3 7 LTE. Hence, 781249 ≡ (781249 ) ≡ 1 (mod 10 ), as desired. k Otherwise, consider the arbitrarily long sequence a = 7 , a = 2 · 10 + 1 , a = 74218751 for 0 k n − 1 21 0 < k < n − 1 First, 21 ≡ 1 (mod 4) implies 7 ≡ 7 (mod 100). Now, by the binomial theorem k 50 k +2 k +1 it is evident (2 · 10 +1) ≡ 1 (mod 10 ), and because 2 · 10 +1 ≡ 1 (mod 50) for k ≥ 1, we k +1 k 2 · 10 +1 k k +2 have (2 · 10 +1) ≡ 2 · 10 +1 (mod 10 ), and similarly for the exponent 74218751 ≡ 1 2 9 9 (mod 50). It remains to show 74218751 ≡ 1 (mod 10 ). We have 74218750 = 2 ∗ 5 ∗ 19 + 1, 4 2 9 9 9 so 74218751 − 1 = 2 · 5 · 19 · 2(5 · 19 + 1), meaning we must show ν (5 · 19 + 1) ≥ 7. Now, 2 3 7 9 7 9 7 5 ≡ − 3 (mod 2 ), so 5 ≡ − 27 (mod 2 ), thus 5 · 19+1 ≡ − 27 · 19+1 ≡ − 512 ≡ 0 (mod 2 ), as desired. 5