# A proof of Euler's Theorem in Number theory

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$

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.

• @Edison: It is worth noting that the product $a_1 \cdots a_{\phi(n)}$ is nonzero (if it were zero, the final division step would be invalid). – Srivatsan Feb 1 '12 at 5:48

If $a_1,\ldots,a_{\phi(n)}$ is a reduced residue system, then so is $aa_1,aa_2,\ldots,aa_{\phi(n)}$. Therefore, $$a_1a_2\cdots a_{\phi(n)} \equiv (aa_1)(aa_2)\cdots(aa_{\phi(n)}) \equiv a^{\phi(n)}(a_1\cdots a_{\phi(n)})\pmod{n}.$$

HINT: If $a_{1}, a_{2}, \cdots , a_{\phi(n)}$ and $b_{1}, b_{2}, \cdots , b_{\phi(n)}$ are two reduced bases, what can you say about the products

$\displaystyle \prod_{i=1}^{\phi(n)} a_i$

and

$\displaystyle \prod_{i=1}^{\phi(n)} b_i?$