Question

Prove Fermat’s Little Theorem: If p is a prime and $\mathbf{a}\mathbf{\in }\mathbf{Z}$, then ${\mathbf{a}}^{\mathbf{p}}\mathbf{=}\mathbf{a}\left(\mathrm{mod}p\right)$. If a is relatively prime to p, then ${\mathbf{a}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{=}\mathbf{1}\left(\mathrm{mod}p\right)$. [Hint translate congruence statements in Z into equality statements in ${\mathbf{Z}}_{\mathbf{p}}$and use Theorem 11.25]

Short answer

${\mathrm{a}}^{\mathrm{p}}=\mathrm{a}\left(\mathrm{mod}\mathrm{p}\right)$ and ${\mathrm{a}}^{\mathrm{p}-1}=1\left(\mathrm{mod}\mathrm{p}\right)$

Step-by-step solution

Separable polynomial:

If the roots of a polynomial are distinct in an algebraic closure of K, then the polynomial p(x) over a given field K is separable.

To prove that ap=a(mod p) and ap-1=1(mod p)

Assume that a belongs to ${\mathrm{Z}}_{\mathrm{p}}$that is $a\in Z_p$and let p is a prime.

Now, to prove that ${\mathrm{a}}^{\mathrm{p}}=\mathrm{a}\left(\mathrm{mod}\mathrm{p}\right)$

It is required to show that the root of $x^p-x$is every element of $Z_p$

Proof:

Let C be any nonzero element of $Z_p$as ${0_z}_p$is a root.

Let U be the product of ${\mathrm{a}}_1,{\mathrm{a}}_2,...{\mathrm{a}}_{\mathrm{n}}$and let ${\mathrm{a}}_1,{\mathrm{a}}_2,...{\mathrm{a}}_{\mathrm{n}}$be all the nonzero elements of $Z_p$.

So, $\mathrm{u}={\mathrm{a}}_1,{\mathrm{a}}_2,...{\mathrm{a}}_{\mathrm{n}}$

Now, $c_i=c_j$

So, the product of elements is:

$\begin{array}{rcl}\mathrm{U}& =& \left({\mathrm{aa}}_1\right)\left({\mathrm{aa}}_2\right)....\left({\mathrm{aa}}_{\mathrm{n}}\right)\\ & =& {\mathrm{a}}^{\mathrm{n}}\left({\mathrm{a}}_1{\mathrm{a}}_2....{\mathrm{a}}_{\mathrm{n}}\right)\\ & =& {\mathrm{ua}}^{\mathrm{n}}\\ & & \end{array}$

Now, cancel Us in the above equation, therefore,

${\mathrm{a}}^{\mathrm{n}}=1_{{\mathrm{z}}_{\mathrm{p}}}$

Hence,

role="math" localid="1659166769782" $$\begin{gathered} {\mathrm{a}}^{\mathrm{n}+1}=\mathrm{a} \\ {\mathrm{a}}^{\mathrm{n}+1}-\mathrm{a}=0_{{\mathrm{z}}_{\mathrm{p}}} \end{gathered}$$

The element is a root of ${\mathrm{x}}^{\mathrm{p}}-\mathrm{x}$since $\mathrm{n}+1=\mathrm{p}$

Hence, ${\mathrm{a}}^{\mathrm{p}}=\mathrm{a}$in $Z_p$.

Which means that ${\mathrm{a}}^{\mathrm{p}}=\mathrm{a}\left(\mathrm{mod}\mathrm{p}\right)$

Now, assume that a is relatively prime to p.

To prove that ${\mathrm{a}}^{\mathrm{p}-1}=1\left(\mathrm{mod}\mathrm{p}\right)$

Proof:

Consider a bijective function ${\mathrm{f}}_{\mathrm{a}}:{\mathrm{Z}}_{\mathrm{p}}\to {\mathrm{Z}}_{\mathrm{p}}$

It is enough to show that f_a is an injection.

So let ${\mathrm{f}}_{\mathrm{a}}\left({\left[{\mathrm{x}}_1\right]}_{\mathrm{p}}\right)={\mathrm{f}}_{\mathrm{a}}\left({\left[{\mathrm{x}}_2\right]}_{\mathrm{p}}\right)$

Then ${\mathrm{ax}}_1={\mathrm{ax}}_2\mathrm{mod}\mathrm{p}$

Also, $\gcd \left(\mathrm{a},\mathrm{p}\right)=1$since a and p are relatively prime.

Hence${\mathrm{x}}_1={\mathrm{x}}_2\mathrm{mod}\mathrm{p}$

Which implies that ${\left[{\mathrm{x}}_1\right]}_{\mathrm{p}}={\left[{\mathrm{x}}_2\right]}_{\mathrm{p}}$

Hence, f_a is an injection.

Now,

$\begin{array}{rcl}{\left[\left(\mathrm{p}-1\right)!\right]}_{\mathrm{p}}& =& {\left[1\right]}_{\mathrm{p}}{\left[2\right]}_{\mathrm{p}}.....{\left[\mathrm{p}-1\right]}_{\mathrm{p}}\\ & =& {\left[1\mathrm{a}\right]}_{\mathrm{p}}{\left[2\mathrm{a}\right]}_{\mathrm{p}}....{\left[\left(\mathrm{p}-1\right)\mathrm{a}\right]}_{\mathrm{p}}\end{array}$

Now, ${\mathrm{f}}_{\mathrm{a}}\left({\left[0\right]}_{\mathrm{p}}\right)={\left[0\right]}_{\mathrm{p}}$ implies that f is an injection.

Now,${\left[1\mathrm{a}\right]}_{\mathrm{p}}{\left[2\mathrm{a}\right]}_{\mathrm{p}}....{\left[\left(\mathrm{p}-1\right)\mathrm{a}\right]}_{\mathrm{p}}={\left[\left(\mathrm{p}-1\right)!{\mathrm{a}}^{\mathrm{p}-1}\right]}_{\mathrm{p}}$

So that, $\left(\mathrm{p}-1\right)!=\left(\mathrm{p}-1\right)!{\mathrm{a}}^{\mathrm{p}-1}\mathrm{mod}\mathrm{p}$

Therefore, $\gcd \left(\left(\mathrm{p}-1\right)!,\mathrm{p}\right)=1$

Thus, ${\mathrm{a}}^{\mathrm{p}-1}=1\left(\mathrm{mod}\mathrm{p}\right)$

Hence, proved.