# Fermat's Little Theorem Help [again]

• Oct 27th 2008, 10:19 AM
Rafael Almeida
Fermat's Little Theorem Help [again]
Hi all,

The question concerns que same subject as my previous post in this section, but I still didn't figure it out:

Let p be a prime number and a be an integer such that p does not divide a. Show that if $\displaystyle p > 2$ then $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ \ (mod \ p)$ or $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ \ (mod \ p)$.

Any tips or approach suggestions will be useful.

• Oct 27th 2008, 11:37 AM
Laurent
Quote:

Originally Posted by Rafael Almeida
Hi all,

The question concerns que same subject as my previous post in this section, but I still didn't figure it out:

Let p be a prime number and a be an integer such that p does not divide a. Show that if $\displaystyle p > 2$ then $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ \ (mod \ p)$ or $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ \ (mod \ p)$.

Any tips or approach suggestions will be useful.

This is because $\displaystyle \left(a^{\frac{p-1}{2}}\right)^2\equiv a^{p-1}\equiv 1\,({\rm mod }\,p)$ (by Fermat's little theorem) and $\displaystyle \pm 1$ are the only roots of the polynomial $\displaystyle X^2-1$ on the field $\displaystyle \mathbb{Z}_p$ (in a field, a polynomial of degree $\displaystyle n$ has at most $\displaystyle n$ roots). Or you can say: if $\displaystyle x^2\equiv 1\,({\rm mod}\,p)$, then $\displaystyle p|x^2-1=(x-1)(x+1)$, so that either $\displaystyle p|x+1$ (i.e. $\displaystyle x\equiv -1\,({\rm mod}\, p)$) or $\displaystyle p|x-1$ (i.e. $\displaystyle x\equiv 1\,({\rm mod}\, p)$) because $\displaystyle p$ is prime.
• Oct 27th 2008, 06:37 PM
ThePerfectHacker
Here is a related proof: $\displaystyle a^{p-1} \equiv 1 \implies a^{p-1} - 1\equiv 0 \implies \left( a^{(p-1)/2} - 1\right)\left( a^{(p-1)/2}+1\right) \equiv 0 (\bmod p)$.
From here we see $\displaystyle a^{(p-1)/2}\equiv \pm 1(\bmod p)$.
• Oct 28th 2008, 01:12 AM
Laurent
Quote:

Originally Posted by ThePerfectHacker
Here is a related proof: $\displaystyle a^{p-1} \equiv 1 \implies a^{p-1} - 1\equiv 0 \implies \left( a^{(p-1)/2} - 1\right)\left( a^{(p-1)/2}+1\right) \equiv 0 (\bmod p)$.
From here we see $\displaystyle a^{(p-1)/2}\equiv \pm 1(\bmod p)$.

And why is this last implication correct? This is because $\displaystyle \mathbb{Z}_p$ is a field (and hence an integral domain). Or because of the other elementary argument I gave about divisibility.
• Oct 28th 2008, 08:15 AM
ThePerfectHacker
Quote:

Originally Posted by Laurent
And why is this last implication correct? This is because $\displaystyle \mathbb{Z}_p$ is a field (and hence an integral domain). Or because of the other elementary argument I gave about divisibility.

Yes, I should have been more explicity why the last line holds. By the way, when I talk about $\displaystyle \mathbb{Z}_p$ instead of saying "it is a field and hence and integral domain" I perfer to say "it is an integral domain and hence a field". Why? Because there is a theorem, which I am sure you know but if not it is a nice result, that says if $\displaystyle D$ is a finite integral domain then $\displaystyle D$ is a field. (Surprised) Because I like this result I like to switch around the order of my statement. But whatever, I am getting off topic.