# Thread: Number theory Question 2

1. ## Number theory Question 2

Show that if p is not a Fermat prime, then there is a such that
$

\left(\frac {a}{p}\right)=-1
$

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

Here $

\left(\frac {2}{p}\right)=-1
$

is legendre symbol.

2. Originally Posted by peteryellow
Show that if p is not a Fermat prime, then there is a such that
$

\left(\frac {a}{p}\right)=-1
$

and [a]_p is not a generator of $(\mathbb Z/p)^*$.
Recall the fact that all primes of the form $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 $
\phi \left( {\phi \left( p \right)} \right) = \phi \left( {p - 1} \right)
$
primitive roots ( or generators) in $(\mathbb Z/p)^*$

And there are $
\tfrac{{p - 1}}
{2}
$

So we'd like to show that $
\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: $
p - 1 = 2^\alpha \cdot m
$
with $
\alpha;m \in \mathbb{Z}^ +
$
such that $
\left( {m,2} \right) = 1
$
- since p>2, the case p=2 is trivial-

Then: $
\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 $
m = 1
$

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

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