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: enter image description here 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.

  • 8
    $\begingroup$ 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. $\endgroup$ Mar 23, 2021 at 5:56
  • 1
    $\begingroup$ @StevenStadnicki Why are you giving a full answer in the comment section? $\endgroup$
    – Arthur
    Mar 23, 2021 at 5:57
  • 2
    $\begingroup$ @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). $\endgroup$ Mar 23, 2021 at 5:58
  • $\begingroup$ 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? $\endgroup$ Mar 23, 2021 at 7:39
  • $\begingroup$ 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. $\endgroup$
    – kabenyuk
    Mar 23, 2021 at 9:58

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

  • 1
    $\begingroup$ 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. $\endgroup$ Mar 23, 2021 at 11:34
  • $\begingroup$ 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. $\endgroup$
    – Servaes
    Mar 23, 2021 at 12:37
  • $\begingroup$ 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. $\endgroup$
    – Servaes
    Mar 25, 2021 at 11:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .