Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer n {\displaystyle n} that are relatively prime to n {\displaystyle n} . It is written using the Greek letter phi 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 {\displaystyle k} in the range 1 ≤ k ≤ n {\displaystyle 1\leq k\leq n} for which the greatest common divisor gcd ( n , k ) {\displaystyle \gcd(n,k)} is equal to 1. The integers k {\displaystyle k} of this form are sometimes referred to as totatives of n {\displaystyle n} . For example, the totatives of n = 9 {\displaystyle 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 {\displaystyle \gcd(9,3)=\gcd(9,6)=3} and gcd ( 9 , 9 ) = 9 {\displaystyle \gcd(9,9)=9} . Therefore, φ ( 9 ) = 6 {\displaystyle \varphi (9)=6} . As another example, φ ( 1 ) = 1 {\displaystyle \varphi (1)=1} since for n = 1 {\displaystyle n=1} the only integer in the range from 1 to n {\displaystyle n} is 1 itself, and gcd ( 1 , 1 ) = 1 {\displaystyle \gcd(1,1)=1} . Euler's totient function is a multiplicative function, meaning that if two numbers m {\displaystyle m} and n {\displaystyle n} are relatively prime, then φ ( m n ) = φ ( m ) φ ( n ) {\displaystyle \varphi (mn)=\varphi (m)\varphi (n)} . This function gives the order of the...