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 $a$ be a primitive root mod the odd prime p. Prove that $a^{(p-1)/2} $$\equiv$-1 (modp). Deduce that if $a, b$ are primitive roots modp, then $a\times b$ is NOT a primitive root mod p.

Here we define that, $a$ is a primitive root of $n$ if $(a,n)=$1 and $a$ has order exactly $\phi(n)$ (where the order refers to the least such $k$ where $a^k$ $\equiv$ 1 (modn), $k \geq 1$) (and $\phi$ denotes Euler's totient function.)

I have started by noting that $a^{(p-1)/2}$ $\equiv \pm 1 $ mod $p$ by Fermats Little Theorem and equating $y=a^{(p-1)/2}$

Also Eulers criterion tells us that $(\frac{a}{p})$ is congruent to $a^{(p-1)/2}$ mod p

Also, Legendre tells us that $(\frac{a}{p})$ =-1 if $a$ is a quadratic non-residue of $p$

So putting this together, am I to show that $a$ being a primitive root mod p implies that it is a quadratic non-residue mod p?

Can't quite get my head round this problem. Help appreciated, thanks in advance.

share|improve this question
    
I believe you mean $\frac{p-1} {2}$ as opposed to $p - \frac{1}{2}$? –  Calvin Lin May 16 '13 at 16:36
    
Yes, that was an oversight, thankyou –  Olivia77989 May 16 '13 at 16:48

4 Answers 4

The Legendre symbol is unimportant here. $a^{(p-1)/2}\equiv \pm 1$, and it's not $1$ since $a$ is a primitive root, so it's $-1$.

share|improve this answer

How to derive this expression $ r ^{ (p-1)/2} \equiv -1 \pmod p$ for primitive root of an odd prime $p$. Gives an answer for your first part. For the second part use the facts of first one i.e:

$a^{\frac{p-1}{2}} \equiv -1(\mod p) $ and $b^{\frac{p-1}{2}} \equiv -1(\mod p)$

$(ab)^{\frac{p-1}{2}} \equiv1(\mod p) \implies ab$ $\text{is not the Primitive root of $p$}$

share|improve this answer

Using Fermat's Little Theorem, $$a^{p-1}\equiv1\pmod p$$

$\implies p$ divides $(a^{p-1}-1)\implies p$ divides $(a^{\frac{p-1}2}-1)(a^{\frac{p-1}2}+1)$

If $a$ is a primitive root, $ord_pa=p-1\implies a^r\not\equiv 1\pmod p$ for $r<p-1$

$\implies p$ does not divide $a^{\frac{p-1}2}-1$

$\implies p$ divides $a^{\frac{p-1}2}+1$

If $a,b$ are primitive roots $a^{\frac{p-1}2}\equiv-1\pmod p$ and $b^{\frac{p-1}2}\equiv-1\pmod p$

$\implies (ab)^{\frac{p-1}2}\equiv(-1)^2\pmod p\equiv1$

So, $ord_p(ab)$ divides $\frac{p-1}2<p-1\implies ord_p(ab)<p-1$

share|improve this answer

Hint 1: For odd primes $p\geq 5$, $\frac{p-1}{2}$ is an integer $\geq 2$. If $a^{\frac{p-1}{2} } = 1 $, then $a$ is not a primitive root by definition.
Check $p=3$ and see if the statement holds.

Hint 2: $ab^{\frac{p-1}{2} } = a^{\frac{p-1}{2} } \times b^{\frac{p-1}{2} } $.

share|improve this answer

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.