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

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.

• There are $p^2-1$ pairs $\langle a,b\rangle$ with at least one of $a, b\neq 0\pmod p$; since that's the order of the group, the order of a subgroup (in this case, the subgroup generated by $1+\sqrt{7}$) must divide it. Mar 23, 2021 at 5:56
• @StevenStadnicki Why are you giving a full answer in the comment section? Mar 23, 2021 at 5:57
• @Arthur In this case, because (a) it fits in a comment (and I don't really feel like that's enough meat for a full answer) and (b) it doesn't entirely answer the question (in particular, it doesn't provide the divisor). Mar 23, 2021 at 5:58
• That makes sense, thank you. My algebra is definitely rustier than I thought. So the generator $1 + \sqrt 7$ makes a subgroup of $G$ and Lagrange's Theorem states the order of a subgroup divides $|G|$. The order of the original group $G$ is $p^2 - 1$ because of your counting argument. Is my understanding correct? Mar 23, 2021 at 7:39
• If the number 7 is a quadratic residue modulo p, then the order m of 1+\sqrt7 divides p-1, otherwise m divides the number p^2-1.For instance, if p=19, 29, 31, 37 then m=9, 14, 15, 9, respectively. Mar 23, 2021 at 9:58

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$$.

• I haven't had the time to digest all of this yet but just wanted to accept this answer now as a lot of thoughtful pointers and already goes into way more detail than I was hoping for. Cheers! If I need to, I'll comment back tomorrow once I've had a chance to dive deeper into all this. Mar 23, 2021 at 11:34
• Thanks! Feel free to ask for more details when you need them. I do believe there is no easy answer to your problem, so it's likely that this answer will stay a collection of half-finished or half-effective ideas. Mar 23, 2021 at 12:37
• I've removed a section that was plainly false; I had overlooked a factor $7^k$ in the binomial expansions. There is nothing useful in this approach, as far as I can tell. Mar 25, 2021 at 11:35