Proof of Euler's Theorem I am trying to prove the following statement: $a^{\varphi(n)}\equiv 1\mod n$ for every integer $a$ relatively prime to $n$. Is the following correct?
Let $a\in \mathbb{Z}$ be relatively prime to $n$. By the division algorithm, $a=qn+r$. Thus $a\mod n \equiv r$ so the problem reduces to showing the result is true for $r$. Let $r\in (\mathbb{Z}/n\mathbb{Z})^\times$. Since $|\langle r \rangle|$ divides the order of the group (namely $\varphi(n)$), it follows that $r^{\varphi(n)}\equiv1\mod n$. The result follows.
 A: That's essentially it.
You shouldn't say, "Let $r\in(\mathbb Z/n\mathbb Z)^\times$," because you already have a value $r$, and it is an integer. "Let $r$..." means you are adding a new assumption about $r$, which is not what you want.
What you should do is prove $\langle r\rangle\in(\mathbb Z/n\mathbb Z)^\times.$
Of course, $\langle a\rangle=\langle r\rangle$, so the division algorithm step is technically not needed. You just need to show that $\langle a\rangle\in (\mathbb Z/m\mathbb Z)^\times.$

(I'm assuming your notation $\langle x\rangle$ means the equivalence class of $x$ in $\mathbb Z/m\mathbb Z$. That is, $\langle x\rangle = x+m\mathbb Z$.)

A full form of this proof is then (assuming we already know $(\mathbb Z/m\mathbb Z)^\times$ is a group of $\phi(m)$ elements:)

Since $\gcd(a,m)=1$, we can solve $ax+my=1$, so $\langle a\rangle \langle x\rangle =\langle 1\rangle$, so $\langle a\rangle\in(\mathbb Z/m\mathbb Z)^\times$, so $\left\langle a^{\phi(m)}\right\rangle=\langle a\rangle ^{\phi(m)}=\langle 1\rangle$, and thus $a^{\phi(m)}\equiv 1\pmod{m}$.

