Why the order of elements of my group $\mathbb{Z}\left[\sqrt 7\right]$ under multiplication modulo prime $p$ often divide $p^2-1$

Question

Consider the group $G$ with elements of the form $a + b \sqrt 7$ ($a, b \in \mathbb{Z}$) under multiplication mod $p$ where $p$ is prime.

I noticed the order of $1 + \sqrt 7$ in my group is usually of the form $\frac{p^2 - 1}{d}$ where $d$ is some positive integer divisor.

For example, operating under mod $p := 5$: $5^2 - 1 = 24$ and $\mathrm{ord}\left(1 + \sqrt 7\right) = 12 = 24/2$.

I plotted the order of $1 + \sqrt 7$ under different values of $p$ and here are the results: You can easily see the patterns emerge (i.e. broken parabolas in the plot):

• $p^2 - 1$
• $(p^2 - 1)/2$
• etc.

Why does this happen? Is there a reliable way to predict when this happens and even what the divisor would be? This could potentially provide an efficient way to calculate the order of my group element.

Answer 1

Let $p$ be a prime number and $G_p$ the group you are considering. For $G_p$ to be a group in the first place, every element of the form $a+b\sqrt{7}$ must be invertible mod $p$. In particular you cannot have $a,b\equiv0\pmod{p}$.

Let's make the situation a bit more precise by working over the finite field $\Bbb{F}_p$ of $p$ elements. Adjoining $\sqrt{7}$, a root of $X^2-7\in\Bbb{F}_p[X]$, then yields a field extension $\Bbb{F}_p\subset\Bbb{F}_p[\sqrt{7}]$, and its degree is either $1$ or $2$. The degree is $1$ if and only if $X^2-7\in\Bbb{F}_p[X]$ has a root in $\Bbb{F}_p$, or equivalently, if $7$ is a quadratic residue mod $p$. By quadratic reciprocity it follows that the degree is $1$ if and only if $$p\equiv1,2,3,7,9,25,27\pmod{28}.$$ In this case $\Bbb{F}_p[\sqrt{7}]=\Bbb{F}_p$ with unit group $\Bbb{F}_p^{\times}=\Bbb{F}_p-\{0\}$, so the invertible elements form a group of order $p-1$. Otherwise $\Bbb{F}_p[\sqrt{7}]\cong\Bbb{F}_{p^2}$, and the invertible elements form a group of order $p^2-1$. Note that in either case this group is cyclic; see this question for a proof.

As far as I can tell there is no quick method to determine the order of an element. A closely related problem is finding a primitive root mod $p$, which is hard in general. But here are a few simple observations:

1. If $7$ is a quadratic residue mod $p$, then the order of $a+b\sqrt{7}$ divides $p-1$.
2. If $b\equiv0\pmod{p}$ then $a+b\sqrt{7}\in\Bbb{F}_p$ and so the order divides $p-1$.
3. If $7$ is not a quadratic residue and $b\not\equiv0\pmod{p}$, then the order of $a+b\sqrt{7}$ does not divide $p-1$. Moreover $(a+b\sqrt{7})^{p+1}\in\Bbb{F}_p^{\times}$, so you can first find a divisor $d$ of $p+1$ such that $(a+b\sqrt{7})^d\in\Bbb{F}_p^{\times}$, and then use point $1$. Note that $\gcd(p-1,p+1)=2$ so you may need to take out a factor $2$.

Another approach might be to consider that $1+\sqrt{7}$ is a root of $X^2-2X-6$. Then for each prime number $p$, you want to find the minimal positive integer $d$ such that $X^2-2X-6$ divides $X^d-1$, or better yet the $d$-th cyclotomic polynomial $\Phi_d$, as polynomials in $\Bbb{F}_p[X]$. The ideas above already give some restrictions on $d$.