Euler's Totient Function

Euler's Totient Function

In number theory, Euler's totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ kn for which gcd(n, k) = 1. The totient function is a multiplicative function, meaning that if two numbers m and n are relatively prime (to each other), then φ(mn) = φ(m)φ(n).

For example let n = 9. Then gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. The other six numbers in the range 1 ≤ k ≤ 9, that is, 1, 2, 4, 5, 7 and 8, are relatively prime to 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since gcd(1, 1) = 1.

The totient function is important mainly because it gives the order of the multiplicative group of integers modulo n (the group of units of the ring ). See Euler's theorem.
The totient function also plays a key role in the definition of the RSA encryption system.

Read more about Euler's Totient FunctionHistory, Terminology, and Notation, Some Values of The Function, Euler's Theorem, Other Formulae Involving φ, Generating Functions, Growth of The Function, Ratio of Consecutive Values, Ford's Theorem

Other articles related to "totient, totients, totient function, function":

Perfect Totient Number
... In number theory, a perfect totient number is an integer that is equal to the sum of its iterated totients ... That is, we apply the totient function to a number n, apply it again to the resulting totient, and so on, until the number 1 is reached, and add together the resulting sequence of ... Or to put it algebraically, if where is the iterated totient function and c is the integer such that then n is a perfect totient number ...
Jordan's Totient Function
... In number theory, Jordan's totient function of a positive integer n is the number of k-tuples of positive integers all less than or equal to n that form a coprime (k + 1)-tuple ... This is a generalisation of Euler's totient function, which is J1 ... The function is named after Camille Jordan ...
Highly Cototient Number - Primes
... Totient function Euler's totient function Jordan's totient function Nontotient Noncototient Highly totient number Sparsely totient number Highly cototient number Prime number classes By formula ...
Sparsely Totient Number
... In mathematics, a sparsely totient number is a certain kind of even natural number ... A natural number, n, is sparsely totient if for all m > n, φ(m)>φ(n), where φ is Euler's totient function ... The first few sparsely totient numbers are For example, 18 is a sparsely totient number because φ(18) = 6, and any number m > 18 falls into at least one of the following classes m has a prime ...
Carmichael's Totient Function Conjecture
... In mathematics, Carmichael's totient function conjecture concerns the multiplicity of values of Euler's totient function φ(n), which counts the number of integers less than and coprime to n ...

Famous quotes containing the word function:

    It is not the function of our Government to keep the citizen from falling into error; it is the function of the citizen to keep the Government from falling into error.
    Robert H. [Houghwout] Jackson (1892–1954)