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: φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6, = φ(9) = 6, φ(10) = 4, φ(11) = 10, φ(12) = 4, φ(13) = 12, etc., do not appear to follow any law. But there is a formula discovered by Euler to which we shall turn shortly. In one special case the formula is really simple: for prime p, φ(p) = p - 1. This is why the Euler's Theorem is indeed a generalization of Fermat's.

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 {m1, m2, ..., mφ(m)} of the remainders of division by m coprime to m. In exactly the same manner as before, multiplication by a results in a permutation (but now) of the set {m1, m2, ..., mφ(m)}. Therefore, two products are congruent:

m1m2 ... mφ(m) = (am1)(am2) ... (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 φ(pa), where p is prime.

Next, we establish the multiplicative property of φ:

(1)

φ(m1m2) = φ(m1)φ(m2)

for coprime m1 and m2.

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

(2)

m = p1a1p2a2 ... pkak,

with distinct pi'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

φ(pa) = pa - pa-1 = pa-1(p - 1) = pa(1 - 1/p).

Indeed, below pa, there are pa-1 - 1 integers divisible by p and hence having common factors with pa. These are 1p, 2p, ..., (pa-1 - 1)p. The total of positive integers below pa and coprime to it is then (pa - 1) - (pa-1 - 1).

To prove the second part, assume m = m1m2, 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 φ(m1) and φ(m2). Let 0 ≤ n < m be coprime to m. Find remainders n1 and n2 of division of n by m1 and m2, respectively:

(3)

n = n1 (mod m1) and n = n2 (mod m2).

Obviously, n1 is coprime to m1 and n2 is coprime to m2. Furthermore, n defines n1 and n2 uniquely. Assume now that n1 and n2 (coprime to m1 and m2, 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) = φ(p1a1)φ(p2a2) ... φ(pkak) = p1a1(1 - 1/p1)p2a2(1 - 1/p2)...pkak(1 - 1/pk)

which simplifies to

φ(m) = m(1 - 1/p1)(1 - 1/p2)...(1 - 1/pk)

References

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

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

Copyright © 1966-2016 Alexander Bogomolny

71471808