From Ireland's Number theory book, Ch.3 ex. 6.
Let and integer $n>0$ be given. A set of integers $a_{1},a_{2}, \cdots ,a_{\phi(n)}$ is called a reduced residue system modulo $n$ if they are pairwise incongruent mod n and $(a_{i},n)=1$ for all $i$. If additionally $(a,n)=1$, prove that $aa_{1},aa_{2}, \cdots ,aa_{\phi(n)}$ is again a reduced residue system modulo n.
I can solve this problem, however, it is not clear to me how this result helps in the following (ex7)
Use ex.6 to give another proof of Euler's therorem, $a^{\phi(n)}\equiv 1 \pmod{n}$ for $(a,n)=1$
Best Answer
There are exactly $\phi(n)$ elements of $\mathbb{Z}/n\mathbb{Z}$ that lift up to integers coprime with $n$, so any reduced residue system corresponds to exactly the same set of representatives in the ring of integers. This means that the product $a_1\cdots a_{\phi(n)}$ is the same as $b_1\cdots b_{\phi(n)}$ modulo $n$ when $a_i$ and $b_i$ are two such systems. Take $b_i=aa_i$ and then divide out both sides of the equality by $a_1\cdots a_{\phi(n)}$ to obtain Euler's.