Exercise 4.4.26* (If $p$ is a prime then $\lfloor (2+\sqrt{5})^p\rfloor \equiv 2^{p+1} \pmod {20p}$)

Proof. Consider the sequence ${(V_n)}_{n\in \mathbb{N}}$ defined by

Let $\lambda =2+\sqrt{5},\mu =2-\sqrt{5}$, so that $V_n={\lambda }^n+{\mu }^n$. Then $\lambda +\mu =4,\mathit{\lambda \mu }=-1$, thus $\lambda ,\mu$ are the roots of the polynomial $x^2-4x-1$.

By Theorem 4.10, ${(V_n)}_{n\in \mathbb{N}}$ is characterized by

Since $-1<2-\sqrt{5}<0$, and $p$ is odd, then $-1<{(2-\sqrt{5})}^p<0$, thus

Therefore, if $p$ is an odd prime,

It remains to show that $V_p\equiv 2^{p+1}(\mathit{mod}20p)$.

If $p=5$, then $V_5=1364\equiv 64(\mathit{mod}100)$, so $V_p\equiv 2^{p+1}(\mathit{mod}20p)$ is true for $p=5$. In the following, we will suppose that $p\ne 2,p\ne 5$, so that $p\wedge 20=1$.

We look at the congruences modulo $4,5,20$ and $p$.

• Modulo 4.

  By (1), $V_{n+2}\equiv V_n(\mathit{mod}4)$, where $V_1\equiv 0(\mathit{mod}4)$, thus $V_n\equiv 0(\mathit{mod}4)$ for all odd integers $n$, so

  $$\begin{array}{lll}\hfill V_p\equiv 0\equiv 2^{p+1}(\mathit{mod}4).& & \hfill \text{(3)}\end{array}$$

• Modulo 5.

  We note that $2^2\equiv 4\cdot 2+1(\mathit{mod}5)$, thus $2^{n+3}\equiv 4\cdot 2^{n+2}+2^{n+1}(\mathit{mod}5)$ for all $n\in \mathbb{N}$. First $V_0=2\equiv 2^1,V_1=4\equiv 2^2(\mathit{mod}5)$. If we suppose that for some $n\in \mathbb{N}$, $V_n\equiv 2^{n+1}$ and $V_{n+1}\equiv 2^{n+2}(\mathit{mod}5)$, then $V_{n+2}=4V_{n+1}+V_n\equiv 4\cdot 2^{n+2}+2^{n+1}\equiv 2^{n+3}(\mathit{mod}5)$. The induction is done, which proves that for all $n\in \mathbb{N}$, $V_n\equiv 2^{n+1}(\mathit{mod}5)$. In particlular

  $$\begin{array}{lll}\hfill V_p\equiv 2^{p+1}(\mathit{mod}5).& & \hfill \text{(4)}\end{array}$$

• Modulo 20.

  Since $4\wedge 5=1$, we conclude from (3) and (4) that

  $$\begin{array}{lll}\hfill V_p\equiv 2^{p+1}(\mathit{mod}20).& & \hfill \text{(5)}\end{array}$$

• Modulo p.

  As in Problems 19, 20, 21, consider the sequence ${(v_n)}_{n\in \mathbb{N}}\in {𝔽}_p^{\mathbb{N}}$ defined by

  $$v_n=\overline{V_n}(n\in \mathbb{N}),$$

  where $\bar{a}$ denotes the class of $a\in \mathbb{Z}$ modulo $p$. Then, for all $n\in \mathbb{N}$,

  $$v_{n+2}=4v_{n+1}+v_n,v_0=\bar{2},v_1=\bar{4}.$$

  The discriminant of the polynomial $\bar{p}(x)=x^2-\bar{4}x-1$ is $\bar{D}=\overline{20}$. Moreover, using the law of quadratic reciprocity,

  $$\left(\frac{D}{p}\right)=\left(\frac{20}{p}\right)=\left(\frac{4}{p}\right)\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right).$$

  So $\bar{D}$ is a square in ${𝔽}_p$ if and only if $\left(\frac{p}{5}\right)=1$.

  • If $\left(\frac{p}{5}\right)=1$, then $\bar{p}(x)$ has two roots $\alpha ,\beta$ in ${𝔽}_p$. Since $5\nmid p$ and $2\nmid p$, then $\bar{D}\ne 0$, thus $\alpha \ne \beta$.

    By induction, we obtain $v_n={\alpha }^n+{\beta }^n(n\in \mathbb{N}),$ thus

    $$v_p={\alpha }^p+{\beta }^p.$$

    By Fermat’s theorem, ${\alpha }^p=\alpha ,{\beta }^p=\beta ,{\bar{2}}^p=\bar{2}$, thus $v_p=\alpha +\beta =\bar{4}={\bar{2}}^{p+1}$, so

    $$V_p\equiv 2^{p+1}(\mathit{mod}p).$$

  • If $\left(\frac{p}{5}\right)=-1$, then $\bar{p}(x)$ is irreducible over ${𝔽}_p$. Then $\bar{p}(x)$ has two roots $\alpha ,\beta$ in $K$, where $K={𝔽}_p(x)∕(\bar{p}(x))$ is a quadratic extension of ${𝔽}_p$.

    We proved in Problem 20 (see equality (8)) that

    $${\alpha }^p=\beta ,{\beta }^p=\alpha .$$

    Therefore

    $$v_p={\alpha }^p+{\beta }^p=\beta +\alpha =\bar{4}.$$

    Since ${\bar{2}}^p=\bar{2}$, we obtain $v_p=2^{p+1}$, so

    $$V_p\equiv 2^{p+1}(\mathit{mod}p).$$

  Since $p\ne 5$, there is no other case, and in both cases,

  $$\begin{array}{lll}\hfill V_p\equiv 2^{p+1}(\mathit{mod}p).& & \hfill \text{(6)}\end{array}$$

  Since $p\wedge 20=1$, (5) and (6) give

  $$\begin{array}{lll}\hfill V_p\equiv 2^{p+1}(\mathit{mod}20p).& & \hfill \text{(7)}\end{array}$$

  We know that this is true also for $p=5$.

  In conclusion, for all odd prime $p$,

  $$\begin{array}{lll}\hfill \lfloor {(2+\sqrt{5})}^p\rfloor \equiv 2^{p+1}(\mathit{mod}20p).& & \hfill \end{array}$$