Let, be a primitive root.

What is the order of ?

Assume, and arrive at contradiction.

We have,

If, is even then we can drop the negative sign,

Contradiction.

If, is odd then some difficultly arises.

So we cannot drop the negative sign,

Multiply through by ,

Since, odd we have even.

Thus, we can write,

We see that is a quadradic residue of .

Hence the Legendre symbol,

Since the Legendre symbol is multiplicative,

Since,

We know that,

Thus,

Then by Euler's criterion we have,

But, is a primitive root

And, .

Thus, we have another contradiction.

Thus can never be odd.

That means the only possible choice is .