Exercise 4.4.21* (If $(D/p) = 1$, then $bU_{p-1} \equiv 0 \pmod p$)

Question

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
Show that if $p$ is odd, $\legendre{D}{p} = 1$, then $bU_{p-1} \equiv 0 \pmod p$.

Richard Ganaye · Accepted Answer

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

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

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

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

\begin{proof} 
If $p \mid b$, then $bU_{p-1} \equiv 0 \pmod p$. Now we suppose that $p
mid b$, and we prove that $U_{p-1} \equiv 0 \pmod p$.

As in the second solution of Problem 19, consider the sequences $(u_n)_{n\in \N}, (v_n)_{n\in \N}$ defined for all $n$ by $u_n = \overline{U_n},\ v_n = \overline{V_n} \in \F_p$, so that
\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]$.

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}
With our hypothesis $p 
mid b$, we know that $\overline{b} 
e 0$, thus $\alpha 
e 0$ and $\beta 
e 0$. Then by Fermat's theorem $\alpha^{p-1} = 1$ and $\beta^{p-1} = 1$, so (1) gives 
$u_{p-1} = 0$.
Therefore
$$U_{p-1} \equiv 0 \pmod p.$$

In conclusion, if $p$ is odd and $\legendre{D}{p} = 1$, then 
$$b U_{p-1} \equiv 0 \pmod p.$$
\end{proof}

Note 1 : It will be useful to note that if $\legendre{D}{p} = 1$, then $v_{p-1} = \alpha^{p-1} + \beta^{p-1} = \overline{2}$, thus
\begin{align}
V_{p-1} \equiv 2 \pmod p.
\end{align}

Note 2: The case $\legendre{D}{p} = -1$ will also be useful in Problem 22.

If $\legendre{D}{p} = -1$, then as in Problem 20, $\overline{D}$ has a square root $\delta$ in some quadratic extension $K$ of $\F_p$ with $p^2$ elements. Let $\alpha$ and $\beta$ be the distinct roots of $p(x)$ in $K$. By induction, 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}
Consider the map
$$\sigma 
\left\{
\begin{array}{ccl}
K & 	o &K\
x & \mapsto & x^p.
\end{array}
ight.
$$
We have proved in Problem 20 that $\sigma$ is an automorphism of $K$, and that $\sigma$ is an involution. Moreover $\alpha^p = \beta$ and $\beta^p = \alpha$, thus
\begin{align*}
u_{p-1}&=  \frac{\alpha^{p-1}- \beta^{p-1}}{\alpha - \beta}\
&= \frac{\frac{\beta}{\alpha} - \frac{\alpha}{\beta}}{\alpha - \beta}\
&=\frac{\beta^2 - \alpha^2}{\alpha \beta (\alpha - \beta)}\
&= - \frac{\alpha + \beta}{\alpha \beta}\
&= \frac{\overline{a}}{\overline{b}}
\end{align*}
This shows that
\begin{align}
U_{p-1} \equiv a \pmod p.
\end{align}

Exercise 4.4.21* (If $(D/p) = 1$, then $bU_{p-1} \equiv 0 \pmod p$)

Answers

Comments

Exercise 4.4.21* (If $(D/p) = 1$, then $bU_{p-1} \equiv 0 \pmod p$)

Answers

Comments

Add answer