Chapter 2

The four different branches of Arithmetic– Ambition, Distraction, Uglification, and Derision.

-The Mock Turtle

Definition The n^{th} triangular number, t_{n}, is the sum of the first n positive integers,

t_{n} = 1 + 2 + 3 + ... + n.

So, for example, t_{1} = 1, t_{2} = 3 = 1 + 2, t_{3} = 6 = 1 + 2 + 3, and t_{341} = 41, 311.

Triangular numbers can be visualized as the total area of a staircase; that’s why they’re called triangular numbers. The ancient Greeks were, and many modern folks are, interested in the geometry of numbers and defined lots of families of figurate numbers. Some of these are familiar to you–why do you think we say x-squared and x-cubed anyway? Perhaps less familiar are the pentagonal, hexagonal, heptagonal, … numbers which correspond to arrangements of points of the corresponding shape. All of these families have interesting properties, consider what follows an existence proof of that assertion in the case of the triangular numbers.

t_{4} would be the area of: \begin{matrix}□ \\ □□ \\ □□□ \\ □□□□ \end{matrix}

Problem 2a Prove that N is triangular if and only if N = \frac{n(n+1)}{2} for some positive integer n.

Proof: Putting together two staircases with side n gives a rectangle with sides n and n + 1.

\overbrace{△□□□□}^{n+1} ; △△□□□ ; △△△□□ ; △△△△□ \} n

Consider the area of this rectangle which is composed of a triangular number added itself. This area is n(n + 1) = 2N. Thus, N = \frac{n(n+1)}{2}.

Problem 2b Prove N is triangular iff 8N + 1 is a perfect square.

Proof: As above the double of a triangular number is the product of two consecutive numbers. Geometrically, an n by n + 1 rectangle. Below is the picture for t_{2} = N, notice the four 2x3 rectangles each composed of two copies of t_{2}. This picture clearly generalizes to the cases for larger n. (Just in case you don’t believe that, an algebraic proof is given below.)

\begin{matrix}□ & □ & □ & ◇ & ◇ \\ □ & □ & □ & ◇ & ◇ \\ ♡ & ♡ & △ & ◇ & ◇ \\ ♡ & ♡ & ♣ & ♣ & ♣ \\ ♡ & ♡ & ♣ & ♣ & ♣ \end{matrix}

Algebraic Proof:

\frac{(8n(n + 1))}{2} + 1 = 4n(n + 1) + 1 = 4n^{2} + 4n + 1 = (2n + 1)^{2}

Problem 2c Prove that the sum of two consecutive triangular numbers is a perfect square.

Proof:

◯  ◯  \begin{matrix}◯ & ◯ & △ \\ ◯ & △ & △ \\ △ & △ & △ \end{matrix}  …  \begin{matrix}♢ & ♢ & ♢ & ♢ & ♢ & ♠ \\ ♢ & ♢ & ♢ & ♢ & ♠ & ♠ \\ ♢ & ♢ & ♢ & ♠ & ♠ & ♠ \\ ♢ & ♢ & ♠ & ♠ & ♠ & ♠ \\ ♢ & ♠ & ♠ & ♠ & ♠ & ♠ \\ ♠ & ♠ & ♠ & ♠ & ♠ & ♠ \end{matrix}  …

Algebraic proof:

\frac{n(n + 1)}{2} + \frac{(n + 1)(n + 2)}{2} = \frac{(2n + 2)(n + 1)}{2} = (n + 1)^{2}

Problem 2d Prove that if N is triangular, then 9N + 1 and 25N + 3 are triangular.

Proof:

9N + 1 = \frac{9n(n + 1)}{2} + 1 = \frac{(9n^{2} + 9n + 2)}{2} = \frac{(3n + 1)(3n + 2)}{2}

This is triangular since it is of the form \frac{m(m+1)}{2}.

25N + 3 = \frac{25n(n + 1)}{2} + 3 = \frac{(25n^{2} + 25n + 6)}{2} = \frac{(5n + 2)(5n + 3)}{2}

As before, this is of the form \frac{m(m+1)}{2}, so it is triangular.

Alternate Proof: From 2b a number, M, is triangular if and only if 8M + 1 is a square. Let’s apply this test to M = 9N + 1.

8(9N + 1) + 1 = 72N + 9 = 9(8N + 1)

Since we are given that N is triangular 8N + 1 is a square, and 9 is, of course, a square. Thus this whole expression is a square and, by 2b, 9N + 1 is triangular.

Using the same method we have

8(25N + 3) + 1 = 200N + 25 = 25(8N + 1)

Problem 2e Generalize the previous result. Claim: If N is triangular, then (2k + 1)^{2}N + \frac{k(k+1)}{2} is triangular.

Proof:

(2k + 1)^{2}N + \frac{k(k + 1)}{2} = (2k + 1)^{2} \frac{n(n + 1)}{2} + \frac{k(k + 1)}{2}

= \frac{(2k + 1)^{2} × n^{2} + (2k + 1)^{2} × n + k(k + 1)}{2}

= \frac{(2k + 1)^{2} × n^{2} + (2k + 1)(k + (k + 1))n + k(k + 1)}{2}

= \frac{[(2k + 1)n + k][(2k + 1)n + (k + 1)]}{2}

= \frac{[(2k + 1)n + k][((2k + 1)n + k) + 1)]}{2}

Alternate Proof: We’ll use 2b and test whether 8[(2k + 1)^{2}N + \frac{k(k+1)}{2}] + 1 is a square. Notice that (2k + 1)^{2} = 8(\frac{k(k+1)}{2}) + 1.

8((8t_{k} + 1)N + t_{k}) + 1 = (64t_{k} + 8)N + (8t_{k} + 1) = (8t_{k} + 1)(8N + 1)

The final expression is a square, by 2b. So (8t_{k} + 1)N + t_{k} must be triangular, also by 2b.

Problem 2f Find a simple formula for the sum of the first m triangular numbers. We know from 2c that t_{n} + t_{n+1} = (n + 1)^{2} Case 1: m is even.

t_{m} + t_{m−1} + ... + t_{4} + t_{3} + t_{2} + t_{1}
= m^{2} + (m − 2)^{2} + ... + 4^{2} + 2^{2}

= 4(\frac{m^{2}}{2} + ... + 2^{2} + 1^{2})

Now, we know that

∑_{i=0}^{k} i^{2} = \frac{k(k + 1)(2k + 1)}{6}

So,

4(\frac{m^{2}}{2} + ... + 2^{2} + 1^{2}) = \frac{2}{3} \frac{m}{2}(\frac{m}{2} + 1)(m + 1)

= \frac{m(\frac{m}{2} + 1)(m + 1)}{3} = \frac{m(m + 1)(m + 2)}{6}

Case 2: m is odd.

t_{m} + t_{m−1} + ... + t_{4} + t_{3} + t_{2} + t_{1}

= \frac{m(m + 1)}{2} + (m − 1)^{2} + (m − 3)^{2} + ... + 4^{2} + 2^{2}

= \frac{(3m(m + 1) + (m − 1)m(m + 1))}{6}

= \frac{(m(m + 1)(3 + m − 1))}{6}

= \frac{m(m + 1)(m + 2)}{6}

Problem 2g Are there any squares that are also triangular numbers?

Yes, for example 1, 36, and 1225. Is there a pattern here? We’ll get back to this. Problem 3 Show that 7 | 2^{3n} − 1, for all n.

Proof: First note that

2^{3n} − 1 = 8^{n} − 1

We also know that in general,

a^{n} − 1 = (a − 1)(a^{n−1} + a^{n−2} + ... + 1)

Thus, in our case

2^{3n} − 1 = 8^{n} − 1
= (8 − 1)(8^{n−1} + 8^{n−2} + ... + 1)
= 7 · (8^{n−1} + 8^{n−2} + ... + 1)

This is clearly divisible by 7.

Problem 4 Show that 8 | 2^{3n} + 7 , for all n.

Proof: To begin an induction proof notice that 8 divides 16 (n = 1). Assume that 8 divides 9^{n} + 7 for some n. Then,

9^{n+1} + 7 = 9(9^{n} + 7) − 56

Both terms on the right are clearly divisible by 8.

Problem 5 Show that 2^{n} + (−1)^{n+1} is always divisible by 3.

Proof: Notice that 2^{n} cannot be a multiple of 3 and therefore must be of the form 3k ± 1. So, the statement is merely that the plus and minus sign alternate with n, beginning with minus when n = 1. This is easily verified, 2(3k +1) = 3(2k +1)−1. Similarly for 3k − 1.

Problem 6 Show that the sum of the squares of 2 odd integers cannot be itself a square.

Proof:

(2k + 1)^{2} + (2n + 1)^{2} = 4(k^{2} + n^{2} + k + n) + 2.

A number of the form 4k + 2 cannot be a square.

Day 3, September 14, notes scribed by Michael Hanslick.

A list of questions that arise from inspection of the table produced in answer to problem 1.

1. There is often more than one way to represent an integer as the sum of n squares.

2. Why don’t you ever need more than 4 squares in such a sum, when n ≤ 400?

3. What about the number of squares in a sum when n > 400?

4. When do two squares suffice?

5. When do three squares suffice?

6. How frequently do you need four squares?

7. Can all even numbers be written as the sum of 2 primes?

8. In how many ways?

9. When is the sum of the divisors of n >, =, or < n?

10. What is the number of divisors of a perfect number n?

11. Are there infinitely many deficient numbers? abundant numbers? perfect numbers? Definition An integer n is said to be deficient when the sum of the divisors of n is less than n. We call n abundant if its divisor sum is more than n, and we say it is perfect if its divisor sum equals n. (Here, the divisor sum does not include n itself) Prime Numbers Definition A number p > 1 is prime if 1 and p are its only divisors. A number greater than one is called composite if it is not prime. (One itself is neither prime nor composite.) Theorem 2.1 If p is prime and p|ab, then p|a or p|b.

Proof: Suppose p does not divide a. Then since gcd(p, a) = 1, Euclid’s lemma implies that p divides b.

Corollary 2.1.1 If p|a_{1}a_{2}....a_{k} and p is prime, then p|a_{j} for some 1 ≤ j ≤ k.

Proof: A straightforward induction, Theorem 2.1 establishes the base case.

Corollary 2.1.2 If p|q_{1}q_{2}....q_{n}, p and q_{i} all prime, then p = q_{i} for some 1 ≤ i ≤ n.

Proof: Follows immediately from Corollary 1.

Fundamental Theorem of Arithmetic Every number a > 1 can be written uniquely, up to the order of the factors, as a product of primes.

Proof: If a is a prime, we’re done. If a is composite, let D = {d: d|a and d ≠ 1 or a}. D has a least element, say δ_{1}. Note that δ_{1} is prime, else it has a divisor which also divides a. Now we have a = δ_{1}a_{1}, and a_{1} < a. Continuing in this way, we obtain:

a = δ_{1}δ_{2}a_{2} a_{2} < a_{1}

a = δ_{1}δ_{2}δ_{3}a_{3} a_{3} < a_{2}

And so on. Clearly, this process ends in a finite number of steps, because the a_{i} are a decreasing sequence of positive numbers. At which point we have

a = δ_{1}δ_{2}δ_{3} … δ_{r}

Where δ_{1}, ..., δ_{r} are all prime. Now all that remains to show is that this representation of a as a product of primes is in fact unique.

Day 4, September 16, notes scribed by Steve Griffeth.

Proof of Uniqueness

Suppose, m ≥ n, p_{i} ≤ p_{i+1}, q_{i} ≤ q_{i+1}, p_{i} and q_{i} are prime.

a = p_{1}p_{2}...p_{n} = q_{1}q_{2}...q_{m}

Now, p_{1} | a, so p_{1} | q_{1}q_{2}...q_{m}. By Corollary 2 of Theorem 2.1 p_{1} ∈ {q_{1}, q_{2}, …, q_{m}}. Likewise, q_{1} ∈ {p_{1}, p_{2}, …, p_{n}}. So p_{1} = q_{k} ≥ q_{1} and q_{1} = p_{k} ≥ p_{1}. Since p_{1} ≥ q_{1} and q_{1} ≥ p_{1}, p_{1} = q_{1}

Repeat the argument for all i, 1 ≥ i ≥ n. Divide

a = p_{1}p_{2}...p_{n} = q_{1}q_{2}...q_{m}

by p_{1}p_{2}...p_{n} to get

1 = 1 = q_{n+1}q_{n+2}...q_{m}

If they exist, q_{n+1}q_{n+2} … q_{m} must all be greater than 1. So they don’t exist, m = n, and the representation of a is unique.

An Introduction to Pythagorean Triples

Consider the following table of numbers. It was generated by trying to find square triangles (problem 2g). Notice that a row gives a square triangle whenever its second entry and either its third or fourth entry are both squares. So that rows 3, 7, and 17 all give square triangles.

\begin{matrix}n & n^{2} & \frac{n^{2}−1}{2} & \frac{n^{2}+1}{2} \\ 3 & 9 & 4 & 5 \\ 5 & 25 & 12 & 13 \\ 7 & 49 & 24 & 25 \\ 9 & 81 & 40 & 41 \\ 11 & 121 & 60 & 61 \\ 13 & 169 & 84 & 85 \\ 15 & 225 & 112 & 113 \\ 17 & 289 & 144 & 145 \end{matrix}

This table has (at least) two interesting features:

1. The third column is 4t_{n} where t_{n} is the n^{th} triangular number.

2. Columns 1,3, and 4 make Pythagoreon Triples. This suggests that given an odd number n ≥ 3, you can always generate a Pythagorean Triple of the form (n, x, x + 1).

Proof of 1. We want to show \frac{(2k+1)^{2}−1}{2} = 4 · \frac{k(k+1)}{2}, since 2k + 1 is an odd number and \frac{k(k+1)}{2} is the k^{th} triangular number. Work with the left side:

\frac{(2k + 1)^{2} − 1}{2} = \frac{4k^{2} + 4k + 1 − 1}{2} = 4(k^{2} + k) = 4\frac{k(k + 1)}{2}

Proof of 2. We want to show n^{2} + (\frac{n^{2}−1}{2})^{2} = (\frac{n^{2}+1}{2})^{2}. Again work from the left:

n^{2} + \frac{(n^{2} − 1)^{2}}{4} = \frac{4n^{2}}{4} + \frac{n^{4} − 2n^{2} + 1}{4} = \frac{n^{4} + 2n^{2} + 1}{4} = \frac{(n^{2} + 1)^{2}}{4}

Problem 2g revisited and partially solved. Consider the two recursively defined sequences,

n_{k} = n_{k−1} + d_{k−1}, (n_{1} = 1)

and

d_{k} = n_{k−1} + n_{k}, (d_{1} = 1)

The first few terms are

n_{k} = 1, 2, 5, 12, 29, 70, …
d_{k} = 1, 3, 7, 17, 41, 99, …

From these lists, it appears that

d_{k}^{2} = 2n_{k}^{2} + (−1)^{k}

Proof (PMI): Basis step (k = 1), n_{1} = d_{1} = 1, and

1^{2} = 2(1)^{2} + (−1)^{1}

Our inductive hypothesis is (−1)^{k} = 2n_{k−1}^{2} − d_{k−1}^{2}. So, we will show that

(−1)^{k+1} = 2n_{k}^{2} − d_{k}^{2}

Using the definitions of n_{k} and d_{k}

2n_{k}^{2} − d_{k}^{2} = n_{k}^{2} + (n_{k−1} + d_{k−1})^{2} − (n_{k−1} + n_{k})^{2}
= n_{k}^{2} + (n_{k−1}^{2} + 2n_{k−1}d_{k−1} + d_{k−1}^{2}) − (n_{k−1}^{2} + 2n_{k−1}n_{k} + n_{k}^{2})
= 2n_{k−1}d_{k−1} + d_{k−1}^{2} − 2n_{k−1}n_{k}

Again substituting,

= 2n_{k−1}d_{k−1} + d_{k−1}^{2} − 2n_{k−1}(n_{k−1} + d_{k−1})
= 2n_{k−1}d_{k−1} + d_{k−1}^{2} − 2n_{k−1}n_{k−1} − 2n_{k−1}d_{k−1}
= d_{k−1}^{2} − 2n_{k−1}^{2}
= (−1)(2n_{k−1}^{2} − d_{k−1}^{2})

But, from our inductive hypothesis this is exactly (−1)^{k+1}.

Why did we do all of this anyway? Notice that n_{k}^{2}d_{k}^{2} is both a perfect square and a triangular number

n_{k}^{2}d_{k}^{2} = n_{k}^{2}(2n_{k}^{2} + (−1)^{k})

= \frac{2n_{k}^{2}}{2} (2n_{k}^{2} + (−1)^{k})

Since 2n_{k}^{2} and 2n_{k}^{2} +(−1)^{k} always differ by one, the above expression is of the form \frac{m(m+1)}{2} and is thus a triangular number! So we have found infinitely many numbers that are both square and triangular. Have we found them all? (See Chapter 3.)

Day 4, September 16, notes scribed by Jay Huston, Michael Hanslick,

and Drew Schroeder. The Sieve of Erastothenes

Some of us spent our summer finding primes. Some of us didn’t. But, either way, the Sieve of Erastothenes is an easy way to find all of the primes less than a given number. List the numbers from 1 to n. Cross out the number 1 (by definition, 1 is not prime). Then, beginning with 2, skip the number you start with and cross out all other multiples of that number (i.e. skip 2, cross out 4, 6, 8, etc.). Go to the next non-eliminated number, repeat (i.e. go to 3, cross out its multiples, then 5, etc.). Once the end has been reached, all remaining numbers are prime. (In actuality, you only need to go up to \sqrt{n}, since there will be no multiples past that point.) An example up to the number 50 is shown below.

\begin{matrix}1̸ & 2 & 3 & 4̸ & 5 & 6̸ & 7 & 8̸ & 9̸ & 1̸0 \\ 11 & 1̸2 & 13 & 1̸4 & 1̸5 & 1̸6 & 17 & 1̸8 & 19 & 2̸0 \\ 2̸1 & 2̸2 & 23 & 2̸4 & 2̸5 & 2̸6 & 2̸7 & 2̸8 & 29 & 3̸0 \\ 31 & 3̸2 & 3̸3 & 3̸4 & 3̸5 & 3̸6 & 37 & 3̸8 & 3̸9 & 4̸0 \\ 41 & 4̸2 & 43 & 4̸4 & 4̸5 & 4̸6 & 47 & 4̸8 & 4̸9 & 5̸0 \end{matrix}

And, before you embark on an expedition to find all of the primes by using the Sieve, you might want to check out this next theorem...

Theorem 2.2 (from Euclid’s Elements) There are infinitely many prime numbers.

Proof: Suppose there are only finitely many prime numbers. Then define the set T as:

T = {t | t is prime } = {2, 3, …, P }.

Now, consider the number N = 2 · 3 · · · · · P + 1.

By construction, N is not divisible by any element t ∈ T. Therefore, there are two possibilities: either N itself is prime, or it factors into a product of primes none of whom are in T. In either case T does not contain all the primes and we have a contradiction to our hypothesis of only finitely many primes.

So, as you can see, you and the Sieve might be there a while.

Problem 9 Prove that n^{5} − n is always divisible by 30.

Proof: To show 30|n^{5} − n, we must show that 2, 3, and 5 all divide n^{5} − n.

First, we factor n^{5} − n:

n^{5} − n = (n − 1)n(n + 1)(n^{2} + 1).

We have three consecutive integers in n − 1, n, and n + 1. Thus, by the Pigeonhole Principle, at least one of these is divisible by 2, and exactly one is divisible by 3. So, both 2 and 3 divide n^{5} −n. It remains to be shown that 5|n^{5} −n. We can write n in the form n = 5k + r, where 0 ≤ r ≤ 4. This gives us five cases to consider:

Case 1: r = 0. If n = 5k + 0, then, clearly, 5|n.

Case 2: r = 1. If n = 5k + 1, then 5k = n − 1, and 5|n − 1.

Case 3: r = 2. If n = 5k+2, then n^{2} +1 = 25k^{2} +20k+4+1 = 5(5k^{2} +4k+1), and we see that 5|n^{2} + 1.

Case 4: r = 3. If n = 5k+3, then n^{2} +1 = 25k^{2} +30k+9+1 = 5(5k^{2} +6k+2), and 5|n^{2} + 1.

Case 5: r = 4. If n = 5k + 4, then n + 1 = 5(k + 1), and 5|n + 1.

Thus, 5 | n^{5} −n, as well. So, 2, 3, and 5 all divide n^{5} −n, and therefore, 30 | n^{5} −n for all n.

Problem 10 The only prime one less than a cube is 7.

Proof: We factor n^{3} − 1 and get n^{3} − 1 = (n − 1)(n^{2} + n + 1). If n^{3} − 1 is to be prime, either n − 1 or n^{2} + n + 1 must be 1. So, we have two cases:

Case 1: If n − 1 = 1, then n = 2, and n^{3} − 1 = 8 − 1 = 7.

Case 2: If n^{2} + n + 1 = 1, then n^{2} + n = n(n + 1) = 0, and n = 0 or −1.

This gives

n^{3} − 1 = 0^{3} − 1 = −1

or

n^{3} − 1 = (−1)^{3} − 1 = −2.

Neither −1 or −2 are positive integers, and thus cannot be prime. Thus, the only prime one less than a cube is 7.

Problem 11 Find all primes such that 3p + 1 is a square.

If 3p + 1 is a square, then we can write 3p + 1 = (t + 1)^{2} = t^{2} + 2t + 1, and this implies that

3p = t^{2} + 2t = t(t + 2).

Since 3 and p are both prime, t and t + 2 must both be prime, as well. (If they weren’t, then t(t + 2) would have at least three prime factors, and either 3 or p would have to be composite, which we know is false.) In addition, 3 must divide t or t + 2, which are both prime, so either t = 3 or t + 2 = 3. If t = 3, then t + 2 = 5, so p = 5. If t + 2 = 3, then t = 1, so p = 1. But, 1 is not a prime. So, the only prime such that 3p + 1 is a square is 5.

Problem 12 Every positive integer of the form 4k + 3 has a prime factor of the same form.

Proof: Hold on to your hats, it’s strong induction to the rescue! Basis Step: k = 0. This gives 4 · 0 + 3 = 3. Three is its own prime factor. So, the basis step holds. Inductive Step: We assume that for all m < n, 4m + 3 has a prime factor of the form 4k + 3. We must show 4n + 3 has a factor of the form 4k + 3. This gives us two cases:

Case 1: If 4n + 3 is prime, it is its own prime factor, and we’re done.

Case 2: If 4n + 3 is not prime, then there exist x, y with 1 < x, y < 4n + 3 such that xy = 4n + 3. There are then four possible forms for each x and y:

\begin{matrix}x & y \\ 4l & 4j \\ 4l + 1 & 4j + 1 \\ 4l + 2 & 4j + 2 \\ 4l + 3 & 4j + 3 \end{matrix}

Since we are looking for the form 4n + 3, which is odd, neither x nor y can be even. This eliminates 4l, 4l + 2, 4j, and 4j + 2.

If x = 4l+1 and y = 4j+1, we get xy = 16lj+4l+4j+1 = 4(4lj+l+j)+1 = 4z+1. This cannot equal 4n + 3.

Therefore, either x = 4l + 3 or y = 4j + 3.

If x or y is prime, we are done.

If not, we know that x, y < 4n + 3, so it must be true that l, j < n. Thus, by the inductive hypothesis, there must exist some r such that r | x or r | y with r prime and of the form 4k + 3.

Thus, 4n + 3 has a prime factor of the form 4k + 3. So, every positive integer of the form 4k + 3 has a prime factor of the same form.

Problem 13 There are infinitely many primes of the form 4k + 3.

Proof: Assume not. Then there exists a non-empty, finite set P such that:

P = {4k + 3 | k ∈ Z, 4k + 3 is prime } = {p_{1}, p_{2}, …, p_{r}}.

Since 4k + 3 = 4n − 1 for some n, this can be rewritten as

P = {4n − 1 | n ∈ Z, 4n − 1 is prime }.

Taking a cue from Euclid, form the product of all the elements of p. Multiply the result by 4 and subtract 1, we get N = 4 · p_{1} · p_{2} · · · · · p_{r} − 1. By the previous theorem, there exists some prime number n such that n|N, and n is of the form 4k+3. Obviously n ∉ P, so we have a contradiction. Therefore, there are infinitely many primes of the form 4k + 3.

Day 5, September 18, notes scribed by Millie Kimes.

Problem 16 Every integer n greater than 11 can be written as the sum of two composite numbers.

Proof A: We consider two cases, depending on the parity of n.

Case 1: n is even.

For all n ≥ 12, we can write n as: n = 4 + (n − 4). Obviously 4 is composite. Since n is even n − 4 is also even, and thus composite as well.

Case 2: n is odd.

Similarly, we can write n as: n = 9 + (n − 9). Once again 9 is composite, and n − 9 is even and (because n > 11) greater than or equal to 4. Therefore, n − 9 is composite, and n has been written as the sum of two composite numbers.

Proof B: In order to find a contradiction suppose n cannot be written as the sum of two composite numbers and that it is the first integer greater than 11 for which this is true. This implies:

n − 1 = p + q for composite p and q

1. Consider p + 1 and q + 1: both must be prime.

To prove this, suppose not, and let p + 1 be composite. This implies:

n = (p + 1) + q

with both p+1 and q composite, a contradiction of our hypothesis. Similarly, q + 1 must also be prime.

2. Consider p − 1 and q + 2. At least one of these numbers must be prime; otherwise, we can express n as the sum of two composite numbers. But, because we know q + 1 is prime, q + 2 cannot also be prime. Therefore:

p − 1 is prime.

3. Now consider p + 3 and q − 2. Again, at least one of these numbers must be prime. Since q + 1 is prime, we know that q − 2 cannot be, thus:

p + 3 is prime.

We have now shown that the numbers p − 1, p + 1, and p + 3 must all be prime. However, exactly one of these must be divisible by 3. Contradiction.

Problem 18 A number of the form 2^{n−1}(2^{n} − 1) is perfect if and only if 2^{n} − 1 is prime.

Proof: The divisors of a number of this form, not including itself, are

1, 2, 4, ..., 2^{n−1} and 1(2^{n} − 1), 2(2^{n} − 1), 4(2^{n} − 1), ..., 2^{n−2}(2^{n} − 1)

We want to show that the sum of the divisors is equal to the number

∑_{i=0}^{n−1} 2^{i} + ∑_{i=0}^{n−1} 2^{i}(2^{n} − 1) = 2^{n−1}(2^{n} − 1)

By induction we can show that

1 + 2 + 4 + ... + 2^{n−1} = 2^{n} − 1

The base case is clear, so assume there exists k such that

1 + 2 + 4 + ... + 2^{k−1} = 2^{k} − 1

. It follows that

1 + 2 + 4 + ... + 2^{k−1} + 2^{k} = 2^{k} − 1 + 2^{k}
1 + 2 + 4 + ... + 2^{k} = 2 · 2^{k} − 1

Thus, 1 + 2 + 4 + ... + 2^{n−1} = 2^{n} − 1. Therefore, the sum of divisors of our original number must be

(2^{n} − 1) + (2^{n} − 1)(2^{n−1} − 1)
= (2^{n} − 1)(1 + 2^{n−1} − 1)
= 2^{n−1}(2^{n} − 1)

The converse is simple. If 2^{n} − 1 is not prime, then there are more divisors than those listed above and 2^{n−1}(2^{n} − 1) is abundant.

Problem 19 For every composite number m, 2^{m} − 1 is also composite.

Proof: Let m = kn for integers k > 1 and n > 1. We want to show that there exists an integer a such that

a(2^{n} − 1) = 2^{kn} − 1

So,

a = \frac{(2^{n})^{k} − 1}{2^{n} − 1}

It is easy to see

(x^{k−1} + x^{k−2} + x^{k−3} + ... + 1)(x − 1) = x^{k} − 1

**Aside - You’ve seen this in calc 2; it’s how you prove that a geometric series converges. Note: this is a factorization, if x−1 = 1, then x = 2, therefore n = 1.**

Thus, x − 1|x^{k} − 1. It immediately follows that 2^{n} − 1|2^{kn} − 1.

Definition A prime of the form 2^{n} − 1 is called a Mersenne prime.

From the preceding theorem it follows that for 2^{n} − 1 to be prime, n must be prime. Some examples of Mersenne primes and the perfect numbers they generate are:

\begin{aligned}2^{2} − 1 & = & 3 & 2 · 3 & = & 6 \\ 2^{3} − 1 & = & 7 & 2^{2}(2^{3} − 1) & = & 28 \\ 2^{5} − 1 & = & 31 & 2^{4}(2^{5} − 1) & = & 496 \\ 2^{7} − 1 & = & 127 & 2^{6}(2^{7} − 1) & = & 8128 \\ 2^{13} − 1 & = & 8191 & 2^{12}(2^{13} − 1) & = & 33, 550, 336 \end{aligned}

2^{127} − 1 = 170141183460469231731687303715884105727 never mind

However, and this is why life is interesting, not all prime exponents produce Mersenne primes. Some examples of prime values of n that do not produce primes are:

2^{11} − 1 = 2047 = 23 · 89
2^{23} − 1 = 8388607 = 47 · 178481
2^{29} − 1 = 233 · 1103 · 2089

How on earth does one tell whether 2^{p} − 1 is prime? It would be pretty tough to find that last factorization, not to mention to convince yourself that 2^{127} − 1 is prime. How do we know? Good questions, keep reading (or better still, go think about it for a while, then continue reading).

Day 5, September 18, notes scribed by Rose Koch.