# Number theory Question 2

• Jan 14th 2009, 02:38 AM
peteryellow
Number theory Question 2
Show that if p is not a Fermat prime, then there is a such that
$\displaystyle \left(\frac {a}{p}\right)=-1$

and [a]_p is not a generator of $\displaystyle (\mathbb Z/p)^*$.

Here $\displaystyle \left(\frac {2}{p}\right)=-1$
is legendre symbol.
• Jan 14th 2009, 03:14 AM
PaulRS
Quote:

Originally Posted by peteryellow
Show that if p is not a Fermat prime, then there is a such that
$\displaystyle \left(\frac {a}{p}\right)=-1$

and [a]_p is not a generator of $\displaystyle (\mathbb Z/p)^*$.

Recall the fact that all primes of the form $\displaystyle 2^n+1$ -save from the number 2- are fermat primes -and conversly- (* that is easy to show, if you have not seen it, ask)

Okay, first remember that there are $\displaystyle \phi \left( {\phi \left( p \right)} \right) = \phi \left( {p - 1} \right)$ primitive roots ( or generators) in $\displaystyle (\mathbb Z/p)^*$

And there are $\displaystyle \tfrac{{p - 1}} {2}$ non-quadratic residues.

So we'd like to show that $\displaystyle \tfrac{{p - 1}} {2} > \phi \left( {p - 1} \right)$ occurs in our case. -remember that the set of generators is included in the set of non-quadratic residues, see here-

We can write: $\displaystyle p - 1 = 2^\alpha \cdot m$ with $\displaystyle \alpha;m \in \mathbb{Z}^ +$ such that $\displaystyle \left( {m,2} \right) = 1$ - since p>2, the case p=2 is trivial-

Then: $\displaystyle \phi \left( {p - 1} \right) = \phi \left( {2^\alpha } \right) \cdot \phi \left( m \right) = 2^{\alpha - 1} \cdot \phi \left( m \right) \leqslant 2^{\alpha - 1} \cdot m = \tfrac{{p - 1}} {2}$ equality occurs iff $\displaystyle m = 1$

Hence if $\displaystyle p$ is not of the form $\displaystyle 2^{\alpha}+1$ (that is $\displaystyle m>1$) there's always a non-quadratic residue that is not a generator.

But, if p is of the form $\displaystyle 2^{\alpha}+1$, then all non-quadratic residues are also generators.