From Fermat to Euler

Mathematics

Let ${Z}_p^*$ demotes the set of positive integer $\{1,2,\cdots,p-1\}$,where $p$ is a prime.
Let $a$ be a positive integer where $p \not\mid a$.
$a{Z}_p^*$ is the full permutation of $\{1,2,\cdots,p-1\}$

Proof:
Let $a\prime = a \mod p$.
For $\forall n \in {Z}_p^*$,if $an \equiv an\prime\pmod{p}$,we have $a\prime n \equiv a\prime n\prime\pmod{p}$.

Because $a \nmid p$,so $gcd(a\prime,p)==1$,$a\prime \in {Z}_p^*$.That is,we can always find $a\prime$'s inverse of modulus $p$,called $a\prime^{-1}$.

Therefore,$a\prime^{-1}a\prime n \equiv a\prime^{-1} a\prime n\prime\pmod{p}$,which is $n \equiv n\prime\pmod{p}$.

Because $n \in \{1,\cdots,p-1\}$,so $n = n\prime$.
In other words,for $\forall n \in {Z}_p^*$,$an \mod{p}$ has distincted value and the range is $[1,p-1]$,so $a{Z}_p^*$ is a permutation of ${Z}_P^*$.

That is,$a{Z}_P^* == {Z}^*_P$.
Q.E.D.

$a^{p-1} \equiv 1\pmod{p}$

Since we have $a{Z}_P^* == {Z}_P^*$,when we multiply all the element in $a{Z}_p^*$,we are multiplying all the elements in ${Z}_P^*$ together.

That is,$a^{p-1}(p-1)! \equiv (p-1)!\pmod{p}$
Since $p$ is a prime,$\forall n \in \{1,...,p-1\}$have a unique inverse.

So we multiply $(p-1)!$ with both sides,we get $a^{p-1} \equiv 1\pmod{p}$.

The map $f_a:{Z}_p^* \mapsto {Z}_p^*$ is a bijection

The map is a permutation,so for every image,we can always find its preimage,so the map is a surjection.

We've already proved that every preimage will be mapped to distincted image.So every image have at most one preimage,the map is a injection.

In conclusion,it's a bijection.

The most important property...Maybe $gcd(a\prime,p)==1$?Without it,we can't find $a\prime^{-1}$ that cancel $a\prime$.

$a{Z}_n^*=={Z}_n^*$ when $gcd(a,n)==1$

From Bezout Theorem we've known that $ax \equiv gcd(a,n)\pmod{n}$,$gcd(a,n)$ is the smallest non-negative integer in $a{Z}_n^*$,and $\forall n \in a{Z}_n^*$ is multiple of $gcd(a,n)$.

Hence,if $a$ is not a coprime of $n$,$a{Z}_n^*$ can not be a permutation of ${Z}_n^*$.The map is neither surjection nor injection.

$1 \equiv a^{|{Z}_n^*|}\pmod{n}$

If ${Z}_n^*$ denotes all the coprime of $n$ in $\{1,\cdots,n-1\}$,then we got ${Z}_n^*==a{Z}_n^*$,where $a$ is also a coprime of $n$.
It's worth noting that every element in ${Z}_n^*$ have its inverse modulus $n$.

Let $m$ = $|{Z}_n^*|$
Then we multiply all the elements together like before,we get $n_1*n_2*\cdots*n_m \equiv a^m*n_1*n_2*\cdots*n_m\pmod{n}$.

Since every element in ${Z}_n^*$ have its inverse modulus $n$,we can multiply their inverse with both sides respectively.

Finally we get $1 \equiv a^{|{Z}_n^*|}\pmod{n}$.

More about Euler's Phi Function

1.when $p$ is a prime, $\phi(p) = p-1$.

2.when $p$ is a prime,for $\forall n \in \{1,\cdots,p^{k-1}\}$,$pn$ is a factor of $p^k$.
$\because |\{1,\cdots,p^{k-1}\}| = p^{k-1}$.
$\therefore \phi(p^k)=p^k-p^{k-1}$

3.when $n$is a composite and $n = q*p$ ,where $q$ and $p$ are distinct primes.
For $\forall c \in \{1,...,p\}$,$gcd(q*c,n)!=1$.Similarly,for $\forall c \in \{1,...,q\}$,$gcd(p*c,n)!=1$.

$\therefore \phi(n)=n-p-q+1.$(plus one because I subtract $p*q$ for two times.)

$\because q*p-p-q-1 = q(p-1)-(p-1)=(p-1)(q-1)$
$\therefore \phi(n)=\phi(p)\phi(q)$

4.Further on,if $n=q*p*...*r$,where $q,p,...,r$ are distinct primes,it seems like $\phi(n)=\phi(q)\phi(p)...\phi(r)$.

5.If $n=q*q*p*...*r$,where $q,p,...,r$ are distinct primes,it seems like $\phi(n)=q*\phi(q)\phi(p)...\phi(r)$