# Euler Function and Theorem

Euler's generalization of the Fermat's Little Theorem depends on a function which indeed was invented by Euler (1707-1783) but named by J. J. Sylvester (1814-1897) in 1883. I never saw an authoritative explanation for the name *totient* he has given the function. In Sylvestor's opinion mathematics is essentially about seeing "differences in similarity, similarity in difference." The word *totient* rhymes with *quotient* and the function has to do with division but in an unusual way. (Scott Brodie brougt to my attention that the Oxford English Dictionary brings up the latin root *tot* for adding up, total. Tot has also the meaning (of unkown origin) of a small child or a small drink. It would be very much in the spirit of the above maxim to use the word with two so different meanings. You could expect this from Sylvester whom E. T. Bell has christened hothead.)

The Euler's totient function φ for integer m is defined as the number of positive integers not greater than and coprime to m. A few first values:

### Euler's Theorem

Let a and m be coprime. Then a^{φ(m)} = 1 (mod m).

### Proof

The proof is completely analogous to that of the Fermat's Theorem except that instead of the set of non-negative remainders {1,2,...,m-1} we now consider the set _{1}, m_{2}, ..., m_{φ(m)}}_{1}, m_{2}, ..., m_{φ(m)}}.

m_{1}m_{2} ... m_{φ(m)} = (am_{1})(am_{2}) ... (am_{φ(m)}) (mod m)

dividing by the left-hand side proves the theorem.

The derivation of the Euler's formula for φ(m) proceeds in two steps. First, we consider the next simplest case φ(p^{a}), where p is prime.

Next, we establish the *multiplicative* property of φ:

(1)

φ(m_{1}m_{2}) = φ(m_{1})φ(m_{2})

for coprime m_{1} and m_{2}.

Since any integer can be (uniquely) represented in the form

(2)

m = p_{1}^{a1}p_{2}^{a2} ... p_{k}^{ak},

with distinct p_{i}'s, these two steps combined will lead to a closed form expression for φ.

### Lemma 1

Let p be prime and a>0, an integer. Then
φ(p^{a}) = p^{a} - p^{a-1} = p^{a-1}(p - 1) = p^{a}(1 - 1/p).

Indeed, below p^{a}, there are ^{a-1} - 1^{a}. These are ^{a-1} - 1)p^{a} and coprime to it is then ^{a} - 1) - (p^{a-1} - 1).

To prove the second part, assume m = m_{1}m_{2}, where the two factor are coprime. We wish to relate the number φ(m) of the remainders of division by m coprime to m to the similarly defined quantities φ(m_{1}) and φ(m_{2}). Let _{1} and n_{2} of division of n by m_{1} and m_{2}, respectively:

(3)

n = n_{1} (mod m_{1}) and n = n_{2} (mod m_{2}).

Obviously, n_{1} is coprime to m_{1} and n_{2} is coprime to m_{2}. Furthermore, n defines n_{1} and n_{2} uniquely. Assume now that n_{1} and n_{2} (coprime to m_{1} and m_{2}, respectively) are given. Then the Chinese Remainder Theorem yields a unique n such that (3) holds. This proves (1).

All that remains is to finally derive the Euler's formula for φ(m). Let m be given by (2). Applying the multiplicative property repeatedly we get

φ(m) = φ(p_{1}^{a1})φ(p_{2}^{a2}) ... φ(p_{k}^{ak}) = p_{1}^{a1}(1 - 1/p_{1})p_{2}^{a2}(1 - 1/p_{2})...p_{k}^{ak}(1 - 1/p_{k})

which simplifies to

φ(m) = m(1 - 1/p_{1})(1 - 1/p_{2})...(1 - 1/p_{k})

### References

- J.H. Conway and R.K. Guy,
*The Book of Numbers*, Springer-Verlag, NY, 1996. - H.D avenport,
*The Higher Arithmetic*, Harper&Brothers, NY - R. Graham, D. Knuth, O. Patashnik,
*Concrete Mathematics*, 2nd edition, Addison-Wesley, 1994. - P. Hilton, D. Holton, J. Pederson,
*Mathematical Reflections*, Springer-Verlag, 1997 - Oystein Ore,
*Number Theory and Its History*, Dover Publications, 1976

- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1966-2016 Alexander Bogomolny

65265721 |