Let varphi(n) denote the number of natural numbers ≤ n that…

Let $\varphi(n)$ denote the number of natural numbers $\le n$ that are relatively prime to $n$. Prove that \[ \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right), \] where the product is taken over all prime divisors $p$ of $n$.

Step 1: A probability model

Choose $X$ uniformly from $\{1,\dots,n\}$: each number has probability $\frac1n$. Then

\[ P(X \text{ is relatively prime to } n) = \frac{\varphi(n)}{n}. \]

Let $p_1,\dots,p_s$ be the different primes dividing $n$. A number is relatively prime to $n$ exactly when it is divisible by none of $p_1,\dots,p_s$ (any common divisor greater than $1$ would have a prime factor dividing $n$).

Step 2: $P(D_p) = 1/p$

Let $D_i$ = "$p_i$ divides $X$". Because $p_i$ divides $n$, the multiples of $p_i$ in $\{1,\dots,n\}$ are $p_i, 2p_i,\dots,n$ — exactly $n/p_i$ numbers. So

\[ P(D_i) = \frac{n/p_i}{n} = \frac{1}{p_i}. \]

Step 3: The events $D_i$ are independent

For any selection of different primes $p_{i_1},\dots,p_{i_j}$: a number is divisible by all of them exactly when it is divisible by their product $d=p_{i_1}\cdots p_{i_j}$ (different primes). Since $d$ divides $n$, there are $n/d$ multiples of $d$ in $\{1,\dots,n\}$:

\[ P(D_{i_1}\cdots D_{i_j}) = \frac{1}{p_{i_1}\cdots p_{i_j}} = P(D_{i_1})\cdots P(D_{i_j}). \]

This holds for every selection, which is exactly the definition of (mutual) independence.

Step 4: The complements are independent too

If events are independent, so are their opposite events. Hence

\[ \frac{\varphi(n)}{n} = P\big(\overline{D_1}\,\overline{D_2}\cdots\overline{D_s}\big) = \prod_{i=1}^{s}P(\overline{D_i}) = \prod_{i=1}^{s}\left(1-\frac{1}{p_i}\right). \]

Multiplying by $n$:

\[ \boxed{\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).} \quad\blacksquare \]

Step 5: The same proof written with inclusion–exclusion

Without the word "independent": the numbers not relatively prime to $n$ are those in $D_1+\dots+D_s$. By inclusion–exclusion,

\[ \varphi(n) = n - \sum_i\frac{n}{p_i} + \sum_{i\lt j}\frac{n}{p_ip_j} - \dots + (-1)^s\frac{n}{p_1\cdots p_s} = n\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_s}\right), \]

since multiplying out the product produces exactly these terms.

Step 6: Examples

Note that repeated prime factors do not matter: $\varphi(8)=8\cdot\frac12=4$ (the odd numbers $1,3,5,7$).