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 $p$ be an odd prime number of the form $p=2^m+1$.

I'd like your help proving that if $a$ is an integer such that $(\frac{a}{p})=-1$, then $a$ is a primitive root modulo $p$.

If $a$ is not primitive root modulo $p$ so $Ord_{p}(a)=t$, where $t<p-1=2^m$ and $t|2^m$ since $Ord_{p}(a)|p-1$ . I also know that there are no solutions to the congruence $x^2=a(p)$, How can I use it in order to reach a contradiction?

Thanks a lot.

share|improve this question
    
Are you allowed to assume the existence of a primitive root to begin with? My solution does not use this but the other one does. –  fretty Jun 8 '12 at 11:45
add comment

3 Answers

up vote 5 down vote accepted

Ok well we know by Fermat's little theorem that:

$a^{p-1} \equiv 1$ mod $p$

i.e.

$a^{2^m} \equiv 1$ mod $p$

Now $a$ must have order $2^i$ for some $0\leq i\leq m$ by Lagrange's theorem.

But the fact that the Legendre symbol is $-1$ coupled with Euler's criterion tells us that:

$a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right)$ mod $p$

i.e.

$a^{2^{m-1}} \equiv -1$ mod $p$

So that $a$ cannot have order $2^i$ for $0\leq i < m$ (otherwise this congruence would be false).

Thus $a$ has order $2^m$, and so is a primitive root.

share|improve this answer
add comment

Here is an easy counting argument.

The number of primitive roots of any prime $p$ is $\varphi(\varphi(p))$. Since $\varphi(p)=2^m$, and $\varphi(\varphi(p))=2^{m-1}$, there are $2^{m-1}$ primitive roots of $p$.

There are only $2^{m-1}$ quadratic non-residues of $p$. The primitive roots are a subset of the quadratic non-residues.

So every quadratic non-residue of $p$ is a primitive root of $p$.

share|improve this answer
add comment

Let $x$ be any primitive root and write $a \equiv x^k \pmod p$. Since $a$ is not a quadratic residuo modulo $p$, $k$ must be odd. The order of $a$ divides $p-1 = 2^m$, so $\operatorname{ord}(a) = 2^l$ for some $l \leq m$. We have $1 \equiv a^{2^l} \equiv x^{k2^l}$. The order of $x$ is $2^m$, so $2^m |k2^l$. But $k$ is odd, so $2^m | 2^l \pmod p$, hence $m=k$. From $\operatorname{ord}(a) = 2^m$ follows that $a$ is a primitive root modulo $p$.

share|improve this answer
    
Is the OP allowed to assume the existence of a primitive root? –  fretty Jun 8 '12 at 11:43
add comment

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.