A clever proof of Euler's Theorem

I've been learning abstract algebra for the last six months or so - and I have learned a lot - yet I get the distinct impression that if Euclid were to appear before me and demand to know why he should care about groups or rings or what have you I wouldn't have much to say. So I was happy to learn of a simple proof of Euler's theorem, which relies solely on Lagrange's theorem, a basic result of group theory.

Euler's theorem deals with $\phi$, the Euler totient function, where $\phi(n)$ is the number of integers less than $n$ that are coprime to $n$. For example, $\phi(6)=2$, since 1 and 5 are the only integers less than 6 that are coprime to 6. If $p$ is prime, $\phi(p)=p-1$ since every number less than $p$ is relatively prime to $p$.

Upon first hearing about this function, I thought it was too insanely complex to know anything about. How the hell should I know what $\phi(n)$ is? There's no easy formula. But it turns out that we can prove the following theorem quite easily:

Euler's theorem: Suppose $a,n$ are coprime. Then $a^{\phi(n)}\equiv 1 \pmod{n}$.

Note that, since $\phi(p)=p-1$, this is just a generalization of Fermat's little theorem. Here's a three-step proof:

1. An integer $a$ is invertible modulo $n$ if and only if $gcd(a,n)=1$ ("invertible" means there's some $a^{-1}$ such that $aa^{-1}\equiv 1 \bmod n$). This is the Linear Congruence Theorem.
2. Consider the group $G$ of all positive integers less than $n$ which are invertible modulo $n$ (formally, $G=\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$). $\phi(n)$ simply counts the number of positive integers $a$ where $gcd(a,n)=1$, so by (1) there are $\phi(n)$ elements in $G$ (the order of $G$ is $\phi(n)$). You can satisfy yourself that $G$ follows the group axioms quickly.
3. Lagrange's theorem says that there must be some $k$ such that $a^k=1$ where $k$ divides the order of the group, namely $\phi(n)$; let's say $km=\phi(n)$. Then $a^{\phi(n)}=a^{km}=\left(a^k\right)^m=1^m=1$ which proves our theorem!

Isn't that cool? I went from thinking that $\phi$ was an impossibly complex function to knowing a foundational result about it within 5 minutes, all because of what seemed like an esoteric result in group theory. 90% of this short post is explaining the terms, the proof itself is only a paragraph!