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