Euler’s Totient Function (also called the phi function) counts the totatives of n: positive integers less than or equal to n that are relatively prime to n. In other words, it’s the simple count of how many totatives are in the set {1, 2, 3, …, n}.
It is denoted by either φ(n) or Φ(n).
What are Totatives?
Totatives are positive integers smaller than a certain number n, but relatively prime to n. Two numbers are relatively prime if they one share “1” as a common factor.
Although Leonhard Euler invented the phi function, the word “totative” was coined by James Sylvester in 1879. It’s unclear why he chose that particular word; It’s likely he made it up from the Latin stem word tot, which means “so many” (Joyce, 2006) or perhaps as a combination of “total” and “quotient” (Turner, 2008).
How to Calculate The Phi Function
A simple (but a little tedious) way to perform the calculation by hand is:
- Write down all of the numbers in the set.
- Delete the numbers that share any common factor greater than 1.
As an example, let’s say the number in the set is n = 30.
Step 1: Write out the numbers:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}.
Step 2: Delete any numbers with factors greater than 1. The number 30 has the following factors: 1, 2, 3, 5, 6, 10, 15, 30.
- Starting with “2”, delete any multiples of two from the list, leaving:
{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29}. - Next, delete any multiples of three from the list:
{1, 5, 7, 11, 13, 17, 19, 23, 25, 29}. - Then 5:
{1, 7, 11, 13, 17, 19, 23, 29}. - Then 6:
{1, 7, 11, 13, 17, 19, 23, 29}. - Next: 10:
{1, 7, 11, 13, 17, 19, 23, 29}. - Then: 15:
{1, 7, 11, 13, 17, 19, 23, 29}. - Finally: 30:
{1, 7, 11, 13, 17, 19, 23, 29}.
Euler’s totient for n = 30 is the last set (8).
You may notice that for the last few steps, the set remained unchanged. If you know your primes, you can slip a few steps by only testing primes less than or equal to the square root of n. The square root of 30 is 5.477, so you only actually need to test the numbers 2, 3, and 5.
Uses for Euler’s Totient
Euler’s totient function is an arithmetic function, which means that it draws from the set of real numbers and maps to the set of complex numbers. They are particularly useful for investigating properties of natural numbers, including primes.
Euler’s totient function has few real-life uses (for example, you probably won’t use one in applied science). However, one are where it is used is in public key cryptography.
References
Joyve, D. (2006). Math 126 Number Theory. Retrieved December 12, 2019 from: https://mathcs.clarku.edu/~djoyce/ma126/meeting18.pdf
Sylvester, J. (1879). On Certain Ternary Cubic Form Equations, Amer. J. Math. 2 pp 280-285, 357-393
Turner, C. (2008). Euler’s Totient Function and Public Key Cryptography. Retrieved December 12, 2019 from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.574.3949&rep=rep1&type=pdf