Sequence $ a_0=1,a_1=3$ and $a_{n+2}=4a_{n+1}-a_n $. Prove that $2017|a^2_{2017}-4a_{2017}+3$

Question

I need a solution verification for next problem.

Let sequence $a_0,a_1,...$ be such that: $ a_0=1,a_1=3$ and $a_{n+2}=4a_{n+1}-a_n $. Prove that $$2017\mid a^2_{2017}-4a_{2017}+3$$

By solving this recurrence we get $$a_n = {3+\sqrt{3}\over 6}(2+\sqrt{3})^n+{3-\sqrt{3}\over 6}(2-\sqrt{3})^n$$

Notice that $p:=2017$ is prime. By Gauss reciprocity law we have $\big({3\over p}\big) = 1$ so there exists $a\in \mathbb{Z}_p$ such that $a^2\equiv 3 \pmod p$. Consider now this sequence in the field $\mathbb{Z}_p$. So we have $$6a_n = (3+a)(2+a)^n+(3-a)(2-a)^n$$

By Fermat little theorem we have $$6a_p\equiv _p (3+a)(2+a)+(3-a)(2-a) \equiv_p 18$$

So, since $p\nmid 6$ we have $a_p \equiv_p 3$ and thus a conclusion.

Answer 1

Your proof works.

I wondered why they chose $$f(m)=m^2-4m+3=(m-1)(m-3),$$ I see when $p=5,7$ that $a_p\equiv 1\pmod p.$

I wonder if this is true for all primes. To prove that, you’d want to to show that if $\left(\frac 3p\right)=-1$ then $a_p\equiv 1\pmod p.$

---

Proof as outlined by commenter Derive Foiler.

If $\left(\frac 3p\right)=-1$ then we have $F_{p^2}=\mathbb F_{p}[\sqrt{3}].$ And the map $f:F_{p^2}\to F_{p^2}$ sending $u\to u^p$ is a non-trivial automorphism. So $f(a+b\sqrt{3})=a-b\sqrt 3.$

Then:

$$6a_n = (3+\sqrt{3})(2-\sqrt{3})+(3-\sqrt{3})(2+\sqrt 3)=6$$

So $a_n\equiv 1\pmod p.$

---

This shows more generally, if $T_{n+1}=bT_n+cT_{n-1}$ with $b,c$ integers and $T_0,T_1$ integers, and $b^2+4c$ is not a perfect square, then when $p\not\mid b^2+4c$ is an odd prime, then $T_p$ is congruent to one of two values, depending on the value of $\left(\frac{b^2+4c}{p}\right).$

When $\left(\frac{b^2+4c}p\right)=1,$ the specific values is $T_p\equiv T_1\pmod p.$

You also get when $\left(\frac{b^2+4c}{p}\right)=-1,$ that $T_p \equiv -cT_{-1}\pmod{p}$ where $T_1=bT_0+cT_{-1},$ or $-cT_{-1}=bT_0-T_1.$ For example, in our current question, $c=-1,b=4$ we get $-cT_{-1}=1.$

So you also get only one value if $bT_0-T_1=-cT_{-1}=T_0,$ or if $(b-1)T_0=T_1.$

A closed form when $T_0=0$:

$$T_p\equiv \left(\frac{b^2+4c}{p}\right)T_1$$ which becomes much easier if $T_0=0.$

For another example, for Fibonacci numbers, $b^2+4c=5,$ then if $p\equiv\pm 1\pmod{5}$ then $F_p\equiv F_1=1\pmod p$ and when $p\equiv \pm 2\pmod 5$ then $F_p\equiv F_0-F_1=-1\pmod{p}.$

(If $b^2+4c$ is a perfect square, including $0,$ then there is one value $d$ such that $T_p\equiv d\pmod p$ for all odd primes $p\not\mid b^2+4c.$ (For $b^2+4c=0,$ it is one value for any $p\not\mid b.$)

Answer 2

That was a good question followed by a good discussion. Thanks! As the size of this remark which I am going to write doesn't fit in the comment section, I am forced to include this in answer section.

I was wondering if for a person like me who isn't well versed with field extensions, it was possible to realize the facts discussed here with elementary knowledge. I was restless till I could realize one:

Assuming the relation for $a_n$ (after solving the recurrence relation), we may write: $$ 6a_n = (3+\sqrt{3})(2+\sqrt{3})^n + (3-\sqrt{3})(2-\sqrt{3})^n.$$ Supposing that $n$ is odd, if we apply the binomial expansion and simplify the above expression, it turns out to be $$ 6a_n = 2 \left(3\sum\limits_{k=0}^{\frac{n-1}{2}} {}^nC_{2k}2^{n-2k}3^k+ \sum\limits_{k=0}^{\frac{n-1}{2}} {}^nC_{2k+1}2^{n-2k-1}3^{k+1}\right).$$ If $n=p$ is a prime, then ${}^pC_k \equiv 0 \pmod p$ for all $0<k< p$. Using this fact in the above equation, we will be left out with $$ \tag{1}\label{1}6a_p \equiv 2\left( 2^p\times3 + 3^{\frac{p+1}{2}}\right) \pmod p. $$ Assuming $p>3$, if $\left(\frac{3}{p}\right) = 1$, then $3^{\frac{p+1}{2}} \equiv 3 \pmod p$. Using this along with Fermat's theorem in the above, we have $$a_p \equiv 3 \pmod p. $$ If $\left(\frac{3}{p}\right) = -1$, then $3^{\frac{p+1}{2}} \equiv -3 \pmod p$. Using this along with Fermat's theorem in $\eqref{1}$, we get $$ a_p \equiv 1 \pmod p. $$ In any case, for any prime $p > 3$, we have $$p|a_{p}^2 - 4a_p +3.$$

I couldn't control writing it here. This way is, of course, restricted to this particular problem which may not lead to discussions in general cases as was done by Thomas.