2
$\begingroup$

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!

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.