# Euler's Totient Function as a multiplication of terms

I remember once reading an interesting, simple way to prove, that $φ(a⋅b) = φ(a) φ(b)$ iff $a$ and $b$ are coprime.

The proof started with the assumption that $φ(n) = n(1−1/p_1)(1−1/p_2)…(1−1/p_r)$ and from then it followed a number of easy steps to complete the proof.

The issue is that the only way I know to arrive at the conclusion that $φ(n) =n(1−1p1)(1−1p2)…(1−1pr)$ is to first prove that the multiplicative property.

So I'm wondering, out of curiosity, how could one prove that $φ(n) =n(1−1p1)(1−1p2)…(1−1pr)$ without assuming first the multiplicative property.

I would really appreciate any help/thoughts!

• The inclusion-exclusion principle says $$\varphi(n) = \sum_{d\mid n} \mu(d) \frac{n}{d}.$$ – Daniel Fischer Jun 4 '17 at 19:42

One fairly direct and intuitive way to prove the relation is as follows.

Let $p_1, p_2, ..., p_r$ be the list of all distinct prime divisors of $n$.

In order to count the integers not larger than $n$ that are relatively prime to $n$, we may first eliminate all integers not larger than $n$ that are multiples of $p_1$, and then all multiples of $p_2$, and so on until we have eliminated all multiples of $p_r$.

The idea is that at each step, the proportion of remaining elements divisible by $p_i$ will be $1/p_i$, so that each time the set size decreases by a factor of $(1 - 1/p_i)$. Making this proportionality argument rigorous was a bit tricky so I will prove this separately and then use it to prove the main claim by induction.

Suppose $P$ is a set of primes, and $S \subset \mathbb{N}$ is a finite set with the property that for any distinct primes $p_1, p_2, ..., p_k \in P$, the number of elements of $S$ divisible by $p_1, ... p_k$ is $\frac{1}{p_1p_2...p_k}|S|$. I will call a set $S$ satisfying this property "$P$-uniform" (not standard terminology, but makes the proof cleaner).

We show that if $S$ is $P$-uniform, then for any $p \in P$, the set $S'$ consisting of all elements of $S$ not divisible by $p$ is $Q$-uniform, where $Q = P\backslash\{p\}$.

Let $p_1, ..., p_k \in Q$. Denote by $N_{a}$ the number of elements of $S$ divisible by $a$, and by $N_{a}'$ the number of elements of $S'$ divisible by $a$. Then we have $N_{p_1...p_k}'=N_{p_1...p_k}-N_{p_1...p_kp}$ because we took out all elements divisible by $p$.

Since $S$ is $P$-uniform and $p_1, ..., p_k \neq p$, we have $N_{p_1...p_k} = \frac{|S|}{p_1...p_k}$ and $N_{p_1...p_kp} = \frac{|S|}{p_1...p_kp}$.

Thus $N_{p_1...p_k}' = \frac{|S|(1-1/p)}{p_1...p_k} = \frac{|S'|}{p_1...p_k}$, proving that $S'$ is $Q$-uniform.

Now to prove the main claim, let $P_0 = \{p_1, ..., p_r\}$ be the set of all prime divisors of $n$.

Let $S_0 = \{1, 2, ..., n\}$. Then $S_0$ is $P_0$-uniform because for any distinct $p_1, ..., p_k \in P_0$, the number of elements of $S_0$ divisible by $p_1...p_k$ is $\frac{n}{p_1...p_k}$.

In general, define $S_k$ as the set of all elements of $S_{k-1}$ that are not divisible by $p_k$, and define $P_k = P_{k-1}\backslash\{p_k\}$. Assume as the inductive hypothesis that $S_{k-1}$ is $P_{k-1}$-uniform. By the above result, $S_k$ is $P_k$-uniform.

Therefore by induction, for every $k = 0, 1, ..., r$, the set $S_k$ is $P_k$-uniform.

This means that for every $k = 1, ..., r$, we have $|S_k| = |S_{k-1}|(1-1/p_k)$, because the number of elements of $S_{k-1}$ divisible by $p_k$ is $|S_{k-1}|/p_k$.

This proves the formula $|S_r| = |S_0|(1-1/p_1)...(1-1/p_r)$.

But $|S_r| = φ(n)$ since this set consists of elements not divisible by any of $p_1, ..., p_r$. And $|S_0| = n$, so this proves the claim.