Euler's theorem in elementary number theory goes as
$$c^{\phi(n)} \equiv 1 \pmod{n}$$
where $\gcd(c,n) = 1$. This is one of first classical results one gets introduced to in elementary number theory is Euler's theorem. This post look at a well-known proof of this theorem.
Proof: Consider the set of all numbers less than $n$ and relatively prime to it. Let $\{a_1,a_2,...,a_{\varphi(n)}\}$ be this set.
Consider a number $c < n$ and relatively prime to it i.e. $c \in \{a_1,a_2,\ldots,a_{\varphi(n)}\}$.
First observe that for any $a_i$, $c a_{i} \equiv a_{j} (\bmod n)$ for some $j$. This is true since $c$ and $a_i$ are themselves relatively prime to $n$, their product has to be relatively prime to $n$.
If $c a_{i} \equiv c a_{j} (\bmod n)$ then $a_i = a_j$. Note that cancellation can be done since $c$ is relatively prime to $n$.
Hence, if we now consider the set $\{ca_1,ca_2,...,ca_{\varphi(n)}\}$ this is just a permutation of the set $\{a_1,a_2,...,a_{\varphi(n)}\}$.
Thereby, we have $\displaystyle \prod_{k=1}^{\varphi(n)} ca_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.
Hence, we get $\displaystyle c^{\varphi(n)} \prod_{k=1}^{\varphi(n)} a_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.
Now, note that $\displaystyle \prod_{k=1}^{\varphi(n)} a_k$ is relatively prime to $n$ and hence you can cancel them on both sides to get
$$c^{\varphi(n)} \equiv 1 (\bmod n)$$ whenever $\gcd(c,n) = 1$
$$c^{\phi(n)} \equiv 1 \pmod{n}$$
where $\gcd(c,n) = 1$. This is one of first classical results one gets introduced to in elementary number theory is Euler's theorem. This post look at a well-known proof of this theorem.
Proof: Consider the set of all numbers less than $n$ and relatively prime to it. Let $\{a_1,a_2,...,a_{\varphi(n)}\}$ be this set.
Consider a number $c < n$ and relatively prime to it i.e. $c \in \{a_1,a_2,\ldots,a_{\varphi(n)}\}$.
First observe that for any $a_i$, $c a_{i} \equiv a_{j} (\bmod n)$ for some $j$. This is true since $c$ and $a_i$ are themselves relatively prime to $n$, their product has to be relatively prime to $n$.
If $c a_{i} \equiv c a_{j} (\bmod n)$ then $a_i = a_j$. Note that cancellation can be done since $c$ is relatively prime to $n$.
Hence, if we now consider the set $\{ca_1,ca_2,...,ca_{\varphi(n)}\}$ this is just a permutation of the set $\{a_1,a_2,...,a_{\varphi(n)}\}$.
Thereby, we have $\displaystyle \prod_{k=1}^{\varphi(n)} ca_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.
Hence, we get $\displaystyle c^{\varphi(n)} \prod_{k=1}^{\varphi(n)} a_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.
Now, note that $\displaystyle \prod_{k=1}^{\varphi(n)} a_k$ is relatively prime to $n$ and hence you can cancel them on both sides to get
$$c^{\varphi(n)} \equiv 1 (\bmod n)$$ whenever $\gcd(c,n) = 1$
