**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 ≤ *k* ≤ *n* 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 Function: History, 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":

... 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 ...

... 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 ...

...

**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 ...

... 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 ...

... 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)