# Chinese Olympiad 2019 Round 2 Question 3

I came across this question and the AOPS website has two response: one is written in Chinese which I have no clue about and there's another approach which I'm not familiar with. Can anyone suggest any other way to approach this question? I have tried attempting this question but my method is not making any sense. Thanks in advance!

Let $$m$$ be an integer where $$|m|\ge 2$$. Let $$a_1,a_2,\cdots$$ be a sequence of integers such that $$a_1,a_2$$ are not both zero, and for any positive integer $$n$$, $$a_{n+2}=a_{n+1}-ma_n$$.

Prove that if positive integers $$r>s\ge 2$$ satisfy $$a_r=a_s=a_1$$, then $$r-s\ge |m|$$

• Can you put a link to the question? Commented May 5, 2020 at 12:18
• Commented May 5, 2020 at 12:33

(Note: This is the official solution in Chinese which I had translated. It is not my original solution)

Assume that $$a_1, a_2$$ are coprime, (otherwise $$(a_1,a_2)=d>1,\frac{a_1}{d}$$ and $$\frac{a_2}{d}$$ are coprime, we can substitute $$\frac{a_1}{d}, \frac{a_2}{d}, \frac{a_3}{d}, \cdots$$ with $$a_1, a_2, a_3, \cdots$$ and the conclusion remains unchanged.)

We know that $$a_2\equiv a_3 \equiv a_4\equiv \cdots \pmod{|m|}$$. ----(1)

Using induction, we will show that $$a_n\equiv a_2-(a_1+(n-3)a_2)m \pmod{m^2}$$ is true for any integer $$n\ge3$$----(2)

Base case $$n=3$$: it is obviously true.

Assuming it holds for $$n=k$$, where k is some integer $$>2$$,

From (1), $$ma_{k-1}\equiv ma_2 \pmod{m^2}$$

$$a_{k+1}=a_k-ma_{k-1}\equiv a_2-(a_1+(k-3)a_2)m-ma_2\equiv a_2-(a_1+(k-2)a_2)m \pmod{m^2}$$

$$\therefore$$ (2) is true for all integers $$n \ge 3$$.

If $$a_1=a_2$$, (2) is true for $$n=2$$ as well.

$$\qquada_2-(a_1+(r-3)a_2)m \equiv a_r \equiv a_s \equiv a_2-(a_1+(s-3)a_2)m \pmod{m^2}$$

$$\qquad$$Since $$a_1+(r-3)a_2 \equiv a_1+(s-3)a_2 \pmod{|m|}$$, $$(r-s)a_2 \equiv 0 \pmod{|m|}$$ ----(3)

Else if $$a_1\neq a_2,a_r=a_s=a_1\neq a_2, \therefore r>s\ge3$$,

$$\qquad$$ We will prove $$a_2$$ and $$m$$ are coprime.

$$\qquad$$ if they have common prime factor $$p$$, $$p$$ is also a common prime factor of $$a_2, a_3, a_4, \cdots$$. Since $$a_1, a_2$$ are coprime, so $$p\nmid a_1$$, which would contradict $$a_r=a_s=a_1$$, therefore not possible

Hence from (3) $$r-s\equiv 0 \pmod{|m|}$$, and since $$r>s$$, $$\therefore r-s\ge|m|$$

• That's great! Beautiful solution well done :) Commented May 6, 2020 at 6:24
• This is actually just the solution in Chinese that I translated, not my original solution. Just added a clarification Commented May 6, 2020 at 11:06