Chapter 23
Solutions for seventh week’s assignments

Note: These are my approaches to these problems. There are many ways to tackle each.

23.1 Problem set 4.1

Problem 2

The (non-repeated) factorizations are 1 ⋅ 35 and 5 ⋅ 7. Drawing those as boxes is straight-forward.

Problem 4

Factors of 18	1	2	3	6	9	18
Quotient	18	9	6	3	2	1

Problem 7

• 48 = 1 ⋅ 48 = 2 ⋅ 24 = 3 ⋅ 16 = 4 ⋅ 6, so the factors are 1, 2, 3, 4, 6, 16, 24, and 48.
• 54 = 1 ⋅ 54 = 2 ⋅ 27 = 3 ⋅ 18 = 6 ⋅ 9, so the factors are 1, 2, 4, 6, 9 18, 27, 54.
• The largest common factor then is 6.

Problem 9

• 48 = {2}^{4} ⋅ {3}^{1}
• 108 = {2}^{2} ⋅ {3}^{3}
• 2250 = {2}^{2} ⋅ {3}^{2} ⋅ {5}^{3}
• 24\kern 1.66702pt 750 = {2}^{1} ⋅ {3}^{2} ⋅ {5}^{3} ⋅ 1{1}^{1}

Problem 10

• Yes, because all primes are shared and no powers of the primes exceed those of a.
• No, because {3}^{2} has a larger exponent than the {3}^{1} in a.
• a∕b = ({2}^{3} ⋅ {3}^{1} ⋅ {7}^{2})∕({2}^{2} ⋅ {3}^{1}) = {2}^{3-2} ⋅ {3}^{1-1} ⋅ {7}^{2-0} = {2}^{1} ⋅ {7}^{2}.
• There are (2 + 1) ⋅ (1 + 1) ⋅ (2 + 1) = 18 factors of a.
• We can make a list by running up the exponents:

  {2}^{0} ⋅ {3}^{0} ⋅ {7}^{0}

  {2}^{1} ⋅ {3}^{0} ⋅ {7}^{0}

  {2}^{2} ⋅ {3}^{0} ⋅ {7}^{0}

  {2}^{3} ⋅ {3}^{0} ⋅ {7}^{0}

  {2}^{0} ⋅ {3}^{1} ⋅ {7}^{0}

  {2}^{1} ⋅ {3}^{1} ⋅ {7}^{0}

  {2}^{2} ⋅ {3}^{1} ⋅ {7}^{0}

  {2}^{3} ⋅ {3}^{1} ⋅ {7}^{0}

  {2}^{0} ⋅ {3}^{0} ⋅ {7}^{1}

  {2}^{1} ⋅ {3}^{0} ⋅ {7}^{1}

  {2}^{2} ⋅ {3}^{0} ⋅ {7}^{1}

  {2}^{3} ⋅ {3}^{0} ⋅ {7}^{1}

  {2}^{0} ⋅ {3}^{1} ⋅ {7}^{1}

  {2}^{1} ⋅ {3}^{1} ⋅ {7}^{1}

  {2}^{2} ⋅ {3}^{1} ⋅ {7}^{1}

  {2}^{3} ⋅ {3}^{1} ⋅ {7}^{1}

  {2}^{0} ⋅ {3}^{0} ⋅ {7}^{2}

  {2}^{1} ⋅ {3}^{0} ⋅ {7}^{2}

  {2}^{2} ⋅ {3}^{0} ⋅ {7}^{2}

  {2}^{3} ⋅ {3}^{0} ⋅ {7}^{2}

  {2}^{0} ⋅ {3}^{1} ⋅ {7}^{2}

  {2}^{1} ⋅ {3}^{1} ⋅ {7}^{2}

  {2}^{2} ⋅ {3}^{1} ⋅ {7}^{2}

  {2}^{3} ⋅ {3}^{1} ⋅ {7}^{2}

Problem 13

No, it is only true that at least one prime factor cannot exceed \sqrt{n}. Consider 2 ⋅ 47 = 94, where both 2 and 47 are prime. We have \sqrt{94} < 10 but 47 > 10 > \sqrt{94}. But 2 < \sqrt{94}.

Problem 14

No. If n is not prime, some of its factors may split between b and c. For example, 2 ⋅ 3 = 6\mathrel{∣}18 = 2 ⋅ 9, but 6 ∤ 2 and 6 ∤ 9. The factors of n = 6, 2 and 3, are split between a = 2 and b = 9.

Problem 23

Here it is true. Consider the prime factorizations of b and c. If p\mathrel{∣}bc, then p must appear in one or both of those prime factorizations, and thus it must divide at least one of b and c.

Problem 24

Again, use the prime factorization of n. Because p and q are primes, they must appear in that factorization. Then pq\mathrel{∣}n because both appear, so you can commute products around to group (pq) and the rest of the factorization.

23.2 Two diagrams

8 ∤ 18:

18 = 2 ⋅ 8 + 2, so you can draw and count:

+

3 ∤ 11:

11 = 3 ⋅ 3 + 2:

+

23.3 Problem set 4.2

Problem 1

• 1554 is even, so divisible by 2, does not end in 5 or 0, so is not divisible by 5, and has digits that add to 0\kern 18mu ({\rm mod}\kern 6mu 3), so is divisible by 3.
• 1999 is not even, so is not divisible by 2, does not end in 5 or 0, so is not divisible by 5, and has digits that add to 1\kern 18mu ({\rm mod}\kern 6mu 3), so is not divisible by 3.
• 805 is not divisible by 2, is divisible by 5, and is not divisible by 3.
• 2450 is divisible by 2, is divisible by 5, and is not divisible by 3.

Problem 2

• 2 and 3
• 2 and 5
• 3 and 5
• 2, 3, and 5

Problem 8

The missing digit must be divisible by 2. Also, the sum of the digits must be congruent to 0 modulo 3. The non-blank digits already add to 0\kern 18mu ({\rm mod}\kern 6mu 3), so the missing digit must be a multiple of 3. There is only one even multiple of 3 less than 10, so the missing digit must be 6.

Problem 14

Expanding the positional notation and simplifying, abc,abc = a⋅(1{0}^{5}+1{0}^{2})+b⋅(1{0}^{4}+1{0}^{1})+c⋅(1{0}^{3}+1{0}^{0}) = (a⋅1{0}^{2}+b⋅1{0}^{1}+c)⋅(1{0}^{3}+1{0}^{0}) = abc⋅1001. Now 1001 = 7 ⋅ 11 ⋅ 13, so abc,abc is divisible by each of those.

Problem 15

• ab - ba = a ⋅ 10 + b - (b ⋅ 10 + a) = (a - b) ⋅ 10 + (b - a). Because 10 ≡ 1\kern 18mu ({\rm mod}\kern 6mu 9), this becomes a - b + b - a ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9). The result always is a multiple of 9. Equivalently, we can rearrange (a - b) ⋅ 10 + (b - a) = (a - b) ⋅ 10 + -1 ⋅ (a - b) = (a - b) ⋅ (10 - 1) = 9(a - b), giving also which multiple of 9.
• Here the difference is (a - c) ⋅ 1{0}^{2} + 0 + (c - a) because the middle digit always cancels. Again, the result always is a multiple of 9 and we can rearrange (a-c)⋅1{0}^{2}+0+(c-a) = (a-c)⋅1{0}^{2}+-1⋅(a-c) = (a-c)⋅(1{0}^{2}-1) = 99(a-c) to see the result is a multiple of 99.

23.4 A familiar incomplete integer

If 8\mathrel{∣}N then 8 divides the last three digits, so 8\mathrel{∣}790 + {x}_{0}. Thus 790 + {x}_{0} ≡ 0\kern 18mu ({\rm mod}\kern 6mu 8). Because 790 ≡ 6\kern 18mu ({\rm mod}\kern 6mu 8), we know that {x}_{0} ≡ 2\kern 18mu ({\rm mod}\kern 6mu 8). The only decimal digit satisfying {x}_{0} ≡ 2\kern 18mu ({\rm mod}\kern 6mu 8) is \mathbf{{x}_{0} = 2}.

Now we have N = 1{0}^{4} ⋅ {x}_{4} + 6792. For 9\mathrel{∣}N, the sum of the digits must be zero modulo 9. Thus {x}_{4} + 6 + 7 + 9 + 2 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9), or {x}_{4} + 6 ≡ 0\kern 18mu ({\rm mod}\kern 6mu 9). Thus \mathbf{{x}_{4} = 3}, and \mathbf{N = 36792}.

(I forgot the decimal place in the problem, so these are very expensive turkeys.)

So if 72 turkeys cost $36792, each turkey costs $511. If I had remembered the decimal place correctly, the turkeys cost $5.11 each.