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)}.$$