Define a sequence of integers $a_0=m, a_1=n$ and $a_{k+1}=4a_k-5a_{k-1}$ for all $k \ge 1$. Suppose $p>5$ is a prime with $p \equiv 1 \pmod{4}$. Prove that it is possible to choose $m,n$ such that $p \nmid a_k$ for any $k \ge 0$.
Problem
Source: India TST 2017 D1 P2
Tags: number theory
Kayak
09.12.2017 18:03
I'm very sure that my solution is flawed, because otherwise its way too easy for TST. Can anybody please check ?
As $p \equiv \mod 4$, by primitive roots/QR, we see that there exists a number $b$ such that $b^2 \equiv (-b)^2 \equiv -1 \mod p$. By a very easy induction, we see the $k$-th term of the sequence is given by $$ a_{k} \equiv q(2+b)^k + r(2-b)^k \mod p$$, for some hideous constants $q, r$. If we choose $m = 1, n = 2+b$, it works, since then we get (note that $p > 5$ implies $|b| \neq 2$, hence $2 \pm b$ is invertible modulo $p$) $q = 1, r = 0$, so the general term is $$ a_k \equiv (2+b)^k \mod p$$, which is obviously never equivalent to zero modulo $p$.
As a side note, is the problems in Indian TST arranged by difficulty (i.e $1 < 2 < 3$ in terms of hardness ?) Edit: Yay thanks to LSG anantmudgal09 for checking my proof.
Mathotsav
10.12.2019 16:05
My solution: If $p=5$ just choose $a_0=a_1=1$ and we are trivially done. Now suppose $p \neq 5$. Since $p$ is of the form $1$ mod $4$, there exist positive integers $a,b$ such that $a>b$(WLOG) and $a^2+b^2=p$. We claim that the choice $a_0=a, a_1=2a-b$ works. Lemma: For the above mentioned choices, $a_n=Re((a+bi)*(2+i)^n)$. Proof: Use characteristic roots and the general method to solve recurrence relations to get $a_n=\frac{(a+bi)(2+i)^n+(a-bi)(2-i)^n}{2}$ and the lemma follows immediately. Now consider the number $a_n$. Let $(a+bi)(2+i)^n=c+di$. Thus, $c=a_n$ from our lemma. Also note that $c^2+d^2=p*5^n$. Now if $p|c$ we must have $p|d$ by mod $p$ but then $p^2|c^2+d^2=p*5^n$ which means $p|5^n$, contradiction as $p \neq 5$. Thus $p$ doesn't divide $c=a_n$ for any $n$. Done
karitoshi
04.03.2020 14:08
We have $a_ka_{k+2}-a_{k+1}^2=5^k(4mn-5m^2-n^2)$ Since $p \equiv 1$ (mod $p$), there is exist $m,n$ such that: $m^2 \equiv -1$(mod $p$); $n \equiv 2m+1$ (mod $p$).=>$$a_ka_{k+2} \equiv a_{k+1}^2$$ So if $p|a_{k+2}$ then $p|a_{k+1}$=>...=>contradiction. Q.E.D