If $x_1, x_2$ are roots of $P(x)=x^2-6x+1$, prove that $5 \nmid x_1^n+x_2^n$

Question

Given $x_1$ and $x_2$ are roots of $P(x)=x^2-6x+1$ prove using Binomial expansion that $x_1^n+x_2^n$ is not divisible by 5 if $n\in \Bbb N\setminus\{0\}$.

Source: list of problems for the preparation for math contests.

Notice: this problem is different from other SE question, as it requires a specific proof that was suggested by @DeepSea in a comment in that post, but not developed.

My attempt: By solving the roots of $P(x)$ it is easy to see that $$x_1=3+2\sqrt{2}\ \ \text{and}\ \ \ x_2=3-2\sqrt{2}$$ and, using the Binomial expansion, $$x_1^n+x_2^n=(x_1+x_2)^n-\sum_{k=1}^{n-1}{{n-1}\choose {k}} x_1^{n-k}x_2^k=6^n-\sum_{k=1}^{n-1} {{n-1}\choose {k}}x_1^{n-k}x_2^k$$

It is easy to see that $6^n\equiv 1\pmod{5}$ for all possible $n$. Therefore the problem is showing that for $$A(n)=\sum_{k=1}^{n-1}{{n-1}\choose {k}}x_1^{n-k}x_2^k,\ \ A(n)\not\equiv 1\pmod{5},\ \forall n\in \Bbb N\setminus\{0\}.$$

My problem is on how to proceed with the proof of this last statement. Hints and answers are welcomed.

Answer 1

I think you misinterpreted the suggestion by @DeepSea. He probably meant expanding $(3\pm2\sqrt{2})^n$ instead of $(x_1+x_2)^n$.

So if we follow this and binomial expand $(3\pm 2\sqrt{2})^n$, we have $$ x_1^n+x_2^n=\sum_{k=0}^n\binom{n}{k}3^{n-k} (2\sqrt{2})^k \underbrace{[1+(-1)^k]}_{=\begin{cases}2&k\text{ even}\\0&k\text{ odd}\end{cases}} $$ So we cancel the odd $k$ terms and are left with $$ x_1^n+x_2^n=2\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}3^{n-2k} (2\sqrt{2})^{2k} \equiv 2\cdot3^n\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}3^{-k}\pmod{5}. $$ Hence we want to prove $$ \sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}(-3)^k\not\equiv 0\pmod{5} $$ which I don't see a way without

Cheating

So we look at an equivalent problem with roots $1\pm\sqrt{-3}\pmod{5}$, which if we take out a common factor of $2$ (doesn't change mod 5 nonzero) becomes a problem with roots $y_\pm=\frac12(1\pm\sqrt{-3})$ (which are of course the roots of $y^2-y+1$, what you get from reducing coefficients of $P$ mod $5$). Now these roots are sixth roots of unity, so $y_+^n+y_-^n$ only take values $\pm 1,\pm 2$.

This leaves the question: why not reduce $P$ mod 5 right at the start and be done with it?

Answer 2

Let $a_n = x_1^n+x_2^n$. Then modulo $5$, $a_1 =1, a_2= 2, a_n = a_{n-1}-a_{n-2}$

We can see that the terms of the sequence are periodic. They go 1,2,1,-1,-2,-1,1 and the cycle continues so that no term is $0$ modulo 5

Answer 3

Here is a solution inspired by Pell's equations, which tangentially is related to Binomial expansion. $(3,2)$ is a solution for $$x^2-2y^2=1 \tag{1}$$ but then any $(x,y)$ of the form $$x=\frac{\left(3+2\sqrt{2}\right)^n+\left(3-2\sqrt{2}\right)^n}{2} \space\space\space\text{ and }\space\space\space y=\frac{\left(3+2\sqrt{2}\right)^n-\left(3-2\sqrt{2}\right)^n}{2\sqrt{2}}$$ where $$x+y\sqrt{2}=\left(3+2\sqrt{2}\right)^n \space\space\space\text{ and }\space\space\space x-y\sqrt{2}=\left(3-2\sqrt{2}\right)^n$$ is also a solution. Using binomial expansion it is easy to check $x,y \in \mathbb{Z}$ and $$2x=x_1^n+x_2^n \tag{2}$$ Now, proof by contradiction. If $5 \mid x_1^n+x_2^n \overset{\color{red}{(2)}}{\Rightarrow} 5 \mid x$, this is from Euclid's lemma. But then $$5\mid x^2 \overset{\color{red}{(1)}}{\Rightarrow} 5 \mid 2y^2+1$$ However $2y^2+1$ is never divisible by $5$. This is easy to see from $y^4 \equiv 1 \pmod{5}$ (LFT) or $5 \mid \left(y^2-1\right)\left(y^2+1\right)$ (applying the same Euclid's lemma)

• if $5 \mid y^2+1 \Rightarrow 5 \nmid 2y^2+1=y^2+1+y^2$, otherwise $5 \mid y^2$ leading to $5 \mid 1$.
• if $5 \mid y^2-1 \Rightarrow 5 \nmid 2y^2+1=2(y^2-1)+3$, otherwise $5 \mid 3$.

Alternatively, it's easy to check that $2y^2+1$ never has $0$ or $5$ as the last digit. $$2\cdot \color{blue}{0}^2+1=1 \text{, }\space\space 2\cdot \color{blue}{1}^2+1=3 \text{, }\space\space 2\cdot \color{blue}{2}^2+1=9 \text{, }\space\space 2\cdot \color{blue}{3}^2+1=19 \text{,}\\ 2\cdot \color{blue}{4}^2+1=33 \text{, }\space\space 2\cdot \color{blue}{5}^2+1=51 \text{, }\space\space 2\cdot \color{blue}{6}^2+1=73 \text{, }\space\space 2\cdot \color{blue}{7}^2+1=99 \text{,}\\ 2\cdot \color{blue}{8}^2+1=129 \text{, }\space\space 2\cdot \color{blue}{9}^2+1=163$$ So we have a contradiction.