Euler's totient function

In <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, Euler's totient function counts the positive integers up to a given integer n that are <a href="/facts/Relatively_prime/bnCxCXxs">relatively prime</a> to n. It is written using the Greek letter <a href="/facts/Phi/pUzerkKk">phi</a> as 
 
 
 
 φ
 (
 n
 )
 
 
 {\displaystyle \varphi (n)}
 
 or 
 
 
 
 ϕ
 (
 n
 )
 
 
 {\displaystyle \phi (n)}
 
, and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the <a href="/facts/Greatest_common_divisor/kNFvBuKl">greatest common divisor</a> gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as <a href="/facts/Totative/fYp0AnMz">totatives</a> of n.
For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1.
Euler's totient function is a <a href="/facts/Multiplicative_function/4kfolbBl">multiplicative function</a>, meaning that if two numbers m and n are relatively prime, then φ(mn) = φ(m)φ(n).
This function gives the <a href="/facts/Order_(group_theory)/Cl3tKGFg">order</a> of the <a href="/facts/Multiplicative_group_of_integers_modulo_n/IACS6cgH">multiplicative group of integers modulo n</a> (the <a href="/facts/Multiplicative_group_of_integers_modulo_n/IACS6cgH">group</a> of <a href="/facts/Unit_(ring_theory)/GJSBu8Y7">units</a> of the <a href="/facts/Ring_(algebra)/JnCUXz63">ring</a> 
 
 
 
 
 Z
 
 
 /
 
 n
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /n\mathbb {Z} }
 
). It is also used for defining the <a href="/facts/RSA_(cryptosystem)/XTzyfHuq">RSA encryption system</a>.

Euler's totient function open-in-new

Euler's totient function