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