Chapter 26
Solutions for seventh week’s assignments

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:

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.

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

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{…}}

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.