Euler's Totient Function

Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n, written using the Greek letter phi as phi(n) and also called Euler's phi function. Equivalently it counts the integers k from one to n whose greatest common divisor with n equals one, sometimes called the totatives of n; for example the totatives of nine are one, two, four, five, seven and eight, so phi of nine equals six, while phi of one equals one since one is its own only totative. The function is multiplicative, meaning that phi of the product of two relatively prime numbers equals the product of their individual phi values, and it gives the order of the multiplicative group of integers modulo n, which is also used in defining the RSA encryption system.