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