HMMT February

Algebra Difficulty 5.1 AIME, harder Find the answer

A sequence of positive integers is defined by $a_{0}=1$ and $a_{n+1}=a_{n}^{2}+1$ for each $n \geq 0$ . Find $\operatorname{gcd}(a_{999}, a_{2004})$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

If $d$ is the relevant greatest common divisor, then $a_{1000}=a_{999}^{2}+1 \equiv 1=a_{0}(\bmod d)$ , which implies (by induction) that the sequence is periodic modulo $d$ , with period 1000 . In particular, $a_{4} \equiv a_{2004} \equiv 0$ . So $d$ must divide $a_{4}$ . Conversely, we can see that $a_{5}=a_{4}^{2}+1 \equiv 1=a_{0}$ modulo $a_{4}$ , so (again by induction) the sequence is periodic modulo $a_{4}$ with period 5 , and hence $a_{999}, a_{2004}$ are indeed both divisible by $a_{4}$ . So the answer is $a_{4}$ , which we can compute directly; it is 677.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.