Trying to understand the proof of Eulers generalisation of Fermat's theorem

Question

So I'm trying to understand how to prove Eulers generalisation of Fermat's theorem:

$a^{\phi(n)} \cong 1$ (mod n)

---

Proof:

If gcd(a, n) = 1 then a has a multiplicative inverse in set n.

Let m = $\phi($n$)$, and

set $[$x$_1]$, $[x_2],...,[x_m]$

be all the elements which has an inverse in set n.

let $y_i \cong ax_i$(mod n) for i = 1, 2, ..., m.

So we have : $y_1, y_2,...,y_m$

---

Then :

• gcd($y_i$, n) = 1 as gcd(a, n) = 1 and gcd($x_i$, n) = 1

• $y_1, y_2,...,y_m$ are all distinct.

hence $y_1, y_2,...,y_m$ are the m positive integers less than n which are coprime to n and thus:

(From here on I don't really understand)

$\Pi x_i \cong \Pi y_i ($mod n$) \cong \Pi ax_i ($mod n$) \cong a^m \Pi x_i ($mod n$)$

But as $x_1, x_2, ..., x_m$ are all invertible, so is $\Pi x_i \cong x_1,x_2,...,x_m$

hence $1 \cong a^m$(mod n)

Answer 1

Note that the $y_i$'s are the $x_i$'s, by another order. So, when you multiply the $y_i$'s, you must get the same thing (modulo $n$) that you get when you multiply the $x_i$'s.

Besides that, since there are $m$ $x_i$'s,$$\prod_{i=1}^max_i=(ax_1)(ax_2)\ldots(ax_m)=a^mx_1x_2\ldots x_m=a^m\prod_{i=1}^mx_i.$$