1
$\begingroup$

I'm attempting to show that $2$ is not a primitive root of primes of the form $p = 8k + 7$. I know that, to do so, I must show that $2$ has order less than $\phi(p)$ modulo $p$ (where $\phi$ denotes Euler's Totient function), however I've found myself a bit stuck.

I've begun by way of contradiction. If we assume $2$ to be a primitive root of $p$, then:

$$2^{\phi(8k+7)} \equiv 1 \pmod{8k + 7}$$

Since $p$ is prime, $\phi(p) = (8k+7)-1 = 8k+6$, hence:

$$2^{8k+6} \equiv 1 \pmod{8k+7}$$

...it isn't clear to me where to go from here.

$\endgroup$
2
  • $\begingroup$ Use Euler's criterion : $$a^{(p-1)/2}\equiv (\frac{a}{p})\mod p$$ for prime $p$ and $gcd(a,p)=1$ , hence a quadratic residue modulo $p$ cannot be a primitive root. $\endgroup$
    – Peter
    Dec 16, 2022 at 13:40
  • $\begingroup$ $2^3\equiv 1\pmod 7). $ $\endgroup$
    – DanielWainfleet
    Dec 16, 2022 at 14:03

1 Answer 1

Reset to default
1
$\begingroup$

Since $p\equiv -1 \bmod 8$, the Legendre symbol is equal to $1$, i.e., $$ \left( \frac{2}{p}\right)=1. $$ On the other hand, by Euler's criterion we have $$ 2^{(p-1)/2}\equiv\left(\dfrac2p\right)=1\bmod p, $$ hence $2$ is not a primive root modulo $p$.

Reference:

Solution to $x^2 = 2$ in field of $p$ element with $p \equiv \pm 1 \bmod 8$ ($p$ prime)

$\endgroup$
3
  • $\begingroup$ If $2$ is a square mod $p$, it obviously can’t be a generator mod $p$ (otherwise class mod $p$ is a square). As far as I can tell, the actual difficulty is to show that $2$ is indeed a square mod $p$. $\endgroup$
    – Aphelli
    Dec 16, 2022 at 14:23
  • $\begingroup$ @DietrichBurde Can't you just use the quadratic reciprocity ? $(2/p)=(-1)^{p^2-1/8}$ $\endgroup$
    – PNT
    Dec 17, 2022 at 9:15
  • $\begingroup$ @PNT Sure, but "Can't you just use" depends on what you just know. For me, it is not easier than what is shown in the linked post. $\endgroup$
    – Dietrich Burde
    Dec 17, 2022 at 10:03

You must log in to answer this question.

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