Problem 30 · 2009 Math Kangaroo
Stretch
Number Theory
mod-10divisibility
A sequence of whole numbers is defined by \(a_0=1\), \(a_1=2\) and \(a_{n+2}=a_n+(a_{n+1})^2\) for \(n\ge 0\). When \(a_{2009}\) is divided by 7, the remainder is
Show answer
Answer: B — 1
Show hints
Hint 1 of 2
Remainders on division by 7 repeat, so compute the sequence mod 7 until it cycles.
Still stuck? Show hint 2 →
Hint 2 of 2
Find the cycle length, then locate 2009 within the cycle.
Show solution
Approach: find the period of the sequence modulo 7
- Reducing a₀ = 1, a₁ = 2, aₙ₊₂ = aₙ + aₙ₊₁² modulo 7 gives a repeating block of length 10.
- Since 2009 ≡ 9 (mod 10), a₂₀₀₉ matches the 9th term of the cycle.
- That remainder is 1.
Mark:
· log in to save