Exercise 4.4.20* ($U_p \equiv (D/p) \pmod p$)

Proof. By the proof of Theorem 4.12, for all $n\in \mathbb{N}$,

In particular, for $n=p$,

By Fermat’s theorem, $2^{p-1}\equiv 1(\mathit{mod}p)$. Moreover $\left(\genfrac{}{}{0.0pt}{}{p}{k}\right)\equiv 0(\mathit{mod}p)$ if $1\le k\le p-1$, so that all terms except the last are congruent to $0$ modulo $p$. This gives

□

Proof. As in the second solution of Problem 19, consider the sequences ${(u_n)}_{n\in \mathbb{N}},{(v_n)}_{n\in \mathbb{N}}$ defined for all $n$ by $u_n=\overline{U_n},v_n=\overline{V_n}\in {𝔽}_p$, so that

• If $\left(\frac{D}{p}\right)=1$, then $D$ has a square root $\delta \ne 0$ in ${𝔽}_p$, and the polynomial $p(x)=x^2-\mathit{ax}-b$ has two distinct roots $\alpha \in {𝔽}_p$ and $\beta \in {𝔽}_p$, so that

  $$\begin{array}{lll}\hfill u_n& =\frac{{\alpha }^n-{\beta }^n}{\alpha -\beta },& \hfill \text{(2)}\\ \hfill v_n& ={\alpha }^n+{\beta }^n.& \hfill \text{(3)}\end{array}$$

  In particular

  $$u_p=\frac{{\alpha }^p-{\beta }^p}{\alpha -\beta },$$

  where ${\alpha }^p=\alpha ,{\beta }^p=\beta$ by Fermat’s theorem, thus $u_p=\bar{1}$. This gives

  $$U_p\equiv 1\equiv \left(\frac{D}{p}\right)(\mathit{mod}p).$$

• If $\left(\frac{D}{p}\right)=-1$, then $\bar{D}$ has a square root $\delta =\sqrt{\bar{D}}$ in some quadratic extension $K$ of ${𝔽}_p$, for instance $K={𝔽}_p[x]∕(x^2-\bar{a}x-\bar{b})$, where $x^2-\bar{a}x-\bar{b}$ is irreducible over ${𝔽}_p$. If $\alpha$ and $\beta$ are the distinct roots of $p(x)$ in $K$, then $K={𝔽}_p(\alpha )={𝔽}_p(\delta )$, and $K$ is a field with $p^2$ elements. Then by induction,

  $$\begin{array}{lll}\hfill u_n& =\frac{{\alpha }^n-{\beta }^n}{\alpha -\beta },& \hfill \text{(4)}\\ \hfill v_n& ={\alpha }^n+{\beta }^n.& \hfill \text{(5)}\end{array}$$

  remain true. In particular

  $$\begin{array}{lll}\hfill u_p=\frac{{\alpha }^p-{\beta }^p}{\alpha -\beta }.& & \hfill \text{(6)}\end{array}$$

  Consider the map

  $$\sigma \{\begin{array}{ccc}\hfill K\hfill & \hfill \to \hfill & K\hfill \\ \hfill x\hfill & \hfill \mapsto \hfill & x^p.\hfill \end{array}$$

  Since the characteristic of $K$ is $p$, $\sigma$ is an automorphism of the field $K$, named Frobenius automorphism, and for all $\gamma \in K$, $\sigma (a)=a$ if $\gamma \in {𝔽}_p$.

  Moreover, since ${\gamma }^{p^2}=\gamma$ for all $\gamma \in K$, $(\sigma \circ \sigma )(\gamma )=\sigma ({\gamma }^p)={\gamma }^{p^2}=\gamma$, so $\sigma \circ \sigma =1_K$.

  The remarkable fact is that $\sigma$ exchanges $\alpha$ and $\beta$:

  $$\begin{array}{lll}\hfill \sigma (\alpha )=\beta ,\sigma (\beta )=\alpha .& & \hfill \text{(7)}\end{array}$$

  Indeed, since ${\alpha }^2-\bar{a}\alpha -\bar{b}=0$, thus $\sigma {(\alpha )}^2-\bar{a}\sigma (\alpha )-\bar{b}=0$, thus $\sigma (\alpha )$ is a root of $p(x)=x^2-\bar{a}x-\bar{b}$, so $\sigma (\alpha )\in \{\alpha ,\beta \}$. But the only elements of $K$ fixed by $\sigma$ are the elements of ${𝔽}_p$, otherwise the polynomial $x^p-x$, of degree $p$, would have more than $p$ roots. Since $\alpha \notin {𝔽}_p$, $\sigma (\alpha )\ne \alpha$, so $\sigma (\alpha )=\beta$, and $\sigma (\beta )=(\sigma \circ \sigma )(\alpha )=\alpha$, so (7) is proven.

  This gives by definition of $\sigma$,

  $$\begin{array}{lll}\hfill {\alpha }^p=\beta ,{\beta }^p=\alpha .& & \hfill \text{(8)}\end{array}$$

  By (6),

  $$\begin{array}{llll}\hfill u_p& =\frac{\beta -\alpha }{\alpha -\beta }=-\bar{1}.& \hfill & \end{array}$$

  Thus

  $$U_p\equiv -1\equiv \left(\frac{D}{p}\right)(\mathit{mod}p).$$

• If $\left(\frac{D}{p}\right)=0$, then $p\mid D$. By induction, using (1), where $\bar{D}={\bar{a}}^2+\bar{4}\bar{b}=0$, we obtain for all $n\in {\mathbb{N}}^{\text{∗}}$,

  $$u_n=n{\alpha }^{n-1},(u_0=0)$$

  where $\alpha \in {𝔽}_p$ is the unique root of $x^2-\bar{a}x-\bar{b}$, that is $\alpha ={\bar{2}}^{-1}\bar{a}$.

  In particular

  $$u_p=p{\alpha }^{p-1}=0.$$

  This gives

  $$U_p\equiv 0\equiv \left(\frac{D}{p}\right)(\mathit{mod}p).$$

In all cases

□