I'm trying to understand how I can prove Euler's theorem, using group theoretical methods and concepts, and found this:
-
An integer $a$ is invertible modulo $n$ if and only if $\textrm{gcd}\:(a,n)=1$ ("invertible" means there's some $a^{−1}$ such that $a\cdot a^{−1}\equiv 1~\textrm{ mod}~ n$). This is the Linear Congruence Theorem.
-
Consider the group $G$ of all positive integers less than $n$ which are invertible modulo $n$ (formally, $G=(\mathbb Z/n\mathbb Z)\times$ ). $\varphi(n)$ simply counts the number of positive integers $a$ where $\textrm{gcd}~(a,n)=1,$ so by (1) there are $\varphi (n)$ elements in $G$ (the order of $G $ is $\varphi(n)$). You can satisfy yourself that $G$ follows the group axioms quickly.
-
Lagrange's theorem says that there must be some $k$ such that $a^k=1$ where $k$ divides the order of the group, namely $\varphi(n)$; let's say $km=\varphi(n).$ Then $a^\varphi(n)=a^{km}=(a^k)^m=1^m=1$ which proves our theorem!
(Source)
However, I wonder how I can prove that $G$ has an inverse that is a part of the underlying set in $G$. Thanks to the linear congruence theorem I know that there is an inverse to any $a$ in this set, but how do I prove that the inverse is a part of the same set?
Best Answer
I take it you want to show that for any $n$ and for any $(a,n)=1$, $$\tag 1 a^{\varphi(n)}=1\mod n$$
As you said, it suffices to show that $\Bbb Z_n^\times$ is a group under multiplication.
But one can show $k$ is invertible mod $n$ iff $(k,n)=1$, by Bezout. Note that if $(k,n)=1$; we know there are $s,t$ with $ks+nt=1$, and $ks=1\mod n$; and moreover we have $(s,n)=1$ by the same equation that witnessed $(k,n)=1$.
Then $(k,n)=(k',n)=1\implies (kk',n)=1$. Thus $\Bbb Z_n^\times $ is a group under multiplication. It has order $\varphi(n)$, so by Lagrange's thorem $(1)$ holds for any $a$.