Table of content
(► Examiners comments)
Proving Euler's Totient Theorem
(►A. Aim)
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 theorem^{1} 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 function^{2}, 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, 3^{4} = 81 ≡1(mod 10).
Also, if n = 15 and a = 2 we see that 2^{8} = 256 ≡ 1 (mod 15).
Euler’s totient theorem is a generalization of Fermat’s little theorem^{3} and works for all n relatively prime to a. Fermat’s little theorem only works for a and p relatively prime
where p is itself prime and states:
a^{p} ≡ a (mod p)
or
a^{p-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.
RTP: a^{p} ≡ 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 a^{p-1} from the left hand side
Giving a^{p-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
a^{p-1} ≡ 1 (mod p)
or
a^{p} ≡ 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 ba ≡ ca (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.
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 theorem^{4}.
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, n_{1}, n_{2}...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 an_{1} x an_{2} x ... x an_{Φn} } ≡ { 1 x n_{1} x n_{2} 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 n_{1} x n_{2} x ... x n_{Φn} } ≡ { 1 x n_{1} x n_{2} x ... x n_{Φn }} (mod n)
If we then divide through by { 1 x n_{1} x n_{2} 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.
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 system^{5}, whose protection revolves around large prime numbers raised to large powers being difficult to factorize.
(►D. Reflection. Linking mathematical ideas)
This theorem may not be Euler’s most elegant piece of mathematics (my personal the favorite is his proof of the two square theorems by infinite descent) or at the time seemed as his most important piece of work at the time but this, in number theory at least, is probably his most useful piece of mathematics to the world today.
This proof has given me a chance to link up some of the work I have done in the largely separate discrete mathematics and sets relations and group options. These two options appear to me to be the purest sections of mathematics that I have studied but are for whatever reason seldom linked in class, this project has allowed me to explore the links between them and use knowledge from one in relation to the other, broadening my view of maths.
(►A. Conclusion. ►C. Personally involved.)