3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user996522 Dec 21 '11 at 16:31
  • $\begingroup$ 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). $\endgroup$ – Álvaro Lozano-Robledo Dec 21 '11 at 16:42
  • $\begingroup$ lol, oops, brain fart. Thank you very much. $\endgroup$ – user996522 Dec 21 '11 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.