# 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 $p > 2$ then $a^{\frac{p-1}{2}} \equiv 1 \ \ (mod \ p)$ or $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 $p > 2$ then $a^{\frac{p-1}{2}} \equiv 1 \ \ (mod \ p)$ or $a^{\frac{p-1}{2}} \equiv -1 \ \ (mod \ p)$.

Any tips or approach suggestions will be useful.

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

And why is this last implication correct? This is because $\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 $\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 $\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 $D$ is a finite integral domain then $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.