Euler’s totient function

Euler’s totient function counts the number of positive integers up to a given integer $n$ that are coprime to $n$. In other word, the number of integers $k$ in the range $1 \le k \le n$ for which the greatest common divisor $\gcd(n, k) = 1$. The function is written using the Greek letter phi as $\varphi(n)$ or $\phi(n)$ and is often called Euler’s phi function.

An simple implementation of Euler’s totient function in Python is shown below:

import math

def phi(n):
    amount = 0

    for i in range(1, n + 1):
        if math.gcd(n, i) == 1:
            amount += 1

    return amount

Applications

One of the applications of Euler’s totient function is the RSA algorithm. Setting up a RSA system involves choosing large prime numbers $p$ and $q$, computing $n = p \cdot q$ and $\varphi(n)$. Because $p$ and $q$ are both prime numbers, $\varphi(n)$ can quickly be calculated: $\varphi(n) = (p - 1)(q - 1)$.

Examples

If we have the product of two primes $n = p \cdot q = 37 \cdot 73 = 2701$, then we can compute $\varphi(n)$ as

$$\varphi(n) = (p - 1)(q - 1) = 36 \cdot 72 = 2592$$