Solutions for seventh week’s assignments

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

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

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

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.

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

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.

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.