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)$ 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.
 A: 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)$$
A: 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).
