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 {m₁, m₂, ..., 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 {m₁, m₂, ..., m_φ(m)}. Therefore, two products are congruent:

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 φ:

for coprime m₁ and m₂.

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

with distinct p_i's, these two steps combined will lead to a closed form expression for φ.

Lemma 1

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

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

Obviously, n₁ is coprime to m₁ and n₂ is coprime to m₂. Furthermore, n defines n₁ and n₂ uniquely. Assume now that n₁ and n₂ (coprime to m₁ and m₂, 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

which simplifies to

References

1. J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
2. H.Davenport, 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

On Internet

1. How PGP works

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2008 Alexander Bogomolny