Exercise (5.1).26

Show that for natural numbers $a$ and $b$:

$$ \phi([a, b]) \times \phi(\gcd(a, b)) = \phi(a) \times \phi(b)$$

where $[a, b] = LCM (a, b)$.

From Exercise (5.1).25, we have

$$ \phi(a b) = \frac{\phi(a) \times \phi(b) \times \gcd(a,b)}{\phi(\gcd(a,b))} $$

This gives us

$$ \phi(a) \times \phi(b) = \frac{\phi(a b) \times \phi(\gcd(a,b))}{\gcd(a,b)} $$

Proposition (2.22) tells us that $ab = [a,b] \times \gcd(a,b)$ for natural numbers $a,b$, and so

$$ \phi(a) \times \phi(b) = \frac{\phi([a,b] \times \gcd(a,b)) \times \phi(\gcd(a,b))}{\gcd(a,b)} $$

Applying the result of Exercise (5.1).25 again

$$ \phi(a) \times \phi(b) = \frac{\phi([a,b]) \times \phi(\gcd(a,b)) \times \gcd([a,b],\gcd(a,b))}{\phi( \gcd([a,b],\gcd(a,b)))} \times \frac{\phi(\gcd(a,b))}{\gcd(a,b)} $$

Now, $\gcd([a,b], \gcd(a,b))=\gcd(a,b)$, and so we can simplify

$$ \phi(a) \times \phi(b) = \frac{\phi([a,b]) \times \phi(\gcd(a,b)) \times \bcancel{\gcd(a,b)}}{\cancel{\phi( \gcd(a,b))}} \times \frac{\cancel{\phi(\gcd(a,b))}}{\bcancel{\gcd(a,b)}} $$

Which leaves us with the desired result

$$ \phi([a, b]) \times \phi(\gcd(a, b)) = \phi(a) \times \phi(b)$$

Exercise (5.1).25

(i) Let $\gcd(m, n) = g$. Prove that

$$ \phi (m \times n) = \frac{\phi (m) \times \phi (n) \times g}{\phi (g)} $$

(ii) Prove Proposition (5.5).

(i) Since $\gcd(m,n)=g$, this means there exist co-prime integers $a,b$ such that

$$ \begin{align} m & = ga \\ \\ n & = gb \end{align} $$

We decompose $a$ and $b$ further into factors $a'$ and $b'$ that don't share any primes with $g$ as follows;

$$ \begin{align} a & = g_a a' \\ \\ b & = g_b b' \end{align} $$

And so we have

$$ \begin{align} m & = g \times \overbrace{g_a}^{\text{prime factors of $a$ also in $g$}} \times \overbrace{a'}^{\text{prime factors of $a$ except those in $g$}} \\ \\ n & = g \times \underbrace{g_b}_{\text{prime factors of $b$ also in $g$}} \times \underbrace{b'}_{\text{prime factors of $b$ except those in $g$}} \end{align} $$

We'll use Proposition (5.9). Let $n = p_1^{k_1} \times p_2^{k_2} \times \ldots p_r^{k_r}$, where $p_i$ are distinct primes, then

$$ \phi(n) = n (1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) \ldots (1 - \frac{1}{p_r}) $$

We'll use the abbreviation $P(n)$ to mean the product of $(1-\frac{1}{p})$ over all distinct prime $p$ factors of $n$.

And so, using Proposition (5.9),

$$ \begin{align} \phi(mn) & =  mn \times P(g) \times P(a') \times P(b') \tag{i} \\ \\ & = \frac{\overbrace{m \times P(g) \times P(a')}^{\phi(m)} \times \overbrace{n \times P(g) \times P(b')}^{\phi(m)}}{P(g)} \\ \\  \phi(mn) & =  \frac{\phi(m) \times \phi(n) \times g}{\phi(g)} \tag{ii} \end{align} $$

This is the desired result.

Let's explain the labelled lines above:

• (i) The distinct prime factors of $mn$ are those in $g$, $a'$ and $b'$. The prime factors in $g_a$ and $g_b$ are accounted for in $g$.
• (ii) $\phi(g)=g \times P(g)$.

---

(ii) Proposition (5.5) states that Euler’s totient function multiplicative. For natural numbers, $m$ and $n$, provided $\gcd(m, n) = 1$,

$$\phi  (m \times n) = \phi (m) \times \phi (n)$$

The author's first solution uses the result from exercise (i) above with $g=1$ to prove the result, but that is a circular argument as the above result is derived from Proposition (5.5).

Lemma $\gcd(k,m) = \gcd(k+jm,m)$

We'll first prove that $\gcd(k,m) = \gcd(k+jm,m)$ for integers $j,k,m$. 

• Set $g =\gcd(k,m)$. This means $g$ divides both $k$ and $m$, and also any linear combination, including $g \mid k+jm$. And so, $g \mid \gcd(k+jm, m)$ which gives us $g \le \gcd(k+jm, m)$. 
• Now consider $h=\gcd(k+jm,m)$. This means $h$ divides $k+jm$ and $m$, and also any linear combination, including $k+jm - jm = k$. And so $h \mid k$. We have $h\mid k$ and $h\mid m$ and so $h\mid \gcd(k,m)$. This gives us $h \le \gcd(k,m)$.
• The above two points have given us $g \le h$ and $h \le g$. This means $g=h$, that is, $\gcd(k,m) = \gcd(k+jm,m)$.

This proof was inspired by (link).

Let's consider the numbers 1 to $mn$ arranged as an $m \times n$ array. Here $1 \le k \le m$.

$$\begin{matrix} 1 & 2 & \ldots & k & \ldots & m \\ m+1 & m+2 & \ldots & m + k & \ldots & 2m \\ 2m+1 & 2m+2 & \ldots & 2m + k & \ldots & 3m \\ \vdots & \vdots & \vdots & \vdots & \vdots &  \vdots \\ \\ (n-1)m +1 & (n-1)m +2 & \ldots & (n-1)m + k & \ldots & nm  \end{matrix}$$

Step 1: Which numbers are coprime to $m$?

We first observe that the right-most column consists of multiples of $m$ and so none of these numbers are coprime to $m$. Are there any columns that are entirely coprime to $m$?

If a number $k$ from the top row is coprime to $m$, then by definition, $\gcd(k,m)=1$. Using the Lemma above, this gives us $\gcd(k+jm, m)=1$ for some integer $j$. That is, $k$ plus some multiple of $m$ is also coprime to $m$ if $k$ is. This means that if any of the numbers in the top row from 1 to $m$ are coprime to $m$, then the entire column is coprime to $m$. By definition there are $\phi(m)$ of these numbers, and so there are $\phi(m)$ columns where all the numbers are coprime to $m$. To be clear, if a number $k$ in the top row is not coprime to $m$, that is $\gcd(k,m) \ne 1$, then no number in that column is coprime to $m$.

Step 2: Which numbers are coprime to $n$?

Our next task is to determine how many of the numbers in these columns, which are coprime to $m$, are also coprime to $n$.

We'll show the values in a column are all different modulo $n$. Let's assume two values $am +k$ and $bm+k$ are equivalent modulo $n$, where $0 \le a,b \le (n-1)$. That is, $am +k \equiv bm+k \pmod n$. This gives $am \equiv bm \pmod n$. Since $m$ and $n$ are coprime, we can cancel $m$ to give $a \equiv b \pmod n$. Since both $a$ and $b$ are less than $n$, this means $a=b$. This means that if two numbers are the same modulo $n$, they are at the same position in the column. And so the values in each column are all different modulo $n$. 

Furthermore, as there are $n$ distinct values in each column, these values modulo $n$ are the set $\{0, 1, \ldots, (n-1)\}$, though not necessarily in that order. There are, by definition, $\phi(n)$ numbers in this set that are coprime to $n$. 

If we can show $\gcd(jm+k,n)= \gcd(t, n)$, where $t$ is the smallest positive residue such that $jm+k \equiv t \pmod n$, then we can conclude there are $\phi(n)$ numbers coprime to $n$ in each column. 

• Let $g=\gcd(jm+k,n)$. This means $g \mid jm+k$ and $g\mid n$.
• Let $h=\gcd(t, n)$. This means $h\mid t$ and $h\mid n$.
• Since $jm+k=t+ns$ for some integer $s$, re-arranging we have $t=jm+k-ns$. And so $g \mid t$, because $g \mid jm+k$ and $g\mid ns$. Now, $g\mid t$ and $g\mid n$ means $g \mid h$.
• $h \mid t$ means $t \mid jm + k -ns$. Since $h \mid n$, we have $h \mid jm+k$. Now, $h \mid jm_k$ and $h \mid n$ means $h \mid g$.
• Together $g \mid h$ and $h \mid g$ means $g=h$, or $\gcd(jm+k,n)= \gcd(t, n)$.

This means that $\gcd(t,n)=1 \iff \gcd(jm_k,n)=1$. 

This means there are $\phi(n)$ numbers coprime to $n$ in each column.

Step 3: Conclusion

We have established there are $\phi(m)$ columns where every value is coprime to $m$, and that there are no values coprime to $m$ outside these columns.

We have also established that within these columns there are $\phi(n)$ values that are coprime to $n$.

And so the number of values coprime to both $m$ and $n$ is $\phi(n)\phi(m)$.

If a value is coprime to $mn$ and $\gcd(m,n)=1$ then it is coprime to both $m$ and $n$. And so the number of values coprime to $mn$ is $\phi(n)\phi(m)$, the desired result.

This video (link) helped develop this solution.

Exercise (5.1).24

Let $m$ be an even perfect number, that is $m = 2^{n - 1}(2^n - 1)$ where $2^n - 1$ is prime and $n \ge 2$.

Prove that

$$ \phi (m) = 2^{n - 1}(2^{n-1} - 1) $$

We want to show that $2^{n-1}$ and $2^n-1$ are coprime. Since $2^n-1$ is prime, and $n\ge2$, then $2^n-1 \ge 3$ is an odd prime. The only prime factor of $2^{n-1}$ is 2. This means $2^{n-1}$ and $2^n-1$ are coprime.

Having established $2^{n-1}$ and $2^n-1$ are coprime, we can use the multiplicity of $\phi$

$$ \begin{align} \phi(2^{n - 1}(2^n - 1)) & = \phi(2^{n - 1}) \times \phi (2^n - 1) \\ \\  & = 2^{n-2} \times (2^n-2) \\ \\ & = 2^{n-1} \times  (2^{n-1}-1) \end{align} $$

This is the desired result.

Exercise (5.1).23

Given that $\gcd(m, n) = 2$, prove that $\phi (mn) = 2 \phi (m) \phi (n)$.

We're given $\gcd(m,n)=2$. This means there exist coprime integers $a$ and $b$ such that $m=2a$ and $n=2b$. Because $a$ and $b$ are coprime, they share no prime factors.

Let's write the prime decomposition of $a$ and $b$,

$$ \begin{align} a & = p_1^{j_1} \times p_2^{j_2} \times \ldots \times p_r^{j_r} \\ \\ b & = q_1^{k_1} \times q_2^{k_2} \times \ldots \times q_s^{k_s} \end{align} $$

Since $a$ and $b$ don't share any prime factors, we have $p_x \ne q_y$. 

Without loss of generality, let's set $p_1=2$. This means there is no prime factor 2 in $b$.

$$ \begin{align} a & = 2^{j_1} \times p_2^{j_2} \times \ldots \times p_r^{j_r} \\ \\ b & = q_1^{k_1} \times q_2^{k_2} \times \ldots \times q_s^{k_s} \end{align} $$

And so

$$ \begin{align} m = 2a & = 2^{j_1+1} \times p_2^{j_2} \times \ldots \times p_r^{j_r} \\ \\ n = 2b & = 2 \times q_1^{k_1} \times q_2^{k_2} \times \ldots \times q_s^{k_s} \end{align} $$

We now consider $\phi$,

$$ \begin{align} \phi(mn) & = \phi \bigl( (2a)(2b) \bigr) \\ \\ & = \phi(2^2ab) \\ \\ & = \phi(2^{j_1+2} \times \underbrace{ p_2^{j_2} \times \ldots \times p_r^{j_r}}_{a/2^{j_1}}  \times \underbrace{q_1^{k_1} \times q_2^{k_2} \times \ldots \times q_s^{k_s}}_{b}) \\ \\ & = \phi(2^{j_1+2}) \times \phi(a/2^{j_i}) \times \phi(b) \tag{i} \\ \\ & = 2^{j_1 + 1} \times \phi(a/2^{j_1}) \times \phi(b) \\ \\ &=2^{j_1 + 1} \times \frac{1}{2^{j_1}} \phi(2^{j_1+1} \times a/2^{j_1}) \times \frac{1}{1} \phi(2b) \\ \\ & = 2 \times \phi(2a)\phi(2b) \\ \\ & = 2\phi(m)\phi(n) \end{align} $$

Step (i) is justified because $(2^{j_1+2})$,  $(p_2^{j_2} \times \ldots \times p_r^{j_r})$ and $(q_1^{k_1} \times q_2^{k_2} \times \ldots \times q_s^{k_s})$ are all co-prime to each other, allowing us to use the multiplicity of $\phi$.

We have shown  that $\gcd(m, n) = 2$ implies $\phi (mn) = 2 \phi (m) \phi (n)$.

Exercise (5.1).22

Prove Proposition (5.9).

Proposition (5.9) states that if $n = p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_r^{k_r}$, then

$$ \phi(n) = n \bigl( 1 - \frac{1}{p_1} \bigr) \bigl( 1 - \frac{1}{p_2} \bigr) \ldots \bigl( 1 - \frac{1}{p_r} \bigr) $$

We'll start from Proposition (5.9) which states that for $n>1$, if its prime decomposition is $n = p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_r^{k_r}$, where $p_i$ are distinct primes, then

$$  \phi(n) =  \bigl( p_1^{k_1} - p_1^{k_1-1} \bigr) \times \bigl( p_2^{k_2} - p_2^{k_2-1} \bigr) \times \ldots \times \bigl( p_r^{k_r} - p_r^{k_r -1} \bigr) $$

And so

$$ \begin{align} \phi(n) & =  \bigl( p_1^{k_1} - p_1^{k_1-1} \bigr) \times \bigl( p_2^{k_2} - p_2^{k_2-1} \bigr) \times \ldots \times \bigl( p_r^{k_r} - p_r^{k_r -1} \bigr) \\ \\ & =  p_1^{k_1}\bigl( 1 - p_1^{-1} \bigr) \times p_2^{k_2} \bigl( 1 - p_2^{-1} \bigr) \times \ldots \times p_r^{k_r}\bigl( 1 - p_r^{-1} \bigr)  \\ \\ & = \underbrace{\bigl[ p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_r^{k_r} \bigr ]}_{n} \; \bigl( 1 - \frac{1}{p_1} \bigr) \bigl( 1 - \frac{1}{p_2} \bigr) \ldots \bigl( 1 - \frac{1}{p_r} \bigr) \\ \\ & = n \bigl( 1 - \frac{1}{p_1} \bigr) \bigl( 1 - \frac{1}{p_2} \bigr) \ldots \bigl( 1 - \frac{1}{p_r} \bigr) \end{align} $$

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) $$

Exercise (5.1).20

Prove that

$$ \phi (p^kq^k) = p^{k−1}q^{k−1} \phi (p) \phi (q) $$

where $p$ and $q$ are distinct primes.

We have

$$ \begin{align} phi(p^kq^k) & = \phi(p^k) \times \phi(q^k) \\ \\ & = p^{k-1}(p-1) \times q^{k-1}(q-1) \\ \\ & = p^{k−1}q^{k−1} \phi (p) \phi (q) \end{align} $$

The last step uses $\phi(p)=p-1$.