Euler's totient function

From Simple English Wikipedia, the free encyclopedia
Jump to navigation Jump to search
The first thousand values of

In number theory, the totient of a positive integer n is the number of positive integers smaller than n which are coprime to n (they share no factors except 1). It is often written as .

For example, , because there are four numbers (1, 3, 5 and 7) which do not share any factors with 8. The function used here is the totient function,[1][2] usually called the Euler totient or Euler's totient, after the Swiss mathematician Leonhard Euler, who studied it. The totient function is also called Euler's phi function or simply the phi function,[3] since the Greek letter Phi () is so commonly used for it. The cototient of n is defined as .

The totient function is important mainly because it gives the size of the multiplicative group of integers modulo n. More precisely, is the order of the group of units of the ring . This fact, together with Lagrange's theorem, provides a proof for Euler's theorem.

A common use of the totient function is in the RSA algorithm. The RSA algorithm is a popular method of encryption used worldwide.

For any prime number, p, .

Related pages[change | change source]

References[change | change source]

  1. "Comprehensive List of Algebra Symbols". Math Vault. 2020-03-25. Retrieved 2020-10-02.
  2. Weisstein, Eric W. "Totient Function". mathworld.wolfram.com. Retrieved 2020-10-02.
  3. "Euler's Totient Function and Euler's Theorem". www.doc.ic.ac.uk. Retrieved 2020-10-02.