The Theorem

27 NOV 2019

Table of content

6. Conclusion

Proving Euler's Totient Theorem

(►A. Aim)

Introduction

My interest in Euker as a mathematician was first sparked when, on completing a listener Crossword, the hidden message, "Read Euler, he is the mster of all" was revealed, so when I saw the inclusion of his name on the list of prompt words there was really no option but to go for him. Euler was a mathematician in the 18th century and is responsible for the first proofs of great many number of conjectures and problems. In number theory alone his accomplishments include prooving the two square theorem and Fermat's little theorem as well as doing a great deal of work that later led to the fisrt proof of the four square theorem. His achievement that I am going to focus on though is less well known, it is a generalisation of Fermat's little theorem that has become to be known as Euler's totient theorem.

(►A. Introduction and rationale)

The Theorem
Euler’s totient theorem1 states that for relatively prime a and n:

aΦn ≡ 1 (mod n)

(►B. Class knew about moulder arethmetic so this didn't need definition)

Where Φn is Euler’s totient function

Euler’s Totient Function

Euler’s totient function2, or Φn, is a count of the numbers that are less than n and relatively prime to n. For example, Φ10 is 4 as there are four number less than ten that are relatively prime to 10 { 1, 3, 7, 9 }, Φ11 is 10 as 11 is prime all numbers less than it is relatively prime to it and Φ6 is 2 as 1 and 5 are relatively prime to 6 but 2,3 and 4 are not.

Below is a table of the totients of the numbers up to 20.

 N Φ N 2 1 3 2 4 2 5 4 6 2 7 6 8 4 9 6 10 4 11 10 12 4 13 12 14 6 15 8 16 8 17 16 18 6 19 18 20 8

(►B. Small n in text. Condoned)

Some examples will serve to demonstrate Euler’s totient theorem.

Let n = 10 and a = 3. Note that 10 and 3 are relatively prime. From the table Φ10 = 4. Then, 34 = 81 ≡1(mod 10).

Also, if n = 15 and a = 2 we see that 28 = 256 ≡ 1 (mod 15).

Fermat’s Little Theorem

Euler’s totient theorem is a generalization of Fermat’s little theorem3 and works for all relatively prime to a. Fermat’s little theorem only works for a and p relatively prime

where p is itself prime and states:

ap ≡ a (mod p)
or
ap-1 ≡ 1 (mod p)

It is immediately apparent that this fits in with Euler’s totient theorem for primes p, as we have seen Φp, where p is a prime, is always p-1. As an introduction to Euler’s totient theorem, I shall prove Fermat’s little theorem.

Proving Fermat’s Little Theorem

RTP:                                                 ap ≡ a (mod p)

Take two numbers a and p which are relatively prime, and where p itself is prime.

Consider the set of the multiples of a { a, 2a, 3a, 4a, 5a ..... (p-1)a }

Consider the set of numbers { 1, 2, 3, 4, 5 ..... (p-1) }

If taken to the modulus p each element of the first set will be congruent to an element in the second, there will be one to one correspondence between the two sets and this is proven as lemma 1.

If we take the product of the first set { a x 2a x 3a x 4a x 5a ...... (p-1)a } and the product of the second { 1 x 2 x 3 x 4 x 5 ..... (p-1)} we can see that they are congruent to one another (as each element in the first is congruent to an element in the second)

Therefore { a x 2a x 3a x 4a x 5a ...... (p-1)a } ≡ { 1 x 2 x 3 x 4 x 5 ..... (p-1) } (mod p)

We can take out a factor of ap-1 from the left hand side

Giving ap-1 { 1 x 2 x 3 x 4 x 5 ..... (p-1) } ≡ { 1 x 2 x 3 x 4 x 5 ..... (p-1) } (mod p)

By dividing each side by { 1 x 2 x 3 x 4 x 5 ..... (p-1) } which is valid as p is prime we get

ap-1 ≡ 1 (mod p)
or
ap ≡ a (mod p)

QED.

Lemma 1: Each number in the first set must be congruent to one and only one number in the second and each number in the second set must be congruent to one and only one number in the first. This may not be obvious at first but can be proved through three logical steps.

(1)     Each number in the first set must be congruent to one of the elements in the second as all possible congruences save 0 are present, none will be congruent to 0 as a and p are relatively prime.

(2)     A number cannot be congruent to two numbers in the second set as a number can only be congruent to numbers which differ by a multiple of p, as all elements of the second set are smaller than p a number can only be congruent to one of them.

(3)     No two numbers in the first set, call them ba and ca, can be congruent to the same number in the second. This would indicate that the two numbers were congruent to each other baca (mod p) which would indicate that b ≡ c (mod p) which is not true as they are both different and less than p itself.

Therefore, through these three steps Lemma, 1 is proven.

Proving Euler’s Totient Theorem

As Fermat’s little theorem is a special case of Euler’s totient theorem (where n is prime) the two proofs are quite similar and in fact, only slight adjustments need to be made to the proof of Fermat’s little theorem to give you Euler’s totient theorem4.

RTP:                                                                        aΦn ≡ 1 (mod n)

Take two numbers, a and n which are relatively prime

Consider the set N of numbers that are relatively prime to n { 1, n1, n2...nΦn}

This set will have Φn elements (Φn is defined as the number of numbers relatively prime to n)

Consider the set aN, where each element is the product of a and an element of N { a,an1,an2... anΦn }

Each element in set aN will be congruent to an element in set N (mod n), this is followed by the same argument as in lemma 1 and so the two sets will be congruent to each other

Therefore { a x an1 x an2 x ... x anΦn } ≡ { 1 x n1 x n2 x ... x nΦn } (mod n)

By taking out a factor of aΦn from the left-hand side we get

aΦn { 1 x n1 x n2 x ... x nΦn } ≡ { 1 x n1 x n2 x ... x nΦn } (mod n)

If we then divide through by { 1 x n1 x n2 x ... x nΦn } which is valid as all elements are relatively prime to n we get:

aΦn ≡ 1 (mod n)

(►A. Complete. Achieves aim. Concise!)

QED.

Applications

Unlike some of Euler’s other work in number theory such as his proof of the two square theorem Euler’s totient theorem has very real uses and applications in the world and like much of number theory those uses are almost exclusively in the world of cryptography and cryptanalysis. Both Fermat’s little theorem and Euler’s totient theorem are used in the encryption and decryption of data, specifically in the RSA encryption system5, whose protection revolves around large prime numbers raised to large powers being difficult to factorize.