In my Excellent_OCW Repo, I have shown you the Logic Tree to prove Euler Theorem and how to applicate it to RSA. In this post, I wanna try to prove it as possible as completely.
Euler Totient Function
Def :
Euler Totient Function $\phi (n)$ denotes the numbers of integers in {$1, 2, 3, …, n-1$} that are relatively prime to $n$.
i.e.
$\phi (12) = 4$, because in {$1, 2, 3, …, 11$}, there are 4 numbers, {$1, 5, 7, 11$}, which are relatively prime to $n$.
Euler’s theorem
If $\gcd(n, k)$ = 1, $k^{\phi (n)} \equiv 1$ ($\mod n$ ) .
Proof
In order to prove Euler’s Theorem, It is necessary to firstly prove the following Lemmas:
Lemma 1:
Iff $\gcd (n, k)=1$ & $ak\equiv bk$ ($\mod n$), $a\equiv b$ ($\mod n$)
Proof
Idea:
Prove the existence of multicative inverse iff $\gcd(n, k)=1$.
Firstly, We should prove “ iff $\gcd(n, k)=1 \implies$ $ \exists k^{-1}$ “.
Use Linear Combination of “$\gcd(n, k)=1$”:
$$\exists_{s,t} s\cdot n + t\cdot k=1$$
Hence,
$$sn = 1-kt$$
$$1-kt\equiv0(\mod n)$$
$$kt \equiv 1(\mod n)$$
Versus,we could also prove iff $\exists k^{-1}\implies$ $\gcd(n, k)=1$
Thus, we have proved that,
Lemma 2:
Suppose that $\gcd(n, k)=1$, let $k_1, k_2, …, k_r$ in {$1, 2, …, n-1$} denotes these integers relatively prime to n, $(r = \phi(n) )$, {$rem(k_1\cdot k, n), …,rem(k_r\cdot k, n)$} = {$k_1,k_2,…,k_r$}
Because This is exactly a much hard Lemma to be proved, So I wanna Prove it by 2 parts.
In Part 1, we would show that there are exactly $r$ factors relatively prime to $n$ [Denoted as #$r$]. Then in Part 2, we would prove {$rem(k_1\cdot k, n), …,rem(k_r\cdot k, n)$} $\subset$ {$k_1,k_2,…,k_r$}. And based on Part 1 and 2, we could see that Lemma 2 holds.
Part 1
Prove that there are exactly and only r factors relatively prime to $n$.[Denoted as #$r$]
Suppoese $rem(k_i\cdot k,n)=rem(k_j\cdot k, n), (i\neq j)$
Hence, $k_i\cdot k \equiv k_j\cdot k (\mod n)$
Based on Lemma1, $k_i\equiv k_j (\mod n)$
Thus, $k_i - k_j \equiv 0(\mod n)$
Because $\gcd(k_i, n)=1$ and $\gcd(k_j, n)=1, n|(k_i-k_j)$
Thus, iff $k_i-k_j=0$, $n|(k_i-k_j)$.
Thus, $k_i = k_j, (i\neq j)$.
Above all, We have shown Part1 of Lemma 2.
Part2
Prove that {$rem(k_1\cdot k, n), …,rem(k_r\cdot k, n)$} $\subset$ {$k_1,k_2,…,k_r$}.
Because $\gcd(k_i\cdot k, n) = \gcd(rem(k_i\cdot k, n), n)=1$, and $\gcd(k_i, n)=1$
Thus,
$$\gcd(rem(k_i\cdot k, n),n)=\gcd(k_i, n)=1$$
Hence,
Conclusion
Based on $\sum i = r$,
Lemma 2$:=${$rem(k_1\cdot k, n), …,rem(k_r\cdot k, n)$} = {$k_1,k_2,…,k_r$} holds.
Proof of Euler’s Theorem
Because $\gcd(k_i\cdot k, n)=\gcd(rem(k_i\cdot k, n),n)= 1$,
$$\prod_{i=1}^r rem(k_i\cdot k, n)\equiv \prod_{i=1}^r k_i\cdot k(\mod n)$$
Based on Lemma 2 and Lemma 1,
$$\prod_{i=1}^r rem(k_i\cdot k, n)=\prod_{i=1}^r k_i$$
Thus,
$$1\equiv \prod_{i=1}^r k(\mod n)$$
$$k^r \equiv 1 (\mod n)$$
Because $r = \phi(n)$,
$$k^{\phi(n)}\equiv1(\mod n)$$
Euler’s Theorem Holds.
Fermat’s Little Theorem
Suppose that $p$ is a prime, It is ease to know that there are {$1, 2, …, p-1$}, $p-1$ factors relatively prime to $p$. Thus, as for a prime $p$, we have $\phi(p)=p-1$. Hence, at that case, Euler’s Theorem could be expressed as following:
Iff $\gcd(k, p)=1$, and $p$ is a prime,
$$k^{p-1}\equiv 1(\mod p)$$
As for this derived Theorem from Euler’s Theorem, We called it “Fermat’s Little Law”.
In Part2, I would show you concrete applications about this elegant theory, such as RSA and SSH.