Library / /23 of 69

, 2011

Number theory Difficulty 4.8 AIME Prove it South Africa

For each positive integer $a$ we consider the sequence $(a_n)$ with $a_0 = a$ and $a_n = a_{n-1} + 40^n$ for $n > 0$ . Prove that every such sequence contains infinitely many numbers that are divisible by $2009$ .

Solution

Since $\gcd(40, 2009) = 1$ , we have $40^{k \cdot \varphi(2009)} \equiv 1 \pmod{2009}$ for all natural numbers $k$ . For $n > \varphi(2009)$ the exponent $n!$ is certainly a multiple of $\varphi(2009)$ , and therefore $a_{n+1} \equiv a_n + 1 \pmod{2009}$ . This means that all values modulo $2009$ are taken cyclically and periodically, and all values are obtained infinitely often. Since this also for the value $0$ , the proof is complete.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.