HMMT 二月 2004 · 代数 · 第 9 题

英文解析

9. A sequence of positive integers is defined by a = 1 and a = a + 1 for each n ≥ 0.
   0 n +1
   Find gcd( a , a ).n
   999 2004
   Solution: 677
   If d is the relevant greatest common divisor, then a = a + 1 ≡ 1 = a (mod d ),2
   1000 0
   which implies (by induction) that the sequence is periodic modulo d , with period 1000.999
   In particular, a ≡ a ≡ 0. So d must divide a . Conversely, we can see that
   4 2004 4
   a = a + 1 ≡ 1 = a modulo a , so (again by induction) the sequence is periodic 2
   5 0 4
   modulo a with period 5, and hence a , a are indeed both divisible by a . So the 4
   4 999 2004 4
   answer is a , which we can compute directly; it is 677. 4