# Show that $2$ is not a primitive root of $8k + 7$

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.

• 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. Dec 16, 2022 at 13:40
• $2^3\equiv 1\pmod 7).$ Dec 16, 2022 at 14:03

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)

• 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$. Dec 16, 2022 at 14:23
• @DietrichBurde Can't you just use the quadratic reciprocity ? $(2/p)=(-1)^{p^2-1/8}$
– PNT
Dec 17, 2022 at 9:15
• @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. Dec 17, 2022 at 10:03