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
Famous quotes containing the word function:
“As a medium of exchange,... worrying regulates intimacy, and it is often an appropriate response to ordinary demands that begin to feel excessive. But from a modernized Freudian view, worrying—as a reflex response to demand—never puts the self or the objects of its interest into question, and that is precisely its function in psychic life. It domesticates self-doubt.”
—Adam Phillips, British child psychoanalyst. “Worrying and Its Discontents,” in On Kissing, Tickling, and Being Bored, p. 58, Harvard University Press (1993)