Olympiad Maths Prep

Track / Stage 7 / 274 of 300 #1674 of 2000

Problem 1674

National olympiad second round; IMO P1/P4
Algebra Difficulty 7.8 Prove it IMO HK TST · Hong Kong

Let rr be the positive root of the equation x2−2004x−1=0x^2 - 2004x - 1 = 0. Define the sequence {an}\{a_n\} as follows:
a0=1,an+1=[ran],n≥0, a_0 = 1, a_{n+1} = [ra_n], n \ge 0,
where [y][y] denotes the greatest integer not exceeding yy. Find the remainder when a2004a_{2004} is divided by 20042004.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

The answer is 10031003.

Note that
r=2004+20042+42 r = \frac{2004 + \sqrt{2004^2 + 4}}{2}
is an irrational number greater than 11. Since an∈Z+a_n \in \mathbb{Z}^+, we have ran∉Qra_n \notin \mathbb{Q}. Thus, we obtain
an+1<ran<an+1+1 a_{n+1} < ra_n < a_{n+1} + 1
for any n≥0n \ge 0. Equivalently, we have
an−1r<an+1r<an. a_n - \frac{1}{r} < \frac{a_{n+1}}{r} < a_n.
As r>1r > 1, this yields an−1<an+1r<ana_n - 1 < \frac{a_{n+1}}{r} < a_n, and hence
[an+1r]=an−1. \left[ \frac{a_{n+1}}{r} \right] = a_n - 1.
Next, observe that r=2004+1rr = 2004 + \frac{1}{r}. It follows that
an+1=[ran]=[2004an+anr]=2004an+an−1−1 a_{n+1} = [ra_n] = \left[ 2004a_n + \frac{a_n}{r} \right] = 2004a_n + a_{n-1} - 1
since 2004an∈Z2004a_n \in \mathbb{Z} and [anr]=an−1−1\left[ \frac{a_n}{r} \right] = a_{n-1} - 1 from above. Thus, we obtain
an+1≡an−1−1(mod2004) a_{n+1} \equiv a_{n-1} - 1 \pmod{2004}
for any n∈Z+n \in \mathbb{Z}^+. Then we can easily obtain
a2004≡a2002−1≡a2000−2≡⋯≡a0−1002≡1003(mod2004). a_{2004} \equiv a_{2002} - 1 \equiv a_{2000} - 2 \equiv \cdots \equiv a_0 - 1002 \equiv 1003 \pmod{2004}.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.