# Euler’s Totient Theorem

I first developed an interest in Euler when I was completing a listener crossword; the concealed message ‘Read Euler was the master of the crossword.’ When I first saw the inclusion of the name ‘Euler’ on the list of prompt words, I had no option but just to go for it. Euler was a famous mathematician in the eighteenth century who was acknowledged for his contribution in the mathematics discipline as he was responsible for the proof of numerous problems and conjectures. Taking number theory as an example, Euler successively played a vital role to proof two-square theorem as well as the Fermat’s little theorem (Griffiths and Peter 81). His contribution also paved the way to the proof of four-square theorem. Therefore, in this course project, I am going to focus on his theory, which is not that known to many, it is a generalization of Fermat’s little theorem that is commonly known as Euler’s theorem.

# Theorem

Euler’s totient theorem holds that if a and n are coprime positive integers; then

Given that Φn is a Euler’s totient function

# Euler’s Totient Function

Euler’s Totient Function (Φn) is the count of positive integers that are less that n and relatively prime to n. For instance, Φ10 is 4 since there are four integers, which are less than 10 and are relatively prime to 10; that is, 1, 3, 7, 9. Consequently, Φ11 is 10 since there 11 prime numbers which are less than 10 and are relatively prime to 10. The same way, Φ6 is 2 as 1 and 5 are relatively prime to 6 but 2, 3, and 4 are not.

The following table represents the totients of numbers up to twenty

 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

Some of these examples seek to prove Euler’s totient theorem.

Let n = 10 and a = 3. In this case, 10 and 3 are co-prime i.e. relatively prime. Using the provided table, it is clear that Φ10 = 4. Then this relation can also be represented as follows:

34 = 81 ≡ 1 (mode 10). Conversely, if n = 15 and a = 2. It is clear that 28 = 256 ≡ 1 (mod 15)

# Fermat’s Little Theory

According to Liskov (221), Euler’s totient theorem is a simplification to Fermat’s little theorem and does work every n that are relatively prime to a. Fermat’s little theorem only work for a and p that are relatively prime.

a p-1 ≡ 1 (mod p)

or

a p ≡ a (mod p)

where p itself is prime

It is, therefore, clear that this equation fits in the Euler’s totient theorem for every prime P, as indicated in Φp, where P is a prime and is given by p-1.

Therefore, to proof Euler’s theorem, it is vital to first proof Fermat’s little theorem.

# Proof to Fermat’s Little Theorem

As earlier indicated, the Fermat’s little theorem can be expressed as follows:

ap ≡ a (mod p)

taking two numbers; a and p that are relatively prime, where p is also prime.

The set of a {a, 2a, 3a, 4a, 5a…(p-1)a}………(i)

Consider another set of number {1, 2, 3, 4, 5….(p-1a)}……(ii)

If one decides to take the modulus for p, each element of the set (i) will be congruent to an item in the second set (ii). Thus, there will be one on one correspondence between the two sets. This can be proven as lemma 1.

Consequently, if one decides to take the product of the first set; that is {a x 2a x 3a x 4a x 5a x …. (p-1)a } as well as the product of the second set as {1 x 2 x 3 x 4 x 5… (p-1)}. It is clear that both of these set are congruent to one another; that is, each element in the first set matches to another element in the second set (Liskov 221).

Thus, the two set can be represented as follows:

{a x 2a x 3a x 4a x 5a x …. (p-1)a } ≡ {1 x 2 x 3 x 4 x 5… (p-1)} (mode p)

If one takes out the factor a p-1 from the left-hand side (L.H.S), the resultant equation will be

Ap-1 {a x 2a x 3a x 4a x 5a x …. (p-1)a } ≡ {1 x 2 x 3 x 4 x 5… (p-1)} (mode p)

If the same equation is divided by {1 x 2 x 3 x 4 x 5… (p-1)} when p is prime, one will obtain

a p ≡ a (mod p)

or

a p-1 ≡ 1 (mod p)

It should be clear that each element in the first set should correspond to another element in the second set (elements of the set are congruent). Even though this is not obvious at the first step, it can still be proved through three logical steps as follows:

1. Each element in the first set should be congruent to one element in the second set since all possible congruence saves 0 and are present; this implies that each none of the elements will be congruent to 0 as p and a are relatively prime.
2. No two numbers in the first set can be labeled as ba or ca. if this is done, some elements in the first set can be the same as those in the second set. This would imply that two numbers are congruent to each other i.e. ba ≡ ca (mod p) which would mean that b ≡ c (mod p) which is not true mathematically since both the element are divergent and less than p.
3. An element in the first set cannot be congruent to two numbers in the second set since a number can only b congruent numbers that differ by multiple of p; as an element of the second set are likely to be smaller that p a number.

Through these three rules, one can proof Fermat’s Little Theorem

# Proof of Euler’s Totient Theorem

Since the Fermat’s little theorem is a special form of Euler’s totient theorem. It follows that the two proofs provided earlier in this exploration are similar but slight adjustments needs to be made to Fermat’s little theorem to justify Euler’s totient theorem (Křížek 97). Using the equation

a Φn ≡ 1 (mod n)

Where the two number; a and n that are relatively prime. The set N of figures which are relatively prime to n {1, n1. n2….n Φn }. This set is likely to have Φn element which is defined by the number of the relatively prime number to n. The same way, the second set aN, where each and every element is a product of a as well as an element of N {a, an1, an2, an3…an Φn}.

Each element of the set aN must be congruent to another element in the set N (mode n) as noted by the earlier three rules. Thus, each element of the two sets will be congruent to each other (Giblin 111).

In this scenario case, it can be said that:

{a x an1 x an2 x an3 x …. an Φn } ≡ {a x  n1 x n2 x n3 x ….n Φn } (mod n)

By factoring out a and a Φn from the left-hand side, one can obtain the following equation

A Φn {1 x n1 x n2 x n3 x ….n Φn} ≡ {1 x n1 x n2 x n3 x ….n Φn } (mod n)

If this obtained equation is divided by {1 x n1 x n2 x n3 x ….n Φn } from both sides which are valid as all the elements in the two sets are relatively prime. The obtained equation will be as follows:

a Φn ≡ 1 (mod n)

# Application of the Euler’s Theorem

Unlike other Euler’s works in the number theory like the proof for two-square theorem and four-square theorem, the Euler’s totient theorem has real applications across the globe. The Euler’s totient theorem and Fermat’s little theorem are commonly used in decryption and encryption of data if not information especially in the RSA encryption systems which protection resolves around big prime numbers raised to large powers are hard to factorize (Wardlaw 97).

# Conclusion

In summary, this theorem may not be Euler’s most well-designed piece of mathematics; my favorite theorem is the two-square theorem by infinite descent. Even though this theorem seems to be a crucial and important piece of work at that time. Number theory is still regarded as the most useful theory in mathematics nowadays. Through this proof, I have had the opportunity to relate some of the work I have earlier done in discrete mathematics, as well as sets relation and group options. Indeed, these two options seem to be among the purest sections of mathematics that I have ever studied in mathematics. However, this exploration has enabled me to explore the relationship between Euler’s totient theorem and Fermat’s little theorem. I have also applied knowledge from one discipline to the other which I believe has broadened my view of mathematics.

# Works Cited

Giblin, P J. Primes, and Programming: An Introduction to Number Theory with Computing. Cambridge UP, 1993.

Griffiths, H B, and Peter J. Hilton. A Comprehensive Textbook of Classical Mathematics: A Contemporary Interpretation. London: Van Nostrand Reinhold Co, 1970. Internet resource.

Křížek, M., et al. 17 Lectures on Fermat Numbers: From Number Theory to Geometry. Springer, 2001.

Liskov, Moses. “Fermat’s Little Theorem.” Encyclopedia of Cryptography and Security, pp. 221-221.

Wardlaw, William P. Euler’s Theorem for Polynomials. Ft. Belvoir: Defense Technical Information Center, 1990. Print.