4 min read

On Euler's Theorem

July 15, 2018

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.

Fermat’s little theorem

If p is a prime number, then for any integer a, the number ap - a is an integer multiple of p.*

ap ≡ a mod p

For example:
  a = 2
  p = 7

  27 = 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
  26 - 1
  64 - 1
  63 = 7 * 9

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

Euler’s theorem

aϕ(n) ≡ 1 mod n

  • It crucially connects two principles, the phi function and modular exponentiation.
  • a and n must be 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
316 ≡ 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
3306 ≡ 1 mod 17
# The number is too big to print, we'll use `bc` on the command line:
$ 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:

135921 mod 19

  1. Substitute ϕ(n) for the large exponent. Recall that a and n must be coprime!

     13ϕ(19) ≡ 1 mod 19
 1318 ≡ 1 mod 19

  2. Use ϕ(19) to reduce the large exponent 5921 into its component parts.

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

  3. Use the component parts to rewrite the statement.

     # Recall that n(a*b) = nab.
 13(18*328+17) mod 19 = 1318328 * 1317 mod 19

  4. Calculate!

     1318328 * 1317 mod 19

 # Recall Euler's theorem, i.e., aϕ(n) ≡ 1 mod n:
 13ϕ(19) ≡ 1 mod 19
 1318 ≡ 1 mod 19

 # So, we can simply replace 1318 with 1!
 1318328 mod 19 = 1328 mod 19
 1318328 ≡ 1328 mod 19
 1328 * 1317 mod 19

 # And since 1k=1, the large exponent 328 can then
 # be reduced to 1.
 1 * 1317 mod 19
 1317 mod 19
 3

Of course, this can be easily verified using bc:

$ bc <<< 13^5921%19
3

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.

  1. 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.

  2. 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)

  3. 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.