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|$


1 Answer 1


(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.

$\qquad$$a_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|$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .