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.

I came across this question while studying primitive roots. I know it has something to do with the fact that if the order of $a$ is $m$ then for every $k \in \mathbb{Z}$, the order of $a^k$ is $m/(m,k)$. The question is as follows:

Let $p$ be an odd prime. Prove that $a^2$ is never a primitive root $\pmod{p}$.

I would appreciate any help. Thank you.

share|improve this question
    
Okay. So, what would $m/\gcd(m,k)$ have to be for $a^2$ to be a primitive root? –  Hurkyl Mar 19 '12 at 1:13

4 Answers 4

If $(a,p)=1$, then $1\equiv a^{p-1}=(a^2)^\frac{p-1}{2}$ implies that $\text{ord}_p(a^2)\le\frac{p-1}{2}$.

share|improve this answer

Your hunch is correct: $\rm\:(m,k)>1\:\Rightarrow\:ord(a^k) = m/(m,k) < m = ord(a).\:$ Since $\rm\:a^k\:$ has smaller order than $\rm\:a,\:$ it doesn't have maximal order in $\rm\left<a\right>.\:$ Your problem is the special case $\rm\:2 = k\ |\ m$

share|improve this answer

The order of $a^2$ is no more than $\frac{p-1}{2}$ since $a^{p-1} \equiv 1\pmod{p}$ by Fermat's Little Theorem.

share|improve this answer

$g$ is a primitive root modulo $p$ if and only if the order of $g$ modulo $p$ is $p-1$.

If the order of $a$ is not $p-1$, then $a^2$ has order less than or equal to the order of $a$, hence is not a primitive root.

If the order of $a$ is $p-1$ then what is the order of $a^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.