Euler’s theorem is named after the great Swiss mathematician Leonhard Euler from a paper he published in 1763 containing several proofs of Fermat’s little theorem. Euler’s theorem is an attempt to find the smallest possible exponent for which Fermat’s little theorem is always true.

First, let’s take a look at Fermat’s little theorem.

If

`p`

is a prime number, then for any integer`a`

, the number`a`

- a is an integer multiple of^{p}`p`

.*a^{p}≡ a mod p For example: a = 2 p = 7 2^{7}= 128 128 - 2 = 126 = 7 * 18 If `a` is not divisible by `p`, Fermat's little theorem is equivalent to the statement that `a^{(p−1)}− 1` is an integer multiple of `p`. a^{(p - 1)}≡ 1 mod p For example: a = 2 p = 7 2^{(7-1)}- 1 2^{6}- 1 64 - 1 63 = 7 * 9

Next, let’s take a look at Euler’s theorem.

a

^{ϕ(n)}≡ 1 mod n

- It crucially connects two principles, the phi function and modular exponentiation.
`a`

and`n`

mustbe coprime!- ϕ(n) is, of course, Euler’s totient function, also known as Euler’s phi function.
- When
`n`

is prime, this is the same statement as Fermat’s little theorem (specifically, when`a`

is not divisible by`p`

)!- When
`n`

is not prime, it is used in public key cryptography algorithms like in the RSA cryptosystem!Euler’s theorem is a generalization of Fermat’s little theorem.

Let’s see some examples of substituting some values that are coprime into the statement. To make calculating the phi function simple, we’ll use prime numbers for `n`

.

a = 3 n = 17 a^{ϕ(n)}≡ 1 mod n 3^{ϕ(17)}≡ 1 mod 17 3^{16}≡ 1 mod 17 43046721 ≡ 1 mod 17 1 ≡ 1 mod 17 --- a = 13 n = 307 a^{ϕ(n)}≡ 1 mod n 13^{ϕ(307)}≡ 1 mod 307 3^{306}≡ 1 mod 17 # The number is too big to print, we'll use `bc`: ~:$ bc <<< 13^306%307 1

## Euler’s Theorem in Action

So, what’s the point of this? Well, Euler’s theorem can be used to easily reduce modular exponentiation with large exponents (and to exponents smaller than `n`

if `n`

is prime)!

For example:

13^{5921} mod 19

Substitute ϕ(n) for the large exponent. Recall that

`a`

and`n`

must be coprime!13

^{ϕ(19)}≡ 1 mod 19 13^{18}≡ 1 mod 19Use ϕ(19) to reduce the large exponent 5921 into its component parts.

5921 = 18(328) + 17 Divisor = 18 Quotient = 328 Remainder = 17

Use the component parts to rewrite the statement.

# Recall that n

^{(a*b)}= n^{ab}. 13^{(18*328+17)}mod 19 = 13^{18328}* 13^{17}mod 19Calculate!

13

^{18328}* 13^{17}mod 19 # Recall Euler's theorem, i.e., a^{ϕ(n)}≡ 1 mod n: 13^{ϕ(19)}≡ 1 mod 19 13^{18}≡ 1 mod 19 # So, we can simply replace 13^{18}with 1! 13^{18328}mod 19 = 1^{328}mod 19 13^{18328}≡ 1^{328}mod 19 1^{328}* 13^{17}mod 19 # And since 1^{k}=1, the large exponent 328 can then # be reduced to 1. 1 * 13^{17}mod 19 13^{17}mod 19 3

Of course, this can be easily verified using `bc`

:

```
bc <<< 13^5921%19
```

## Euler’s Theorem and Public Key Cryptography

Neat! And this theorem has even more practical applications, as mentioned earlier, particularly with RSA in the field of cryptography.

As is now known, Euler’s theorem ties together ϕ(n) (the phi function) and modular exponentiation.

The keys generated by RSA depend on the phi function, the result of which can only be deduced by the prime factorization of the modulus

`n`

, which is computationally infeasible given a large enough composite number.Further, the choice of the public key

`e`

can only be reproduced knowing the prime numbers, which again is tied directly to ϕ(n).`e`

must be coprime to ϕ(n)`e`

must be between 1 and ϕ(n), i.e.,`1 < e ϕ(n)`

Lastly, the private key

`d`

can only be reproduced knowing the public key`e`

and calculating its modular multiplicative inverse, again infeasible without knowing the initial prime numbers on which ϕ(n) depends!- d*e = 1 mod ϕ(n)

I’ve done a post on the RSA algorithm which explains this last section in greater depth.

* Definitions and examples taken from the Wikipedia article on Fermat’s little theorem.