I wonder why 4 is not a primitive root for any prime p ?
I've been trying to find an answer with no success so far. Any suggestion would be very helpful, thanks in advance !
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
As $2^2=4,$
$4^{\left(\frac{p-1}2\right)}=2^{p-1}\equiv1\pmod p$ for any prime $p>2$ using Fermat's Little Theorem
So, the ord$_p4\le \frac{p-1}2<p-1$
answered Apr 15, 2013 at 14:38
-
$\begingroup$ Observe that this will hold for any number $a^n$ with $n>1$ and any modulo $m$ which has a primitive root such that $(a,m)=1$ $\endgroup$ Apr 15, 2013 at 15:10
$\begingroup$
$\endgroup$
For any relevant $p$, the order of 2 will be larger than the order of $4 = 2\cdot 2$.
$\begingroup$
$\endgroup$
Hint $\ $ If $\rm\ 1 < d\mid p\!-\!1\ $ then $\rm\:mod\ p\!:\ a\not\equiv 0 \:\Rightarrow\: (a^d)^{(p-1)/d}\! \equiv a^{p-1}\! \equiv 1,\:$ therefore $\rm\:a^d$ has order at most $\rm\:(p-1)/d < p-1.\:$ Thus $\rm\:d$'th powers are not primitive roots. Your case is $\rm\:d = 2.$
$\begingroup$
$\endgroup$
This follows from Bhattacharjee's answer.
If you have $r$ a primitive root of $p$. GCD$(r,p)=1$
$r^{2\cdot (\frac{p-1}{2})} \equiv r^{p-1}\equiv -1 \mod p \implies r^2$ can't be primitive root if $r$ is a primitive root.
