# If $p - 1 = 2q$, and $5$ is a primitive root $\bmod q$, then $5$ is a primitive root $\bmod p$

Let $p$ and $q$ be odd primes. If $p - 1 = 2q$, and $5$ is a primitive root $\bmod q$, then $5$ is a primitive root $\bmod p$.

Thanks to Álvaro Lozano-Robledo, here is what i have; valid?

If:

(A) p and q are odd primes; and
(B) p - 1 = 2q <-> p = 2q + 1 ; and
(C) 5 is a primitive root mod q.

then:

(1) There exist phi(p-1) = phi(2q) = (1*(q-1)) = (q-1) primitive roots mod p
(2) There exist (p-1)/2 = q quadratic non-residues mod p
(3) Since ((odd*2) + 1) is always congruent to 3 mod 4; -1 mod p is a quadratic non-residue (Law Of Quadratic Reciprocity)
(4) (-1 mod p) i.e. (p-1 mod p) cannot be a primitive root because ((p-1)^2 mod p) = ((p^2) - 2p + 1 mod p) = 1 mod p. p is also >= 7
(5) From (1),(2),(3),(4) Every Quadratic-NonResidue other than p-1 is a primitive root.
(6) Legendre(5/q) = -1, Legendre(q/5) = -1, i.e. q^(4/2) is congruent to (4 mod 5); q is congruent to (+ or -) (2 mod 5)
(7) 2q is congruent to (4 or 1) mod 5
(8) (substitute for 2q, p-1) p is congruent to (0 or 2) mod 5
(9) p cannot be 5 or any of its multiples, because its a prime and must be greater than 6.
(10) p must be congruent to 2 mod 5
(11) p^(5-1 /2) mod 5 is -1,
(12) Legendre(p/5) = -1, Legendre(5/p) = -1
(13) 5 is a quadratic non-residue mod p
(14) 5 is a primitive root mod p fom (13),(1),(2),(3)

cheers arun

• Hint: If $p=2q+1$, what are the possible orders of $5$ elements in $\mathbb{Z}/p$? – David E Speyer Dec 21 '11 at 3:40

## 1 Answer

Here is one way to solve this. Let $p$ and $q$ be odd primes, with $p=2q+1$. Prove the following steps:

(1) Every primitive root is a quadratic non-residue.

(2) There are $q$ quadratic non-residues modulo $p$, and $q-1$ primitive roots mod $p$.

(3) $p\equiv 3\bmod 4$. Thus, $-1$ is a quadratic non-residue mod $p$.

(4) Hence, every quadratic non-residue modulo $p$, except $-1$, is a primitive root.

(5) By assumption, $5$ is a primitive root modulo $q$. Thus, $5$ is a quadratic non-residue modulo $q$.

(6) By quadratic reciprocity, $q\equiv \pm 2\bmod 5$. It follows that $p\equiv 0$ or $2\bmod 5$. But $q$ is odd, so $p\neq 5$, hence $p\equiv 2\bmod 5$. It follows, again by quadratic reciprocity that $5$ is a quadratic non-residue modulo $p$.

(7) By (4) and (6), we conclude that $5$ is a primitive root modulo $p$.

• Thank you very much, i get everything up to: By quadratic reciprocity, q≡±2mod5. It follows that p≡0 or 2mod5. But why if q is odd, p cannot be congruent to 0 mod p. For example let q = 7, then p = 15. Which is congruent to 0 mod 5. – user996522 Dec 21 '11 at 16:31
• But $15$ is not a prime! The only prime $p\equiv 0 \bmod 5$ is $p=5=2\cdot 2 +1$ (in which case $q=2$ is even). – Álvaro Lozano-Robledo Dec 21 '11 at 16:42
• lol, oops, brain fart. Thank you very much. – user996522 Dec 21 '11 at 16:47