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

HMMT November 2016 — GEN Round — Problem 9

Let the sequence a be defined as a = 2 . Find the number of integers 1 ≤ n ≤ 1000 such that if i i +1 a = n , then 100 divides a − a . 0 1000 1

解析

Let the sequence a be defined as a = 2 . Find the number of integers 1 ≤ n ≤ 1000 such that if i 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 .