Exercise 4.4.27* ($p \mid u_p$, where $u_{n+1} = u_{n-1} + u_{n-2}, u_1 = 0, u_2 = 2, u_3 = 3$)

Question

Let the sequence $u_n$ be determined by the relations $u_1 = 0,\ u_2 = 2, u_3 = 3$, and $u_{n+1} = u_{n-1} + u_{n-2}$ for $n \geq 3$. Prove that if $p$ is prime then $p \mid u_p$. (The least composite number with this property is $271,441 = 521^2$.)

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

\begin{proof} 
The associate characteristic polynomial  is 
$$p(x) = x^3 - x - 1.$$
Let $\lambda, \mu, 
u$ be the complex roots of $p(x)$. Since $p(x)$ has the form $p(x) = x^3 + px +q$, where $p = q = -1$, the discriminant $D$ of $p(x)$ is $D = -4p^3 - 27q^2 = 4 -27 = -23$. Since $D 
e 0$, the roots $\alpha, \beta, \gamma$ are distinct. (The expression of $\alpha, \beta, \gamma$ by the Cardan's formulas are useless.)

Moreover
$$\lambda + \mu + 
u = 0,\qquad \lambda \mu + \lambda 
u + \mu \lambda = -1,\qquad \lambda \mu 
u = 1.$$
Therefore
\begin{align*}
\lambda + \mu + 
u\quad  &= 0\
&=u_1,\
\lambda^2 + \mu^2 + 
u^2 &= (\lambda + \mu + 
u)^2 - 2 (\lambda \mu + \lambda 
u + \mu \lambda)\
&= 2\
&= u_2,\
\lambda^3 + \mu^3 + 
u^3 &= \lambda + 1 + \mu + 1 + 
u + 1\
&=3\
&= u_3.
\end{align*}
since $\lambda^2 = \lambda + 1, \mu^2 = \mu + 1, 
u^2 = 
u + 1$, we obtain for all $n \in \N$
\begin{align}
\lambda^{n+3} = \lambda^{n+1} + \lambda^n,\qquad \mu^{n+3} = \mu^{n+1} + \mu^n, \qquad  
u^{n+3} = 
u^{n+1} + 
u^n.
\end{align}
Consider the proposition, defined for $n\in \N^*$,
$$\mathscr{P}(n):u_n =  \lambda^n + \mu^n + 
u^n.$$
We have verified that $\mathscr{P}(0), \mathscr{P}(1), \mathscr{P}(2)$ are true.

Suppose now that $\mathscr{P}(n), \mathscr{P}(n+1),\mathscr{P}(n+2)$ are true for some $n \in \N^*$. Then
\begin{align*}
u_{n+3} &= u_{n+1} + u_n\
&=\lambda^{n+1} + \mu^{n+1} + 
u^{n+1} + \lambda^{n} + \mu^n + 
u^n\
&=\lambda^{n+3} + \mu^{n +3}+ 
u^{n+3} & (	ext{by (1)}).
\end{align*}
so $\mathscr{P}(n+3)$ is true.
The induction is done, so for all $n\in \N^*$,
\begin{align}
u_{n} &= \lambda^n + \mu^n + 
u^n.
\end{align}
Consider now the sequence $(v_n)_{n \in \N^*} \in \F_p^{\N^*}$ defined by
$$v_n = \overline{u_n},$$
where $\overline{a}$ denotes the class modulo $p$ of an integer $a$.

Then 
\begin{align*}
&\forall n \in \N^*, n \geq 3 \Rightarrow v_{n+1} = v_{n-1} + v_{n-2},\
&v_1 = \overline{0},\qquad v_2 = \overline{2}, \qquad v_3 = \overline{3}.
\end{align*}
Let $\alpha, \beta, \gamma$ be the roots of $x^3 - x - 1 \in \F_p[x]$ (not necessarily distinct) in a splitting field $K=\F_p(\alpha,\beta,\gamma)$ of $\F_p$ (see examples below), so that
$$x^3 - x - 1 = (x -\alpha)(x- \beta)(x- \gamma).$$
Then
$$\alpha + \beta + \gamma = \overline{0}, \qquad \alpha \beta + \alpha \gamma + \beta \gamma = -\overline{1}, \qquad \alpha \beta \gamma = \overline{1},$$
thus, as above,
\begin{align*}
\alpha + \beta + \gamma\quad &= \overline{0} = v_1,\
\alpha^2 + \beta^2 + \gamma^2 &= \overline{2} = v_2,\
\alpha^3+ \beta^3 + \gamma^3 &= \overline{3} = v_3.
\end{align*}
With a similar easy induction, we obtain for all $n \in \N^*$,
\begin{align*}
v_n = \alpha^n + \beta^n + \gamma^n.
\end{align*}
In particular,
\begin{align*}
v_p &= \alpha^p + \beta^p + \gamma^p.
\end{align*}

Since the characteristic of $K$ is $p$, for all $(u_1,u_2) \in K^2$, $(u_1+u_2)^p = u_1^p + u_2^p$, and by induction, $(u_1+u_2+\cdots +u_n)^p = u_1^p + u_2^p+ \cdots + u_n^p$. Therefore
\begin{align*}
\overline{u_p} = v_p &= \alpha^p + \beta^p + \gamma^p\
&=(\alpha + \beta + \gamma)^p\
&= \overline{0}
\end{align*}
so
$p \mid u_p$.
\end{proof}

{\bf Example 1:} For $p = 59$, $x^3 - x - 1$ has three distinct roots $\alpha = \overline{42}, \beta= \overline{13}, \gamma = \overline{4}$ in $\F_p$ (Here the splitting field of $p(x)$ is $K = \F_p$). By Fermat's theorem, 
$$\alpha^p = \alpha, \qquad \beta^p = \beta, \qquad \gamma^p = \gamma,$$
so
$$v_p = \alpha^p + \beta^p + \gamma^p = \alpha + \beta + \gamma =  \overline{42} + \overline{13} + \overline{4} = \overline{0}.$$

\bigskip
{\bf Example 2:} For $p = 31$, the polynomial $p(x) = x^3 - x- 1$ has no root in $\F^p$, and $\deg(p(x)) = 3$, so $p(x)$ is irreducible over $\F_p$. Then $p(x)$ has three distinct roots $\alpha, \beta, \gamma$ in $K = \F_p[x]/(x^3 - x-1)\simeq \F_{31^3}$. The automorphism of Frobenius $\sigma$ defined by $\sigma(x) = x^p$ satisfies for some good ordering of $\alpha, \beta, \gamma$,
$$\sigma(\alpha) =\alpha^p =  \beta,\qquad \sigma(\beta) = \beta^p =  \gamma, \sigma(\gamma)= \gamma^p  = \alpha,$$ 
so $$v_p = \alpha^p + \beta^p + \gamma^p  = \beta + \gamma + \alpha = 0.$$
Put $\alpha = x+ (x^3 - x - 1)\F_p[x]$, so that $\alpha$ is a root of $p(x)$. The other roots are obtained with Sagemath
\begin{verbatim}
P = x^3 - x - 1
Fp3.<alpha> = GF(p^3, modulus = P)
beta = alpha^p; beta
\end{verbatim}
$$6 \alpha^{2} + 6 \alpha + 27$$
\begin{verbatim}
gamma = alpha^(p^2); gamma
\end{verbatim}
$$25 \alpha^{2} + 24 \alpha + 4$$
\begin{verbatim}
alpha + beta + gamma
\end{verbatim}
$$0$$
\begin{verbatim}
alpha^p + beta^p + gamma^p
\end{verbatim}
$$0$$

\bigskip
{\bf Example 3:} For $p = 17$, there is only one root $\alpha = \overline{5}$ in $\F_{17}$, and $x^3 - x - 1 = (x - \overline{5})(x^2 + \overline{5} x +\overline{7})$.  The irreducible polynomial $x^2 + \overline{5} x +\overline{7}$ has two roots $\beta, \gamma$ in some quadratic extension $K$ of $\F_{17}$, and $\beta + \gamma = -\overline{5}$. Here the splitting field of $p(x)$ is $K \simeq \F_{17^2}$. Then the automorphism of Frobenius exchanges $\beta, \gamma$, and
$$v_p = \overline{5} ^p + \beta^p + \gamma^p = \overline{5} + \gamma + \beta = \overline{0}.$$

\bigskip
{\bf Example 4:} In the exceptional case $p = 23$, $\overline{D} = -\overline{23} = \overline{0}$, so $x^3 - x - 1$ has a multiple root : $\alpha = \overline{3}, \beta = \gamma =\overline{10}$. As in example 1,
$$v_p = \alpha^p + \beta^p + \gamma^p = \alpha + \beta + \gamma = \overline{3} + \overline{10} + \overline{10} = \overline{0}.$$

Exercise 4.4.27* ($p \mid u_p$, where $u_{n+1} = u_{n-1} + u_{n-2}, u_1 = 0, u_2 = 2, u_3 = 3$)

Answers

Comments

Exercise 4.4.27* ($p \mid u_p$, where $u_{n+1} = u_{n-1} + u_{n-2}, u_1 = 0, u_2 = 2, u_3 = 3$)

Answers

Comments

Add answer