# I don't understand a step in the proof of Euler's Theorem, please explain

I am trying to learn the proof for Euler's theorem which states:

If $\gcd(a,m)=1$ then $a^{\phi(m)} \equiv 1 \mod m$.

The proof goes like this. Take the reduced residue system modulo $m$. $ar_1,...,ar_k$ is also a reduced residue system modulo $m$ (the text proves this lemma) then they state that,

$$r_1 r_2...r_k \equiv a r_1 a r_2... a r_k \mod m$$

Where $k=\phi(m)$. I don't understand this step, please explain.

• prove it when $m$ is a prime (Fermat little theorem), then when it is a prime power, and finally prove the general statement : if $a^{(p_i^{\;e_i}-1)} \equiv 1 \pmod{p_i^{e_i}}$ for $p_1,p_2,\ldots,p_k$ different primes and $e_i$ some integer exponents, then $a^{\prod ( p_i^{\;e_i} - 1)} \equiv 1 \pmod{\prod p_i^{e_i}}$ or with $m = \prod p_i^{\; e_i}$ : $a^{\phi(m)} \equiv 1 \pmod m$ – reuns Feb 9 '16 at 1:09

A reduced residue system mod $m$ consists of those congruence classes that are relatively prime to $m$. Stated differently, we say that $r_1, \ldots, r_k$ is a reduced residue system mod $m$ if it is a reordering of every number (mod $m$) from $1$ to $m-1$ that is relatively prime to $m$.

So the two lists of numbers $r_1, r_2, \ldots, r_k$ and $ar_1, ar_2, \ldots, ar_k$ are the same lists of numbers (mod $m$, that is). Therefore multiplying them together mod $m$ must give the same product, which is the step you are asking about.

Let's do an example. Suppose we're interested in showing $2^6 \equiv 1 \pmod 9$. Then a reduced residue system mod $9$ is $$1,2,4,5,7,8.$$ What happens when we multiply each of these by $2$? At first, we get $$2,4,8,10,14,16,$$ and after reducing mod $9$ we get $$2,4,8,1,5,7.$$ Notice that this is exactly the same as the first list, but in a different order.

Since these are the same lists, their products must be equal. Here, that means that $$1\cdot 2 \cdot 4 \cdot 5 \cdot 7 \cdot 8 \equiv 2 \cdot 4 \cdot 8 \cdot 10 \cdot 14 \cdot 16 \equiv 2^6 \cdot 1 \cdot 2 \cdot 4 \cdot 5 \cdot 7 \cdot 8 \pmod 9.$$ After multiplying by the modular inverse of $1 \cdot 2 \cdot 4 \cdot 5 \cdot 7 \cdot 8$, we see that $$2^6 \equiv 1 \pmod 9.$$

Do you see how it works now?

• So $r_i \equiv ar_i\mod m$ when $1 \leq i \leq m-1$ since the $a$ and $m$ are coprime? Therefore the product of the two sets of integers are equivalent modulo $m$ (which I'll have to take a look at)? – Agnostic Atheist Feb 9 '16 at 1:06
• It's not actually true that $r_i \equiv a r_i \pmod m$, in the sense that you've used $i$ for both sides. The two lists are the same, but not necessarily in the same order. For instance, in my first list in the example, $r_1 = 1$ while $2r_1 = 2$. These aren't the same. But overall, as lists, the list of $r_i$ is the same list as those of $ar_i$ after reducing mod $m$. – davidlowryduda Feb 9 '16 at 2:20

The function multiply-by-$a$-mod $m$ is a bijection, ie. a permutation on the set $\{r_1,r_2,\ldots, r_k\}$. SO the product on either sides in your question are equal mod m. To check it is a bijection suffices to check it is one-one.

Suppose $ar_i\equiv ar_j \pmod m$. This shows $m$ divides $a(r_i-r_j)$. But as $\gcd(a,m)=1$ it follows that $r_i-r_j$ must be a multiple of $m$. As all the $r_i$'s are less than $m$ this is possible only when the difference is zero, hence $r_i=r_j$. QED