Why does Euler's totient theorem always return 1 for two relative primes?

Question

I'm working on a RSA encryption algorithm, and I can put in the formula and get the result I want, but I'm trying to understand how it is doing what it's doing.

So the theorem in its basic form is:

If GCD(x, y) = 1; and x < y; then x^φ(y) ≡ 1 (mod y)

So for 8 and 21:

8^φ21 ≡ 8¹² ≡ 1 (mod 21)

Where Φ(n) is all the numbers that are relatively prime to n for 1 to n - 1 (i.e. all the numbers in that range than have no factors in common with n other than 1).

But my question is why is this the case? Why is x^φ(y) always congruent with 1 for a modulo of y? (When GCD(x, y) = 1; and x < y). I can't seem to get my head around what is going on conceptually, even though I can use the formula in practice. Any advice will be greatly appreciated.

Answer 1

Here is the proof in the case $x=3$, $y=10$. We start with the numbers $1,3,7,9$ which are coprime to $10$, and multiply them all by $3$ to get $$3\times1\equiv3\,,\quad 3\times3\equiv9\,,\quad 3\times7\equiv1\,,\quad 3\times9\equiv7\pmod{10}\ .$$ Multiplying all these, $$(3\times1)\times(3\times3)\times(3\times7)\times(3\times9)\equiv 3\times9\times1\times7\pmod{10}\ .$$ Now we can cancel $1\times3\times7\times9$ to find $$3^4\equiv1\pmod{10}\ .$$ IMHO this is one of the best proofs in elementary number theory: it not only shows that the result is true, but also makes it clear why the exponent has to be the number of residues modulo $10$ which are coprime to $10$. Of course to give a complete proof there are a couple of things you have to do.

(1) For any $x$ and $y$, show that if you take the coprime residues modulo $y$ and multiply them all by $x$, you get the same residues back again.

(2) Explain why the residues can then all be cancelled.

I suspect it is these details that are causing you difficulty. But if you concentrate on the main idea, as illustrated by one example, it should help you to understand what is going on. Good luck!