If $\alpha, \beta$ are the roots of the equation $x^2-(p+1)x+1=0.$ show that $\alpha^n + \beta^n$ is not divisible by $p$ $(p \ge3)$

Question

Let $p \ge 3$ be an integer and $\alpha, \beta$ are the roots of the equation $x^2-(p+1)x+1=0.$ Using mathematical induction show that $\alpha^n + \beta^n$

(i) is an integer

(ii) is not divisible by $p$

First part is fairly easy, as we can write $(\alpha^n+\beta^n)(\alpha+\beta)= \alpha^{n+1}+\beta^{n+1}+\alpha^{n-1}+\beta^{n-1}$ and then we can show that $P(n+1)\in\Bbb Z$.

For the second part, we can show patterns of remainder in $P(1)$, $P(2),\dots$ but I was looking for general proof for the same.

Answer 1

Hint. From Vieta's $$\alpha+\beta =p+1$$ $$\alpha\cdot\beta =1$$ or $$\alpha+\frac{1}{\alpha}=p+1 \equiv \color{red}{1} \pmod{p}$$ $$\alpha^2+\frac{1}{\alpha^2}=(p+1)^2-2 \equiv \color{red}{-1} \pmod{p}$$

and by induction $$\alpha^{n+1}+\frac{1}{\alpha^{n+1}}= \left(\alpha^n+\frac{1}{\alpha^n}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha^{n-1}+\frac{1}{\alpha^{n-1}}\right) \tag{1}$$

---

Using $(1)$ $$\alpha^{3}+\frac{1}{\alpha^{3}}= \left(\alpha^2+\frac{1}{\alpha^2}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha+\frac{1}{\alpha}\right) \equiv \color{red}{-2} \pmod{p}$$ $$\alpha^{4}+\frac{1}{\alpha^{4}}= \left(\alpha^3+\frac{1}{\alpha^3}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha^{2}+\frac{1}{\alpha^{2}}\right) \equiv -1 \pmod{p}$$ $$\alpha^{5}+\frac{1}{\alpha^{5}}= \left(\alpha^4+\frac{1}{\alpha^4}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha^{3}+\frac{1}{\alpha^{3}}\right) \equiv 1 \pmod{p}$$ $$\alpha^{6}+\frac{1}{\alpha^{6}}= \left(\alpha^5+\frac{1}{\alpha^5}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha^{4}+\frac{1}{\alpha^{4}}\right) \equiv 2 \pmod{p}$$ $$\alpha^{7}+\frac{1}{\alpha^{7}}= \left(\alpha^6+\frac{1}{\alpha^6}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha^{5}+\frac{1}{\alpha^{5}}\right) \equiv \color{red}{1} \pmod{p}$$ $$\alpha^{8}+\frac{1}{\alpha^{8}}= \left(\alpha^7+\frac{1}{\alpha^7}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha^{6}+\frac{1}{\alpha^{6}}\right) \equiv \color{red}{-1} \pmod{p}$$ $$\alpha^{9}+\frac{1}{\alpha^{9}}= \left(\alpha^8+\frac{1}{\alpha^8}\right)\cdot\left(\alpha+\frac{1}{\alpha}\right)-\left(\alpha^{7}+\frac{1}{\alpha^{7}}\right) \equiv \color{red}{-2} \pmod{p}$$

The reminder "period" starts revealing, given that $R(\alpha, n) = \alpha^{n}+\frac{1}{\alpha^{n}} \pmod {p}$ $$R(\alpha, n)=R(\alpha, n-1)-R(\alpha, n-2)$$

Answer 2

Let $S_n=\alpha^n+\beta^n$. Then $S_1 \equiv -1$ (mod $p$) and so from your first part, we have: $S_{n-1}+S_n+S_{n+1} \equiv 0$ (mod $p$); replacing $n$ by $n-1$ and subtracting, we get: $S_{n+1} \equiv S_{n-2}$ (mod $p$), so you can use this to prove the pattern or argue by induction (with first three values as base cases).