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

Exercise (5.1).19

Show that $\phi (2^{2k+1}) = l^2$ where $l$ is a natural number.

We have

$$ \phi(2^{2k+1}) = 2^{2k +1 -1 }(2-1) = (2^{k})^2 $$

And so, $\phi (2^{2k+1}) = l^2$ where $l=2^k$.

Exercise (5.1).18

Let $d$ be a positive divisor of $n$, that is $d \mid n$. Prove that

$$ \phi (d) \; \mid \; \phi (n)$$

Hint: Consider the prime decompositions of $d$ and $n$.

We're given $d \mid n$ and so every prime $p_i$ that appears in prime decomposition of $d$ also appears in the prime decomposition of $n$, raised to the same or higher power.

If we decompose $d$ as follows, with $p_i$ as distinct primes, and $k_i \ge 1$ natural numbers

$$ d = \prod_{i=1}^{r}p_i^{k_i} $$

then we can decompose $n$ as

$$ n = m \times \prod_{i=1}^{r}p_i^{k_i+j_i} $$

where $j_i \ge 0$, and $m$ is the remaining factor which contains no primes $p_i$. 

We now consider $\phi(d)$ and $\phi(n)$, making use of $m$ being coprime to any power of $p_i$ to use the multiplicity of $\phi$.

$$ \begin{align} \phi(d) & = \textcolor{Red}{\prod_{i=1}^{r} p_i^{k_i-1}(p-1)} \\ \\  \phi(n) & = \phi(m) \times  \prod_{i=1}^{r} p_i^{k_i + j_i -1}(p_i -1)  \\ \\ & = \phi(m) \times \textcolor{Red}{\prod_{i=1}^{r} p_i^{k_i -1}(p_i -1)} \times  p_i^{j_i} \end{align} $$

We can see $\phi(d)$ appears as a factor of $\phi(n)$ and so we can conclude

$$ \phi (d) \; \mid \phi (n) $$

Exercise (5.1).17

Prove that

$$ \phi ( \phi (p^k)) = p^{k−2} \phi [p(p− 1)] $$

where $p$ is prime and $k \ge 2$.

We proceed as follows

$$  \phi(p^k) = p^{k-1}(p-1)$$

Since $p^{k-1}$ and $(p-1)$ are coprime, we can use the multiplicity of $\phi$ 

$$ \phi(\phi(p^k)) = p^{k-2}(p-1) \phi (p-1) $$

Similarly, $p$ and $(p-1)$ are coprime, we can again use the multiplicity of $\phi$

$$ \phi(\phi(p^k)) = p^{k-2} \phi [p(p-1)] $$

Exercise (5.1).16

Disprove $ \phi (m + n) = \phi (m) + \phi (n)$ where $m$ and $n$ are natural numbers.

We will use a counter-example to disprove the statement.

Consider the smallest natural numbers $m=1$ and $n=1$. Then

$$ \begin{align} \phi(1 + 1) = \phi(2) = 1 \quad & \ne \quad 2 = 1 + 1 = \phi(1) + \phi(1) \\ \\  \phi(1 + 1) \quad & \ne \quad  \phi(1) + \phi(1) \end{align} $$

That is, $n=m=1$ is a counter-example.

Exercise (5.1).15

(i) Is it possible to have $\phi(n) \ge n$?

Give reasons for your answer.

(ii) Show that $0 < \frac{\phi (n)}{n} < 1$ for $n > 1$.

(i) $\phi(n)$ is defined to be the quantity of natural numbers from 1 to $n$, inclusive,  that are coprime to $n$. Since there are only $n$ natural numbers in this range, those coprime are less than or equal to $n$. 

However, the natural number 1 is coprime to $n$, and so that quantity, $\phi(n)$, is less than or equal to $(n-1)$, or equivalently, less than $n$.

$$ \phi(n) < n$$

This is equivalent to $\phi(n) \ge n$ being false.

(ii) Since 1 is coprime to any $n>1$ meaning $\phi(n)>0$, and since we're established $ \phi(n) < n$, then

$$ 0 < \phi(n) < n $$

Equivalently

$$ 0 < \frac{\phi (n)}{n} < 1 $$

Exercise (5.1).14

Let $p$ be prime and $p \mid n$ . Prove that

$$ \phi(n) \le \frac{n(p-1)}{p} $$

We're given $p \mid n$. This means that multiples of $p$, up to the value of $n$, are not coprime with $n$. There are $n/p$ of these multiples.

Since we don't know about any other possible factors of $n$, we can only say the quantity of numbers between 1 and $n$ that are coprime to $n$, which is $\phi(n)$, is less than or equal to $n - n/p$. 

And so

$$ \phi(n) \le n - \frac{n}{p} =  \frac{np - n}{p} = \frac{n(p-1)}{p} $$

That is

$$ \phi(n) \le \frac{n(p-1)}{p} $$

Exercise (5.1).13

Let $n = 2^{k_1} × 3^{k_2} × 5^{k_3}$.

Show that $\phi (n) = \frac{4}{15}n$.

We have

$$ \begin{align} \phi(n) & = 2^{k_1 - 1}(2-1) \times 3^{k_2 -1 }(3-1) \times 5^{k_3 - 1}(5-1) \\ \\  & = \frac{1\times 2 \times 4}{2 \times 3 \times 5}n \\ \\ & = \frac{4}{15}n \end{align}$$

Exercise (5.1).12

Give an example of a natural number $n$ such that $\phi(n) < \frac{n}{3}$.

Give reasons for your choice.

Proposition (5.9) tell us that

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

where $p_i$ are distinct primes.

We saw in the previous exercise that the inclusion of 2 and 3 as primes leads to $\phi(n) =\frac{n}{3}$.

The inclusion of any other prime reduces the size of the product because $(1-\frac{1}{p})<1$ for any prime.

If we choose to include the prime 5, then for any $n=2^a3^b5^c$ we have $\phi(n)<\frac{n}{3}$, for natural numbers $a,b,c$.

The simplest example is $n=2 \times 3 \times 5 = 30$. 

As a check $\phi(30) = (2-1) \times (3-1) \times (5-1) = 8$, which is indeed less than a third of $30$.

Exercise (5.1).11

Solve the following equations for a general $n$ such that:

(a) $ \phi(n) = \frac{n}{2} $

(b) $ \phi(n) = \frac{n}{3} $

We remind ourselves of Proposition (5.9) which states that for a natural number $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) = n \times  \biggl(1- \frac{1}{p_1}\biggr) \times \biggl(1- \frac{1}{p_2}\biggr) \times \ldots \times \biggl(1- \frac{1}{p_r}\biggr) $$

(a) We require 

$$ \frac{n}{2} =  n \times  \biggl(1- \frac{1}{p_1}\biggr) \times \biggl(1- \frac{1}{p_2}\biggr) \times \ldots \times \biggl(1- \frac{1}{p_r}\biggr) $$

This is only possible with $p_1=2$ and no other primes. 

This means the general solution, for some natural number $k$, is

$$n = 2^k$$

(b) We require 

$$ \frac{n}{3} =  n \times  \biggl(1- \frac{1}{p_1}\biggr) \times \biggl(1- \frac{1}{p_2}\biggr) \times \ldots \times \biggl(1- \frac{1}{p_r}\biggr) $$

This is only possible with $p_1=2, p_2=3$ and no other primes. 

This means the general solution, for some natural numbers $j, k$, is

$$n = 2^j3^k$$

Exercise (5.1).10

(a) Determine the number of incongruent residues that have an inverse modulo 310.

(b) Show that the probability of a given residue $a \pmod {p^n}$ has a multiplicative inverse is $1 - \frac{1}{p}$ where $p$ is prime.

(a) By Proposition (3.21), a residue $a$ has an inverse modulo $n$ if and only if $\gcd(a,n)=1$

The number of incongruent residues modulo 310 which are coprime to 310 is

$$ \phi(310) = \phi(2 \times 5 \times 31) = \phi(2) \times \phi(5) \times \phi(31) = (2-1)(5-1)(31-1) = 120 $$

So there are 120 incongruent residues that have an inverse modulo 310.

(b) The probability of a given residue $a \pmod {p^n}$ has a multiplicative inverse is the same as the probability of it being coprime to $p^n$, which is

$$ \frac{\phi(p^n)}{p^n} = \frac{p^{n-1}(p-1)}{p^n} = \frac{p-1}{p} = 1 - \frac{1}{p}$$

Exercise (5.1).9

What is the probability that a number $m \in \{1, 2, 3, \ldots , 164\}$ is relatively prime to 164?

There are $\phi(164)$ numbers from 1 to 164, inclusive, that are coprime to 164.

Let's calculate this first

$$ \phi(64) = \phi(2^2 \times 41) = \phi(2^2) \times \phi(41) = 2^1(2-1) \times (41-1) = 80 $$

And so the probability is

$$ \frac{80}{164} = \frac{20}{41} \approx 0.49$$

Exercise (5.1).8

Are there any natural numbers $n$ such that $\phi (n) = n$?

The function $\phi(n)$ counts the natural numbers from 1 to $n$ which are coprime to $n$.

For $n>1$, we have $\gcd(n,n) = n \ne 1$, and so $\phi(n) < n$.

The only remaining case is $n=1$, and indeed $\phi(1)=1$.

Exercise (5.1).7

Prove that $\phi (n^m) = n^{m−1} \phi (n)$.

Let's write $n$ as its prime decomposition

$$ n = p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_z^{k_z} $$

where $p_i$ are primes, and $k_j$ are natural numbers. This means

$$ \begin{align} n^m & = p_1^{mk_1} \times p_2^{mk_2} \times \ldots \times p_z^{m k_z} \\ \\ n^{m-1} & = p_1^{(m-1)k_1} \times p_2^{(m-1)k_2} \times \ldots \times p_z^{(m-1) k_z} \end{align} $$

We have

$$ \phi (n) = p_1^{k_1-1}(p_1 - 1) \times p_2^{k_2-1}(p_2 - 1) \times \ldots \times p_z^{ k_z-1}(p_z - 1) $$

And so

$$ \begin{align} \phi(n^m) & = \phi(p_1^{mk_1}) \times \phi(p_2^{mk_2}) \times \ldots \times \phi(p_z^{m k_z})   \\ \\ & = p_1^{mk_1-1}(p_1-1) \times p_2^{mk_2 - 1}(p_2 - 1) \times \ldots \times p_z^{mk_z-1}(p_z - 1) \\ \\ & = \biggl( p_1^{(m-1)k_1} \times p_2^{(m-1)k_2} \times \ldots \times p_z^{(m-1) k_z} \biggr) \times \\ & \quad \; \biggl(  p_1^{k_1-1}(p_1 - 1) \times p_2^{k_2-1}(p_2 - 1) \times \ldots \times p_z^{ k_z-1}(p_z - 1) \biggr) \\ \\  &= n^{m−1} \phi (n) \end{align} $$

The last line is justified by noting that $(m-1)k_i + k_i -1 = mk_i - 1$.

We've shown $\phi(n^m) = n^{m−1} \phi (n)$.

Exercise (5.1).6

Show that $\phi (10^m) = 4 (10^{m−1})$ where $m$ is a natural number.

Since $\gcd(2^m, 5^m)=1$, we can use the multiplicity of $\phi$, 

$$ \begin{align} \phi(10^m) & = \phi(2^m5^m)\\ \\ & = \phi(2^m) \times \phi(5^m) \\ \\ & = 2^{m-1}(2-1) \times 5^{m-1}(5-1) \\ \\  & = 4(10^{m-1}) \end{align} $$

Exercise (5.1).5

Show that $\phi (2^n) = \frac{1}{2} (2^n)$ where $n$ is a natural number.

What does $\phi (2^n) = \frac{1}{2} (2^n)$ signify?

Using Proposition (5.4) we have

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

This is the quantity of odd numbers (not multiples of 2) from 1 to $2^n$.

Exercise (5.1).4

Show that $\phi (p^m) = \phi (p) p^{m−1}$ where $p$ is a prime and $m$ is a natural number.

We use Proposition (5.4) which says that if $p$ is prime, then $\phi(p^k) = p^{k-1}(p-1)$ where $k$ is a natural number.

We also remember that $\phi(p)=p-1$.

And so

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

Exercise (5.1).3

Find the Euler totient function $\phi (n)$ of the following numbers:

(a) $2^{1000}$ (b) $3^{1000}$ (c) $5^{1000}$ (d) $7^{1000}$

(a) Since 2 is prime, we have

$ \phi(2^{1000}) = 2^{1000-1}(2-1) = 2^{999}$

There are $2^{999}$ numbers between 1 and $2^{1000}$ which are not multiples of 2. These are odd numbers.

(b) Since 3 is prime, we have

$ \phi(3^{1000}) = 3^{1000-1}(3-1) = 2 \times 3^{999}$

There are $2 \times 3^{999}$ numbers between 1 and $3^{1000}$ which are not multiples of 3. 

(c) Since 5 is prime, we have

$ \phi(5^{1000}) = 5^{1000-1}(5-1) = 4 \times 5^{999}$

There are $4 \times 5^{999}$ numbers between 1 and $5^{1000}$ which are not multiples of 5. 

(d) Since 7 is prime, we have

$ \phi(7^{1000}) = 7^{1000-1}(7-1) = 6 \times 7^{999}$

There are $6 \times 7^{999}$ numbers between 1 and $7^{1000}$ which are not multiples of 7. 

Exercise (5.1).2

Find the Euler totient function $\phi (n)$ of the following numbers:

(a) 15 (b) 64 (c) 200 (d) 1000 (e) 1001 (f) 666

We will use Proposition (5.4), that if $p$ is prime and $k$ is a natural number then $\phi (p^k) = p^k - p^{k−1} = p^{k−1} (p− 1)$.

We will also use the multiplicative property of the Euler totient function, Theorem (5.5), that $\phi (m \times n) = \phi (m) \times \phi (n)$ provided $\gcd(m, n) = 1$.

(a) The prime decomposition of 15 is $15=3 \times 5$. Since $\gcd(3,5)=1$, we can use the multiplicity of $\phi$, 

$ \phi(15)= \phi(3) \times \phi(5) = (3-1)(5-1) = 8$

(b) Since $64=2^6$, we have

$ \phi(64) = \phi(2^6) = 2^5(2-1) = 32 $

(c) Since $\gcd(2^3, 5^2)=1$, we can use the multiplicity of $\phi$,

$ \phi(200) =  \phi(2^3 \times 5^2) = \phi(2^3) \times \phi(5^2) = 2^2(2-1) \times 5^1(5-1) = 80$

(d) Since $\gcd(2^3, 5^3)=1$, we have

$ \phi(1000) = \phi(2^3 \times 5^3) = \phi(2^3) \times \phi(5^3) = 2^2(2-1) \times 5^2(5-1) = 400 $

(e) The prime decomposition of 1001 is  $1001 = 7 \times 11 \times 13$, and so

$ \phi(10001) = \phi(7) \times \phi(11) \times \phi(13) = (7-1) \times (11-1) \times (13-1) = 720 $

(f) The prime factorisation of 666 is $666 = 2 \times 3^2 \times 37$, and so

$ \phi(666) = \phi(2) \times \phi(3^2) \times \phi(37) = (2-1) \times 3^1(3-1) \times (37-1) = 216$

Exercise (5.1).1

Determine the Euler totient function $\phi (n)$ of the following prime numbers:

(a) 13

(b) 211

(c) 311

(d) 1973

(e) 1999

(f) 2017

Let's remind ourselves of the Euler totient function. $\phi(n)$ counts the numbers from 1 to $n$ which are coprime to $n$,

For a prime $p$, all the numbers less than $p$ are coprime to $p$. In addition, a prime number is not coprime to itself. And so, for prime $p$, we have $\phi(p)=p-1$.

(a) $\phi(13) = 13-1 = 12$

(b) $\phi(211) = 211-1 = 210$

(c) $\phi(311) = 311-1 = 310$

(d) $\phi(1973) = 1973-1 = 1972$

(e) $\phi(1999)=1999-1 = 1998$

(f) $\phi(2017)=2017-1 =2016$

Exercise (4.5).16

Let $N$ be a perfect number. Prove the following:

(a) $m \times N$ where $m > 1$ is an abundant number.

(b) $\frac{N}{d}$ where $d$ is a non-trivial divisor of $N$ is a deficient number.

We remember that $\sigma(N)=2N$ for perfect $N$.

(a) Note that we can't use the multiplicity of $\sigma$ because $N$ and $m$ are not necessarily coprime.

We start by comparing the divisors of $mN$ to those of $N$

$$ \begin{align} \sigma(m N) & = \sum_{d \mid mN} d \tag{i} \\ \\ & >   m \sum_{e \mid N} e \tag{ii} \\ \\ & = m(2N)  \tag{iii} \\ \\ & = 2(mN) \end{align} $$

Let's explain each step:

(i) $\sigma(nM)$ is the sum of all the divisors of $nM$.

(ii) The divisors of $N$, each multiplied by $m$, are divisors of $mN$. However this list is a proper subset of the divisors of $mN$. For example, this list does not contain the divisors of $N$ not multiplied by $m$. And so the sum of the divisors of $mN$ is strictly greater than the sum of the divisors of $N$, each multiplied by $m$.

(iii) Since $N$ is perfect, the sum of its divisors is $2N$.

Since $\sigma(mN) > 2(mN)$, then $mN$ is abundant. 

(b) We start by comparing the divisors of $\frac{N}{d}$ and $N$

$$ \begin{align} d \times \sigma \bigl ( \frac{N}{d} \bigr ) & < \sigma(N) \tag{iv} \\ \\ & = 2N  \tag{v} \\ \\ \sigma \bigl ( \frac{N}{d} \bigr ) & < 2 \bigl ( \frac{N}{d} \bigr ) \end{align} $$

Let's explain each step:

(iv) The divisors of $\frac{N}{d}$ are all divisors of $N$. But not all divisors of $N$ are divisors of $\frac{N}{d}$, for example $N$ itself. This means the divisors of $\frac{N}{d}$ are a proper subset of the divisors of $N$. If we multiply the divisors of $\frac{N}{d}$ by $d$, the resulting set of numbers are all divisors of $N$. However, again, not all divisors of $N$ are in that set, for example 1 is not in that set, because it was multiplied by $d>1$. So the sum of divisors of $\frac{N}{d}$ multiplied by $d$ is strictly less than the sum of divisors of $N$.

(v) Since $N$ is perfect, the sum of its divisors is $2N$.

Since $\sigma \bigl ( \frac{N}{d} \bigr ) < 2 \bigl ( \frac{N}{d} \bigr )$, then $\frac{N}{d}$ is deficient. 

Note the author's solutions appear to have typos for both parts (a) and (b).

Exercise (4.5).15

Find the fallacy in the following argument:

Let $N$ be a perfect number, then $N = 2^{p−1} (2^p− 1)$ where $2^p- 1$ is prime. Hence every perfect number is even.

The flaw is at the beginning. Theorem (4.30) requires that $N$ be a perfect even number, before we can conclude it is of the form $2^{p-1}(2^p-1)$ where $(2^p-1)$ is prime.

That is:

Incorrect: Let $N$ be a perfect number, then $N = 2^{p−1} (2^p− 1)$ where $2^p- 1$ is prime.

Correct: Let $N$ be an even perfect number, then $N = 2^{p−1} (2^p− 1)$ where $2^p- 1$ is prime.

Exercise (4.5).14

Show that if $p$ is an odd prime then the even perfect number

$$ 2^{p−1}(2^p− 1) \equiv 1 \pmod 9 $$

The prime $p$ is given as odd, and so $p-1$ is even, which we can write as $2k$ for some integer $k$.

Numerical experiments suggest that $2^{p-1}$ should be congruent to 1, 4 or 7 modulo 9. We'll prove a more general version of this statement by induction.

---

Let $S(k)$ be the statement 

$$ S(k) := \quad 2^{2k} \equiv 1 \lor 4 \lor 7 \pmod 9 $$

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

Base Case $S(1)$

The base case is

$$ S(1) := \quad 2^{2 \times 1} \equiv 1 \lor 4 \lor 7 \pmod 9 $$

Since $2^2 \equiv 4 \pmod 9$, the base case is true.

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

We assume $S(k)$ and aim to show $S(k+1)$, which is

$$ S(k+1) := \quad 2^{2(k+1)} \equiv 1 \lor 4 \lor 7 \pmod 9 $$

We start with

$$  2^{2(k+1)} \equiv 4 \times 2^{2k} \pmod 9 $$

Since $S(k)$ is true, we have $2^{2k} \equiv 1 \lor 4 \lor 7 \pmod 9$. 

Let's consider each case in turn.

$$ 2^{2k} \equiv 1 \pmod 9 \implies 2^{2(k+1)} \equiv 4 \times 1 \equiv 4 \pmod 9 $$

$$ 2^{2k} \equiv 4 \pmod 9 \implies 2^{2(k+1)} \equiv 4 \times 4 \equiv 7 \pmod 9 $$

$$ 2^{2k} \equiv 7 \pmod 9 \implies 2^{2(k+1)} \equiv 4 \times 7 \equiv 1 \pmod 9 $$

And so the inductive step is true for each case.

We have shown by induction that for integer $k \ge 1$

$$ \boxed{ 2^{2k} \equiv 1 \lor 4 \lor 7 \pmod 9 } $$

---

We now consider $2^p-1$ as follows, with integer $k \ge 1$

$$ \begin{align} 2^{p-1} & \equiv 2^{2k} \pmod 9  \\ \\ 2^p & = 2 \times(2^{2k}) \pmod 9 \\ \\ 2^p -1 & \equiv 2 \times (2^{2k}) -1 \pmod 9 \end{align} $$

Now, we've established that  $ 2^{2k} \equiv 1 \lor 4 \lor 7 \pmod 9 $, so we'll consider each case in turn.

Case  $2^{2k} \equiv 1 \pmod 9$

$$  \begin {align} 2^p-1  & \equiv 2 \times (1) -1 \pmod 9 \\ \\ & \equiv 1 \pmod 9 \\ \\  2^{p-1}(2^p-1) & \equiv 1 \times 1 \pmod 9 \\ \\ & \equiv 1 \pmod 9 \end{align} $$

Case  $2^{2k} \equiv 4 \pmod 9$

$$  \begin {align} 2^p-1  & \equiv 2 \times (4) -1 \pmod 9 \\ \\ & \equiv 7 \pmod 9 \\ \\  2^{p-1}(2^p-1) & \equiv 4 \times 7 \pmod 9 \\ \\ & \equiv 1 \pmod 9 \end{align} $$

Case  $2^{2k} \equiv 7 \pmod 9$

$$  \begin {align} 2^p-1  & \equiv 2 \times (7) -1 \pmod 9 \\ \\ & \equiv 4 \pmod 9 \\ \\  2^{p-1}(2^p-1) & \equiv 7 \times 4 \pmod 1 \\ \\ & \equiv 1 \pmod 9 \end{align} $$

We've shown that in every case $2^{p-1}(2^p-1) \equiv1 \pmod 9$

---

The author's solution is simpler, which we'll set out here for practice.

We note that $2 \equiv -1 \pmod 3$. Since $p$ is odd, $p-1$ is even, and so $2^{p-1} \equiv 1 \pmod 3$. That is, for some integer $k$, we have $2^{p-1} = 3k + 1$.

We also note that $2 \times 2^{p-1} -1 = 2^p - 1 = 6k + 2 -1 = 6k + 1$. 

Combining the two expressions gives us $2^{p-1}(2^p-1) = (3k+1)(6k+1) = 18k^2 + 9k+1$. This immediately gives us $2^{p-1}(2^p-1) \equiv 1 \pmod 9$.

Exercise (4.5).13

(i) Prove that the last digit of $2^{2k}$ is either 4 or 6.

(ii) Prove that for every even perfect number the last digit is either a 6 or an 8.

Note the proposition is not true for $k=0$, so we proceed assuming $k>0$.

---

(i) The last digit of a number is congruent to that number modulo 10.

We use induction to prove the result. Let the statement $P(k)$ be the proposition

$$ P(k) := \quad 2^{2k} \equiv 4 \pmod {10} \quad \lor \quad 2^{2k} \equiv 6 \pmod {10} $$

We need to prove the base case $P(1)$, and the induction step $P(k) \implies P(k+1)$. Note the proposition is not true for $k=0$.

Base Case $P(1)$

Let's consider $k=1$

$$ 2^{2 \times 1} \equiv 2^2 \equiv 4 \pmod {10} $$

And so the base case is true.

Induction Step $P(k) \implies P(k+1)$

We assume the induction hypothesis $P(k)$.

Consider

$$ 2^{2(k+1)} \equiv 2^{2k} \times 2^2 \equiv 4N \pmod {10} $$

where $N = 2^{2k}$.

The induction hypothesis tells is that $N \equiv 4 \pmod {10}$ or $N \equiv 6 \pmod {10}$. Let's consider each case:

$$N \equiv 4 \pmod {10} \quad \implies \quad 4N \equiv 16 \equiv 6 \pmod {10}$$

$$N \equiv 6 \pmod {10} \quad \implies \quad 4N \equiv 24 \equiv 4 \pmod {10}$$

So in all cases, the induction step $P(k) \implies P(k+1)$ is true.

By induction we have shown that $2^{2k}$ is 4 or 6 modulo 10. That is, the last digit of $2^{2k}$ is either 4 or 6.

---

(ii) We recall that every even perfect number $N$ is of the form

$$N = 2^{p-1}(2^p-1)$$

where $(2^p-1)$ is prime, which also means $p$ is prime. 

Case $p$ even

We first deal with the first even perfect number, $N=6$, which corresponds to $p=2$, the only even prime. In this case, the last digit is 6, and so the statement that the last digit is 6 or 8 is true.

Case $p$ odd

We now consider even perfect numbers corresponding to $p$ odd. In this case $p-1$ is even, and so $2^{p-1}$ can be written as $2^{2k}$ for some integer $k$. We've shown above that

$$ 2^{p-1} \equiv 2^{2k} \equiv 4 \pmod {10} \quad \lor \quad 2^{p-1} \equiv 2^{2k} \equiv 6 \pmod {10}$$

Let's consider each of these cases in turn.

For $2^{p-1} \equiv 6 \pmod {10}$

$$ \begin{align} 2^{p-1} & \equiv 4 \pmod{10} \\ \\ 2^p & \equiv 8 \pmod {10} \\ \\ 2^p - 1 & \equiv 7 \pmod {10} \\ \\ 2^{p-1}(2^p-1) & \equiv 4 \times 7 \pmod {10} \\ \\  & \equiv 8 \pmod{10} \end{align} $$

For $2^{p-1} \equiv 8 \pmod {10}$

$$ \begin{align} 2^{p-1} & \equiv 6 \pmod{10} \\ \\ 2^p & \equiv 12 \pmod {10} \\ \\ 2^p - 1 & \equiv 1 \pmod {10} \\ \\ 2^{p-1}(2^p-1) & \equiv 6 \times 1 \pmod {10} \\ \\  & \equiv 6 \pmod{10} \end{align} $$

We have shown that every even perfect number, which is of the form $2^{p-1}(2^p-1)$ where $(2^p-1)$ is prime and so $p$ is prime, has a last digit of 6 or 8.

Exercise (4.5).12

(a) Show that

$$ \sigma (p^3) = (p^2 + 1) (p + 1) $$

where $p$ is prime.

(b) Show that

$$ \sigma (p^5) = (p^2 − p + 1) (p^2 + p + 1) (p + 1) $$

where $p$ is prime.

(a) By definition of the sigma function

$$ \sigma (p^3) = 1 + p + p^2 + p^3 = (p^2+1)(p+1) $$

(b) By definition of the sigma function

$$ \sigma(p^5) = 1 + p + p^2 + p^3 + p^4 + p^5 = (p + 1) (p^2 - p + 1) (p^2 + p + 1) $$

Exercise (4.5).11

Prove Proposition (4.37).

Proposition (4.37). Let the prime decomposition of a natural number $n$ be given by

$$ n = p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \ldots \times p_m^{k_m} $$

where $p_j$’s are distinct primes. Then

$$ \begin{align} \sigma(n) & = \sigma(p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \ldots \times p_m^{k_m}) \\ \\ & = \sigma(p_1^{k_1}) \times \sigma(p_2^{k_2}) \times \sigma(p_3^{k_3}) \times \ldots \times \sigma(p_m^{k_m})  \end{align} $$

We start by noting that the divisors of $n$ are of the form

$$ p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \ldots \times p_m^{a_m} $$

where $0 \le a_i \le k_i$ where $1 \le i \le m$.

The sum of all such divisors is given by the following product. To explain this further, multiplying out the brackets results in summands that represent every possible divisor of the above form.

$$ \begin{align} \sigma(n) & = (\sum_{i=0}^{k_1} p_1^i) \times (\sum_{i=0}^{k_2} p_2^i) \times (\sum_{i=0}^{k_3} p_3^i) \times \ldots \times (\sum_{i=0}^{k_m} p_m^i) \\ \\ & = \sigma(p_1^{k_1}) \times \sigma(p_2^{k_2}) \times \sigma(p_3^{k_3}) \times \ldots \times \sigma(p_m^{k_m})  \end{align}$$

This is the desired result.

Note: the author's solution incorrectly applies Proposition (4.36).

Exercise (4.5).10

Prove Proposition (4.32).

Proposition (4.32) states that

$$ p \text{ prime } \iff \sigma (p) = p + 1 $$

We need to prove both directions: 

• $ p \text{ prime } \implies \sigma (p) = p + 1 $
• $ p \text{ prime } \impliedby \sigma (p) = p + 1 $

($\implies$)

We assume $p$ is prime. That means its only divisors are $p$ and 1. The $\sigma$ function is the sum of divisors, which here is $\sigma(p) = p + 1$.

($\impliedby$)

We start with $\sigma(p)=p+1$. This tells us the divisors of $p$ sum to $p+1$. We know the divisors of $p$ include $p$ and $1$, and these sums to $p+1$. This is the value of $\sigma(p)$ and so there is no possibility for additional divisors. That is, the only divisors of $p$ are $p$ and $1$, and so, by definition, $p$ is prime.

Example (4.5).9

Prove Theorem (4.30).

Theorem (4.30) states that every even perfect number N is of the form:

$$ N = 2^{p−1}(2^p− 1) $$

where $(2^p− 1)$ is prime.

---

For additional practice, we'll first re-prove Theorem (4.28), which is the converse of Theorem (4.30):

Let $p$ be a prime number. If the Mersenne number $2^p− 1$ is prime then $N = 2^{p−1} (2^p− 1)$ is a perfect number.

We first note that $N$ is a perfect number if $\sigma(N)=2N$, and that $\sigma$ is a multiplicative function.

$$ \begin{align} \sigma(N) &= \sigma \bigl ( \; 2^{p−1} \; \underbrace{(2^p-1)}_{\text{prime}} \; \bigr) \\ \\  & = \sigma(2^{p-1}) \times \sigma(2^p-1) \\ \\ & = (1 + 2 + 2^2 + 2^3 + \ldots + 2^{p-1}) \times (2^p -1 + 1) \\ \\ & = (2^p-1)\times  2^p \\ \\ & = 2 \times 2^{p-1}(2^p-1) \\ \\ &= 2N \end{align} $$

And so we have shown that if $2^p− 1$ is prime then $N = 2^{p−1} (2^p− 1)$ is a perfect number.

---

We now prove Theorem (4.30). 

We start with $N$ as an even perfect number. This means we can write it as $N=2^{k-1}M$, where $k \ge 2$ and $M$ is odd.

Since $N$ is a perfect number, we have $\sigma(N)=2N$. Using that $\sigma$ is multiplicative, we have

$$ \begin{align} 2N & = \sigma(N) \\ \\ 2 \times 2^{k-1}M & = \sigma(2^{k-1}) \times \sigma(M) \\ \\  2^kM & = (2^k-1) \times \sigma(M) \tag{i} \end{align} $$

This tells us that $2^k \mid (2^k-1) \times \sigma(M)$, but $2^k$ and $(2^k-1)$ are coprime, it must be the case that $2^k \mid \sigma(M)$. That is, for some integer $c$ we have

$$ \sigma(M) = 2^k c $$

Substituting into (i) gives us

$$ \begin{align} 2^kM & = (2^k-1) \times 2^k c  \\ \\ M &= (2^k-1) \times c \end{align}$$

This means

$$ N = 2^{k-1} (2^k-1) \times c $$

We need to show $N=2^{p-1}(2^p-1)$, which means we need to show $c=1$.

Let's consider $M = (2^k-1) \times c$ and $\sigma(M) = 2^k c$.

$M$ has divisors $M$ and $c$. We notice that $M+c = (2^k-1) \times c) + c = 2^kc$. This happens to be equal to $\sigma(M)$, telling us that $M$ and $c$ are the only divisors of $M$. Only primes have two divisors, the prime itself and 1. And so $M$ is prime, and $c=1$.

We have shown that every even perfect number $N$ is of the form $2^{p-1}(2^p-1)$, where $(2^p-1)$ is prime.

Note: this solution is inspired by the proof given in Elementary Number Theory (Jones & Jones).