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.

  • $\begingroup$ 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$ $\endgroup$ – 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?

  • $\begingroup$ 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)? $\endgroup$ – Agnostic Atheist Feb 9 '16 at 1:06
  • $\begingroup$ 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$. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.