Probabilistic approach to the Euler totient function

Euler’s totient function, \( \varphi(n) \) is a well-known arithmetic function from number theory. For any \(n \in \mathbb{N} \), \( \varphi(n) \) is defined to be the number of integers \( k \) in the range \( 1 \leq k \leq n \) for which \( \gcd(n, k) = 1 \). There is a formula for computing \( \varphi(n) \):

\( \varphi(n) = n \displaystyle\prod_{p|n} (1 – \frac{1}{p}), \)

where the product is taken over all the distinct primes \( p \) dividing \( n \). This formula can be proved in a few ways. One rests on the fact that \( \varphi(n) \) is multiplicative. Another uses an elaborate form of inclusion-exclusion. The one I am presenting now is based on probability.

Suppose we fix a positive integer \( n \) and choose uniformly at random an integer \( k \) in the range  \( 1 \leq k \leq n \). What is the probability that \( \gcd(n, k) = 1 \)? We answer this question in two ways. On one hand, we know by definition that there are \( \varphi(n) \) successful outcomes and \( n \) total outcomes, so the probability is equal to \( \frac{\varphi(n)}{n} \). On the other hand, we proceed more constructively. In order for the integer \( k \) to be relatively prime to \( n \), it is necessary and sufficient for each prime divisor \( p \) of \( n \) that \( k \) must not be divisible by \( p \).

The probability that \( k \) is divisible by \( p \) is \( \frac{1}{p} \). Hence, the probability that \( k \) is not divisible by \( p \) is \( 1 – \frac{1}{p} \). Furthermore, for distinct primes \( p \) and \( q \), the events that \( k \) is not divisible by \( p \) and \( k \) is not divisible by \( q \) are mutually independent. (More precisely, the events that \( a \) and \( b \) are not both divisible by \( u \) and \( a \) and \( b \) are not both divisible by \( v \), for relatively prime integers \( u \) and \( v \), are mutually independent.)

Thus, the probability that \( k \) is relatively prime to \( n \) is

\( \displaystyle \prod_{p|n} \left(1 – \frac{1}{p}\right). \)

Equating our two results, we have

\( \displaystyle\frac{\varphi(n)}{n} = \displaystyle\prod_{p|n}(1-\frac{1}{p}).\)

In other words,

\( \varphi(n) = n \displaystyle\prod_{p|n}(1-\frac{1}{p}). \, \spadesuit \)

We’ll use a similar approach in the future to show that the probability of choosing uniformly at random a pair of relatively prime integers is \( \frac{1}{\zeta(2)}. \)

Leave a Reply