HMMT 二月 2004 · 代数 · 第 9 题

HMMT February 2004 — Algebra — Problem 9

A sequence of positive integers is defined by a = 1 and a = a + 1 for each n ≥ 0. 0 n +1 n Find gcd( a , a ). 999 2004

解析

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