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

-
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

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

-

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

-

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$

-

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

-