Monday, 9 February 2026

Exercise (5.1).21

Prove Corollary (5.6).


Corollary (5.6) states that if the integers $m_j$ are pairwise prime then

$$ \phi (m_1 × m_2 × \ldots × m_k) = \phi (m_1) × \phi (m_2) × \ldots × \phi (m_k) $$


We will prove this by induction.

Let $S(k)$ be the statement:

$$ m_j \text{ pairwise prime } \implies  \phi (m_1 × m_2 × \ldots × m_k) = \phi (m_1) × \phi (m_2) × \ldots × \phi (m_k) $$

We need to prove the base case $S(2)$ and the inductive step $S(k) \implies S(k+1)$.


Base Case $S(2)$

The base case is

$$ m_1, m_2 \text{ pairwise prime } \implies  \phi (m_1 × m_2) = \phi (m_1) × \phi (m_2) $$

This is Theorem (5.5), and so the base case is true.


Inductive Step $S(k) \implies S(k+1)$

We assume $S(k)$, the induction hypothesis, and aim to show $S(k+1)$.

We start assuming $m_j$ all pairwise prime,

$$ \phi ( (m_1 \times m_2 \times \ldots \times m_k) \times m_{k+1}) = \phi  (m_1 \times m_2 \times \ldots \times m_k) \times \phi (m_{k+1}) $$

This is justified by $m_{k+1}$ being coprime to $(m_1 \times m_2 \times \ldots \times m_k)$.

$S(k)$ true gives us $\phi (m_1 \times m_2 \times \ldots \times m_k) = \phi (m_1) \times \phi (m_2) \times \ldots × \phi (m_k)$, and so

$$ \phi ( m_1 \times m_2 \times \ldots \times m_k \times m_{k+1}) =  \phi (m_1) \times \phi (m_2) \times \ldots × \phi (m_k) \times \phi (m_{k+1}) $$

This is $S(k+1)$ and so the induction step is proven.


By induction we have shown that if $m_j$ are pairwise prime, then

$$ \phi (m_1 × m_2 × \ldots × m_k) = \phi (m_1) × \phi (m_2) × \ldots × \phi (m_k) $$