## Chapter 26Solutions for seventh week’s assignments

Also available as PDF.

### 26.1 Section 5.1 (prime numbers)

Problem 3
There is one even prime number, 2. The statement is false.
Problem 4
If 9\mathrel{∣}n, then n = 9 ⋅ k for some integer k. Then also n = 3 ⋅ (3 ⋅ k) = 3 ⋅ k' for an integer k' = 3k, so 3\mathrel{∣}n. The statement is true.
Problem 5
Here, 5\mathrel{∣}15 but 10 ∤ 15, so the statement is false.
Problem 7
A number n = 1 ⋅ n. This is of the divisibility form n = 1 ⋅ n + 0 with a remainder of zero, so n\mathrel{∣}n and n is a factor of itself. Also n ⋅ 1 = n and n is a multiple of itself. Thus the statement is true.
Problem 14
18 = 1 ⋅ 18 = 2 ⋅ 9 = 3 ⋅ 6, so its factors are 1, 2, 3, 6, 9, and 18.
Problem 15
20 = 1 ⋅ 20 = 2 ⋅ 10 = 4 ⋅ 5, so its factors are 1, 2, 4, 5, 10, and 20.
Problem 16
28 = 1 ⋅ 28 = 2 ⋅ 14 = 4 ⋅ 7, so its factors are 1, 2, 4, 7, 14, and 28.

#### 26.1.1 Problem 80

First evaluate M = 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 + 1 = 30031. To check if this is a prime or composite, we need to check for factors up to \sqrt{ 3}0031 ≈ 173.3 and hence up to 173.

Using Eratosthenes’s sieve method to search through integers:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

Once we reach the prime 59, we find 59\mathrel{∣}30031 and thus 30031 is not a prime. Its factorization is \mathbf{59 ⋅ 509}.

### 26.2 Section 5.1 (factorization)

Problem 34
425 = {5}^{2} ⋅ 17
Problem 35
663 = 3 ⋅ 13 ⋅ 17
Problem 36
885 = 3 ⋅ 5 ⋅ 59

The above could be solved by any reasonable method. As an example of the sieve method, consider the last problem of factoring 885.

 2 3 4 5 6 7 8 9 10

We start to list numbers up to \sqrt{885} ≈ 29.7 but only list them one line at a time. For the first prime, 2 ∤ 885. Then 3\mathrel{∣}885 and 885∕3 = 295. Only one factor of 3 can be pulled out, so 885 = 3 ⋅ 295. Now we only need to check numbers up to \sqrt{295} ≈ 17.2. The next prime 5\mathrel{∣}295, and 295∕5 = 59. Because 5 ∤ 59, only one factor of five can be pulled out. Now 885 = 3 ⋅ 5 ⋅ 59.

A previous problem showed that 59 is a prime, so we could stop here. Or if we didn’t know that 59 is prime, we need to check for factors up to \sqrt{ 59} ≈ 7.7. Only one more prime, 7, is in that range, and 7 ∤ 59, so 59 is prime.

The prime factorization is \mathbf{885 = 3 ⋅ 5 ⋅ 59}.

Problem 56
48 = {2}^{4} ⋅ {3}^{1}, so there are (4 + 1) ⋅ (1 + 1) = \mathbf{10} factors.
Problem 57
72 = {2}^{3} ⋅ {3}^{2}, so there are (3 + 1) ⋅ (2 + 1) = \mathbf{12} factors.
Problem 58
144 = 1{2}^{2} = {({2}^{2} ⋅ {3}^{1})}^{2} = {2}^{4} ⋅ {3}^{2}, so there are (4 + 1) ⋅ (2 + 1) = \mathbf{15} factors.
Problem 59
{2}^{8} ⋅ {3}^{2} = 2304, and there are (8 + 1) ⋅ (2 + 1) = \mathbf{27} factors.

### 26.3 Section 5.4 (modular arithmetic)

#### 26.3.1 Problems 9-13

The operation table is

 + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3

Every entry is an integer no less than zero and less than five, so the operation as defined is closed. Considering congruence classes rather than clocks, every integer is in one congruence class, so operations that produce integers must be closed.

The table is symmetric along its diagonal (0 ⋅ 0, 1 ⋅ 1, \mathop{\mathop{…}}), so the operation is commutative. Adding 0 + a ≡ a\kern 18mu ({\rm mod}\kern 6mu 5), so zero is the additive identity. And adding a + (5 - a) ≡ 0\kern 18mu ({\rm mod}\kern 6mu 5), so \mathbf{5 - a} is the additive inverse.

#### 26.3.2 Other problems

Problem 29
19 = 6 ⋅ 3 + 1 and 5 = 1 ⋅ 3 + 2. So \mathbf{19≢5\kern 18mu ({\rm mod}\kern 6mu 3)}.
Problem 31
The sum of the digits is 9 + 9 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 3), so 3\mathrel{∣}5445 and \mathbf{5445 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 3)}.
Problem 33
12 + 7 = 19 ≡\mathbf{3\kern 18mu ({\rm mod}\kern 6mu 4)}.
Problem 35
35 - 22 = 13 ≡\mathbf{3\kern 18mu ({\rm mod}\kern 6mu 5)}.
Problem 37
5 ⋅ 8 ≡-1 ⋅-1 ≡\mathbf{1\kern 18mu ({\rm mod}\kern 6mu 3)}.
Problem 39
4 ⋅ (13 + 6) = 4 ⋅ 19 ≡ 4 ⋅ 8 ≡ 4 ⋅ (-3) ≡-12 ≡-1 ≡\mathbf{10\kern 18mu ({\rm mod}\kern 6mu 11)}.

### 26.4 Section 5.1 (divisibility rules)

These can be found either with the rules in the text or by evaluating each number:

Problem 21
5\mathrel{∣}25025
Problem 22
5\mathrel{∣}45815
Problem 23
3\mathrel{∣}123\kern 1.66702pt 456\kern 1.66702pt 789, 9\mathrel{∣}123\kern 1.66702pt 456\kern 1.66702pt 789
Problem 24
3\mathrel{∣}987\kern 1.66702pt 654\kern 1.66702pt 321, 9\mathrel{∣}987\kern 1.66702pt 654\kern 1.66702pt 321 (same digits, different order)

Using the method described in class:

Problem 43
453\kern 1.66702pt 896\kern 1.66702pt 248 ≡ 8 - 4 + 2 - 6 + 9 - 8 + 3 - 5 + 4 ≡ 3\kern 18mu ({\rm mod}\kern 6mu 11), so 11 ∤ 453\kern 1.66702pt 896\kern 1.66702pt 248.
Problem 44
522\kern 1.66702pt 749\kern 1.66702pt 913 ≡ 3 - 1 + 9 - 9 + 4 - 7 + 2 - 2 + 5 ≡ 4\kern 18mu ({\rm mod}\kern 6mu 11), and 11 ∤ 522\kern 1.66702pt 749\kern 1.66702pt 913.

#### 26.4.1 Take a familiar incomplete integer\mathop{\mathop{…}}

Take a familiar incomplete integer, -679-. Using the expression of -679- as N = 1{0}^{4} ⋅ {x}_{4} + {x}_{0} + 6790, use 8\mathrel{∣}N to find {x}_{0}. Given that, use 9\mathrel{∣}N to find {x}_{4}. Now if 72 turkeys cost $-679-, what is the total? If 8\mathrel{∣}N, then we need only check the last three digits. So 790 + {x}_{0} = 8 ⋅ k for some k. There are only four values of {x}_{0} worth checking: 0, 2, 4, and 8. Of these, only 8\mathrel{∣}792, so {x}_{0} = 2. Now 9\mathrel{∣}N implies 9\mathrel{∣}{x}_{4} ⋅ 1{0}^{4} + 6792. Adding just the digits suffices, so we must solve {x}_{4} + 6 + 7 + 9 + 2 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9). Hence {x}_{4} + 6 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9), and {x}_{4} ≡-6 ≡ 3\kern 18mu ({\rm mod}\kern 6mu 9). The only such {x}_{4} that satisfies 0 ≤ {x}_{4} ≤ 9 is {x}_{4} = 3. Thus \mathbf{{x}_{4} = 3}, \mathbf{{x}_{0} = 2} and the total price is$367.92. The price per turkey is \$5.11.