Say $P_0=3,P_1=0$, $P_2=2$ and $P_n= P_{n-2}+P_{n-3}$. Then $p\mid P_p$ if $p$ prime.

Question

Is a proof number 1 on Bogomolny's page valid, namely how does he know that $z$ is an integer? Obviously $r_1,r_2,r_3$ are not an integers.

Answer 1

I am trying to give the one or the other sense to Proof 1 from the linked address.

---

First way to proceed:

Let $R$ be the ring of algebraic integers $R$ of the splitting field $L$ of the polynomial $f=x^3-x-1$ involved in the recursion for $(P_n)$. Let $r,s,t\in R$ be the roots of $f$, they are algebraic integers, since the minimal polynomial $f$ lies in $\Bbb Z[x]$.

Now consider the Proof 1, as a computation in $R$, and everything works fine.

We have: $$ \begin{aligned} &(r+s+t)^p-r^p-s^p-t^p \\ &\qquad= \sum_{\substack{a+b+c=p\\a,b,c\ne p}} \frac {p!}{a!b!c!} \; r^a\; s^b\; t^c \\ &\qquad= p \cdot \underbrace{ \sum_{\substack{a+b+c=p\\a,b,c\ne p}} \underbrace{\frac {(p-1)!}{a!b!c!}}_{\in\Bbb Z\subset R} \; \underbrace{r^a\; s^b\; t^c}_{\in R} }_{\in R\cap \Bbb Q=\Bbb Z} \\ &\qquad=pz \ , \end{aligned} $$ where as shown above $z\in \Bbb Q\cap R=\Bbb Z$, since the algebraic integers in the field $L$, which are also in $\Bbb Q$, are integers in $\Bbb Q$ (i.e. satisfy a monic polynomial with integer coefficients), and thus are integers.

---

Second way to proceed:

We have to show that an equality of integers holds modulo $p$. We consider this equality modulo $p$. So we consider instead the sequence $(P_n\text{ modulo }p)_n$ as a sequence in the field $\Bbb F_p=\Bbb Z/p$. The polynomial $X^3-X-1$ has three roots in some extension of the field, (which are different in characteristic $p\ne 23$), let us denote them by $r,s,t$. Then as it happened inductively over $\Bbb Z$, we have the same algebraic formula for $P_n$, and then: $$ P_p\text{ modulo }p =r^p+s^p+t^p=(r+s+t)^p=0^p=0\ . $$

---

Bonus:

Not strictly related to the question, but this may be a useful additional information, we use some computational aid and will work in the ring of algebraic integers $R$ of the splitting field $L=\Bbb Q[a]$ of the polynomial $x^3-x-1$ involved in the recursion for $(P_n)$.

This ring $R$ is a unique factorization domain, which is not an obvious fact. For this i asked the computer:

sage: S.<x> = PolynomialRing(QQ)
sage: f = x^3 - x - 1
sage: L.<a> = f.splitting_field()
sage: L.class_number()
1
sage: L.is_unique_factorization_domain()
True
sage: a.minpoly()
x^6 + 3*x^5 + 19*x^4 + 31*x^3 + 121*x^2 + 143*x + 307
sage: L
Number Field in a with defining polynomial x^6 + 3*x^5 + 19*x^4 + 31*x^3 + 121*x^2 + 143*x + 307

sage: SL.<X> = PolynomialRing(L)
sage: roots = ( X^3 - X - 1 ).roots(multiplicities=False)

sage: for r in roots:
....:     print r
....:     
1/69*a^5 + 1/23*a^4 + 5/23*a^3 + 35/69*a^2 + 68/69*a + 146/69
-3/575*a^5 - 12/575*a^4 - 19/575*a^3 - 162/575*a^2 - 6/23*a - 904/575
-16/1725*a^5 - 13/575*a^4 - 106/575*a^3 - 389/1725*a^2 - 50/69*a - 938/1725

sage: for r in roots:
....:     print r.norm(), r.is_unit(), r.is_integral()
....:     
1 True True
1 True True
1 True True

Above, sage computes a generator $a$ for the extension $L:\Bbb Q$, it is some choice of a generator, which is an algebraic integer in $L$. Of course, the roots of $(X^3-X-1)$ in $L$ are also algebraic integers, they have norm one, so they are units. An additional information is that $L$ is a unique factorization domain.