Let $a$ and $n$ be integers such that $n >0$ and $gcd(a,n)=1$. Then $a^{\phi(n)}\equiv 1$ (mod $n$). (with $\phi(n)$ being the Euler function)
Proof:
Since $|U(n)|=\phi(n)$ and $a\in U(n)$ because $gcd(a,n)=1$, then $a^{\phi(n)}=a^{|U(n)|}=1$ for all $a\in U(n)$. Then $n|(a^{\phi(n)}-1)$. Then $a^{\phi(n)}\equiv 1$ (mod $n$).
This was the proof given in class, and we did not discuss any Euler quotient. So how do I deduce that $n|(a^{\phi(n)}-1)$? I cannot find the connection.
On
By definition, for every natural number $n$, the value $\phi(n)$ the Euler $\phi$ function at $n$ is defined as the number of elements in the set $\{ 1, \dots, n \}$ that are relatively prime to $n$; that is, $$ \phi(n) = \# \{ \ x \in \mathbb{N}: \ x \leq n, \ \mathrm{gcd}(x, n) = 1 \ \} = \left\lvert \{ \ x \in \mathbb{N}: \ x \leq n, \ \mathrm{gcd}(x, n) = 1 \ \} \right\rvert,$$ where, for any set $S$, $\#(S)$ or $\lvert S \rvert$ denotes the cardinality of $S$, which of course is the same as the number of elements in $S$ if $S$ is a finite set.
Now suppose that $a$ and $n$ are integers such that $n > 0$ and $\mathrm{gcd} (a, n) = 1$. Let $r_1, \ldots, r_{\phi(n)}$ be the natural numbers in the set $\{ 1, \ldots, n \}$ that are relatively prime to $n$. Then, for each $i = 1, \ldots, \phi(n)$, we can write $$ r_i x_i + n y_i = 1$$ for a unique pair of integers $x_i$ and $y_i$, and so $$ r_i x_i - 1 = n y_i, \tag{1}$$ which implies that $$ r_i x_i \equiv 1 \ (\mod n), \tag{2}$$ and (1) also implies that $\mathrm{gcd} \left( x_i, n \right) = 1$ also, and so $$ \mathrm{gcd} \left( r_i x_i, n \right) = 1. \tag{3} $$ Hope these facts are clear to you.
Now (2) gives $$ a r_i x_i \equiv a\ ( \mod n). \tag{4}$$ for each $i = 1, \ldots, \phi(n)$.
Multiplying together all the congruences in (4) we obtain $$ a^{\phi(n)} \prod_{i=1}^{\phi(n)} r_i x_i \equiv a^{\phi(n)}\ ( \mod n). \tag{5} $$ But from (3) we can also conclude that $$ \mathrm{gcd} \left( \prod_{i=1}^{\phi(n)} r_i x_i \ , \ n \right) = \prod_{i=1}^{\phi(n)} r_i x_i \mathrm{gcd} \left( r_i x_i \ , \ n \right) = 1. \tag{6} $$ Now by virtue of (6), we can divide both sides of (5) by the non-zero integer $\prod_{i=1}^{\phi(n)} r_i x_i $ to obtain $$ a^{\phi(n)} \equiv 1 \ ( \mod n), $$ as required.
Hope this is helpful.
That proof seems straight forward to me.
Let $U(n)$ be the set of units modulo $n$ that is $U(n)=\{k \in Z_{n}| \gcd(k,n) = 1\}$.
$|U(n)| = \phi(n)$, of course.
And under multiplication $U(n)$ is a group.
Pf: $1 \in U(n)$ and $1*k = k$. If $k \in U(n)$ then by Bezout, there are $p, q$ so that $pk + mn = 1$ and thus $pk \equiv 1 \mod n$ and as an equivalency class $p$ is the inverse of $k$. And $p$ must be relatively prime to $n$ or else $pk + mn$ could not be $1$. So every element of $U(n)$ has an inverse. QED.
Using the notation of $[m]$ to be the equivalence class of the integer $m$ we get: $|U(n)| = \phi(n)$. Then for any $[a] \in U(n)$, by Legrange's Theorem, we have $[a]^{|U(n)|} = [a]^{\phi(n)}=[a^{\phi(n)}]=[1]$ under the group operation.
But the group operation is nothing more than multiplication of equivalency classes. So $a^{\phi(n)} \equiv 1 \mod n$. and that's that.
The proof took an extra step that for $[a], [b] \in U(n)$ to say that $[a] = [b]$ means that $n| (b- a)$. I don't see that that step makes things any easier of clearer. In fact I think it muddies things.