Manuel Kauers Hagenberg, June 14, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 11

Exercise 1 If n, m ∈ ℤ are coprime, then

φ(nm) = φ(n) · φ(m).

Let n, m ∈ ℤ be coprime. Then the ideals (n), (m) ⊴ ℤ are coprime, because the Euclidean algorithm asserts the existence of numbers a, b ∈ ℤ with

an + bm = gcd(n, m) = 1.

Now, by the Chinese remainder theorem,

ℤ/(n) ∩ (m) ≅ ℤ/(n) × ℤ/(m).

If these rings are isomorphic, then in particular also their multiplicative groups are:

(ℤ/(n) ∩ (m))^{∗} ≅ (ℤ/(n))^{∗} × (ℤ/(m))^{∗}.

Observing that (n) ∩ (m) = (nm) and that for every N ∈ ℤ,

φ(N) = |{ k ∈ [N] : k ⊥ N }| = |(ℤ/(N))^{∗}|

(again by Euclid) completes the proof.

Exercise 2 For all n ∈ ℕ,

φ(n) = n · ∏_{{p|n \atop p prime}}(1 − \frac{1}{p}) .

Let N = p_{1}^{e_{1}} … p_{r}^{e_{r}} be a prime decomposition of N. For every prime p_{i}, we obviously have

φ(p_{i}^{e_{i}}) = |(ℤ/(p_{i}^{e_{i}}))^{∗}| = p_{i}^{e_{i}} − p_{i}^{e_{i}}/p_{i} = p_{i}^{e_{i}−1}(p_{i} − 1).

Furthermore, p_{i}^{e_{i}} ⊥ p_{j}^{e_{j}} for i ≠ j. Iterated application of Exercise 1 gives

∏_{i=1}^{r} φ(p_{i}^{e_{i}}) = ∏_{i=1}^{r} p_{i}^{e_{i}−1}(p_{i} − 1) = ∏_{i=1}^{r} p_{i}^{e_{i}}(1 − 1/p_{i}) = n ∏_{i=1}^{r} (1 − \frac{1}{p_{i}} ) .

Exercise 3 For all n ∈ ℕ,

n = ∑_{d|n} φ(d).

Write n = p_{1}^{e_{1}} … p_{r}^{e_{r}}. We proceed by induction on r. For r = 0, we have n = 1 and

∑_{d|1} φ(d) = φ(1) = 1.

Suppose the claim holds for r ∈ ℕ, i.e. for all n ∈ ℕ with at most r different prime factors. Let n be such a number, p be a “new” prime, and e ∈ ℕ. We prove the claim for np^{e}. First,

∑_{d|np^{e}} φ(d) = ∑_{d|n} ∑_{i=1}^{e} \underbrace{φ(dp^{i})}_{φ(d)φ(p^{i})} = \underbrace{∑_{d|n} φ(d)}_{=n} · ∑_{i=0}^{e} φ(p^{i}).

Concerning the last sum, we find

∑_{i=0}^{e} φ(p^{i}) = 1 + ∑_{i=1}^{e} p^{i}(1 − 1/p) = 1 + ∑_{i=1}^{e} (p^{i} − p^{i−1}) = 1 + p^{e} − 1 = p^{e}.

Putting things together, we obtain

∑_{d|np^{e}} φ(d) = np^{e},

as required.