Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Is this homework? If so, please add the "homework" tag to it. –  Álvaro Lozano-Robledo Dec 21 '11 at 2:03
1  
Hint: If $p=2q+1$, what are the possible orders of $5$ elements in $\mathbb{Z}/p$? –  David Speyer Dec 21 '11 at 3:40
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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