Euler's Theorem

If a and n are coprime whole numbers with n>1, then:

a^φ(n) ≡ 1 (mod n)

In other words: when we raise a to the power φ(n) and divide by n, the remainder is 1.

So what does coprime mean, and what's φ(n)?

Coprime: Two numbers are coprime if their only common factor is 1.

Euler's Totient Function φ(n): This counts how many whole numbers less than n are coprime to n.

An example will help:

Example: a = 3, n = 10

Are they coprime?

The only common factor of 3 and 10 is 1. Yes!

Find φ(10)

The whole numbers less than 10 that are coprime to 10 are:

{1, 3, 7, 9}

There are 4 of them, so φ(10) = 4.

Calculate

a^φ(n) = 3⁴ = 81

Check the remainder

81 ÷ 10 = 8 remainder 1

So 3⁴ ≡ 1 (mod 10)

Why Does This Work?

If we look at all the numbers less than n that are coprime to n, they form a special repeating pattern when multiplied by a (as long as a is also coprime to n).

When we multiply each of those numbers by a, we just rearrange them, we don't create any new remainders.

Because of this repeating pattern, multiplying them all together leads to:

a^φ(n) ≡ 1 (mod n)

Note: Euler's Theorem is a generalization of Fermat's Little Theorem.

Why Is This Useful?

Euler's Theorem helps us work with very large powers when we only care about the remainder.

It is one of the key ideas behind modern cryptography, including RSA encryption.