HMMT 十一月 2016 · GEN 赛 · 第 9 题

英文解析

9. Let the sequence a be defined as a = 2 . Find the number of integers 1 ≤ n ≤ 1000 such that ifi i +1
   a = n , then 100 divides a − a .
   0 1000 1
   Proposed by: Allen Liu
   Answer: 50
   We claim that a is constant mod 100.
   1000
   a is divisible by 2. This means that a is divisible by 4. Thus a is constant mod 5. Since it
   997 998 999
   is also divisible by 4, it is constant mod 20. Thus a is constant mod 25, since φ (25) = 20. Since
   1000
   a is also divisible by 4, it is constant mod 100.
   1000
   We know that a is divisible by 4, and let it be congruent to k mod 25.
   1000
   n n
   Then 2 is divisible by 4 ( n ≥ 2) and 2 ≡ k mod 25 We can also show that 2 is a primitive root mod 25,
   0 mod 4
   2 16 mod 20
   so there is one unique value of n mod 20. It suffices to show this value isn’t 1. But 2 ≡ 2
   mod 25, so n ≡ 16 mod 20. Thus there are 1000 / 20 = 50 values of n .