Exercise 4.4.19* (If $(D/p) = 1$, then $U_{p+1} \equiv a \pmod p$)

Question

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Show that if $p$ is an odd prime and $\legendre{D}{p} = 1$, then $U_{p+1} \equiv a \pmod p$.

Richard Ganaye · Accepted Answer

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

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

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

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

{\bf First proof.}
\begin{proof} 
In the proof of Theorem 4.12, , we obtained for all odd prime numbers $p$,
$$2U_{p+1} \equiv \binom{p+1}{1} a^p + \binom{p+1}{p} a D^{(p-1)/2} \equiv a (1+D^{(p-1)/2}) \pmod p.$$
Using Euler's criterion, this gives
$$2 U_{p+1} \equiv a \left( 1 + \legendre{D}{p}ight).$$
If $\legendre{D}{p} = 1$, then $2 U_{p+1} \equiv 2a \pmod p$, where $p$ is odd, thus
$$U_{p+1} \equiv a \pmod p.$$
\end{proof}

{\bf Second proof} (personal proof).
\begin{proof}
Here we write $\overline{a}$ the class of $a \in \Z$ in $\Z/p\Z$, and $\F_p$ the field with $p$ elements. Moreover, we write $u_k, v_k$ in $\F_p$ the classes 
$$u _k = \overline{U_k},\qquad  v_k = \overline{V_k}.$$
By definition of the sequences $(U_n)_{n\in \N}, (V_n)_{n\in \N}$ (see 4.10), for all $n \in \N$,
\begin{align}
\left\{
\begin{array}{ll}
U_{n+2} &= a U_{n+1} + b U_{n},\
V_{n+2} & = a V_{n+1}+ b V_n,
\end{array}
ight.
\qquad
\left\{
\begin{array}{l}
U_{0} = 0,\ U_1 = 1,\
V_{0} = 2,\ V_1 = a.
\end{array}
ight.
\end{align}
Reducing modulo $p$, this gives
\begin{align}
\left\{
\begin{array}{ll}
u_{n+2} &= \overline{a} u_{n+1} +\overline{b} u_n,\
v_{n+2} &= \overline{a} v_{n+1} +\overline{b} v_n,
\end{array}
ight.
\qquad
\left\{
\begin{array}{l}
u_{0} = \overline{0},\ u_1 = \overline{1},\
v_{0} = \overline{2},\ v_1 = \overline{a}.
\end{array}
ight.
\end{align}
Here $\legendre{D}{p} = 1$, thus there exists $\delta \in \F_p^*$ such that $\delta^2 = \overline{D}$, written $\delta = \sqrt{\overline{D}}$, so there are two distinct roots $\alpha, \beta \in \F_p$ of $x^2 -\overline{a}x -\overline{b} \in \F_p[x]$ (given by $\alpha =\overline{2}^{-1} (\overline{a}+ \delta), \beta = \overline{2}^{-1}(\overline{a}- \delta)$). Then $\alpha + \beta = \overline{a}$.

By induction, using (2), we obtain for all $n \in \N$,
\begin{align}
u_n &= \frac{\alpha^n - \beta^n}{\alpha - \beta},\
v_n &= \alpha^n + \beta^n.
\end{align}
In particular,
\begin{align}
u_{p+1} =  \frac{\alpha^{p+1} - \beta^{p+1}}{\alpha - \beta}.
\end{align}
By Fermat's theorem, $\alpha^p = \alpha$ and $\beta^p = \beta$, thus 
\begin{align}
u_{p+1} &=  \frac{\alpha^{2} - \beta^{2}}{\alpha - \beta}\
&=\alpha + \beta\
&= \overline{a}.
\end{align}
In conclusion, if $\legendre{D}{p} = 1$, where $p$ is an odd prime, then
$$U_{p+1} \equiv a \pmod p.$$
\end{proof}

Exercise 4.4.19* (If $(D/p) = 1$, then $U_{p+1} \equiv a \pmod p$)

Answers

Comments

Exercise 4.4.19* (If $(D/p) = 1$, then $U_{p+1} \equiv a \pmod p$)

Answers

Comments

Add answer