Chapter 25
Solutions for eighth week’s assignments

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

25.1 Problem set 4.3

Problem 6

Every integer divides zero, so (0,n) = n appears correct for n > 0. Indeed, 0 = 0 ⋅ n and n = 1 ⋅ n, so n divides both. The only point for discussion is in the definition of the greatest common divisor and divisibility. The text defines it in an obtuse way that disallows (0,n) = n.

Most mathematicians would allow n\mathrel{∣}0 and (0,n) = n. Indeed, n\mathrel{∣}0 for all n is stated on the first page of one of the most respected number theory textbooks¹ . So, alas, the “correct” response is to find out what standardized test uses which definition. This is yet another reason why standardized tests in higher mathematics are useless.

Problem 7

Again, by the text’s definitions, this cannot be true. By most common mathematical definitions, \mathop{lcm}\nolimits (0,n) = 0. This is another example where I’m interested in seeing how you state and defend your position.

Problem 13

• One method for finding both is to find the prime factorizations 18 = 2 ⋅ {3}^{2}, 24 = {2}^{3} ⋅ 3, and 12 = {2}^{2} ⋅ 3. Then (18,24,12) = 2 ⋅ 3 = 6 and \mathop{lcm}\nolimits (18,24,12) = {2}^{3} ⋅ {3}^{2} = 72.
• Here 8 = {2}^{3}, 20 = {2}^{2} ⋅ 5, and 14 = 2 ⋅ 7. So (8,20,14) = 2 and \mathop{lcm}\nolimits (8,20,14) = {2}^{3} ⋅ 5 ⋅ 7 = 280.
• Verify: 2 ⋅ 280 = 560, 8 ⋅ 20 ⋅ 14 = 2240. So the two quantites are not equal. The product of the gcd and lcm only equals the product of the numbers when there are only two numbers involved or when no pairs of numbers any factors.

Problem 15

• (24,18) = 6, and (6,12) = 6. Also, \mathop{lcm}\nolimits (24,18) = 72 and \mathop{lcm}\nolimits (72,12) = 72. Both give the same result, as they must.
• (8,20) = 4, (4,14) = 2. \mathop{lcm}\nolimits (8,20) = 40, \mathop{lcm}\nolimits (40,14) = 280. Again, these agree.
• The gcd and lcm can be computed pairwise. That is, you can compute each over the first pair of numbers, then compute over that result and the next number, etc.

Problem 18

• Find the largest jump such that you can reach all the numbers when starting from zero.
• Take each number as a jump size. Find the first number where all the jumps land simultaneously.

Problem 25

This is looking for the least common multiple of 45 and 96. Think of it like the number line problem above. You mark a notch on each gear. Starting with that notch on zero, you roll each gear to generate the “jumps”. You are looking for the point where they coincide. So \mathop{lcm}\nolimits (45,96) =\mathop{ lcm}\nolimits (3 ⋅ 15,3 ⋅ 32) = 3 ⋅ 15 ⋅ 32 = 1440 teeth will go past. In terms of the smaller hear, this is 1440∕45 = \mathbf{32} revolutions.

25.2 Computing GCDs

Prime factorizations:

• 241 is prime. So (720,241) = 1.
• 64 = {2}^{6}, 336 = {2}^{4} ⋅ 3 ⋅ 7. (64,336) = {2}^{4} = 16.
• (-15,75) = (15,75). 15 = 3 ⋅ 5, 75 = 3 ⋅ {5}^{2}, so (-15,75) = 15.

Euclidean algorithm:

• \eqalignno{ 720 & = 2 ⋅ 241 + 238, & & \cr 241 & = 1 ⋅ 238 + 3, & & \cr 238 & = 79 ⋅ 3 + \mathbf{1} & & \cr 3 & = 3 ⋅ 1 + 0. & & }

  So (720,241) = \mathbf{1}.

• \eqalignno{ 336 & = 5 ⋅ 64 + \mathbf{16}, & & \cr 64 & = 4 ⋅ 16 + 0. & & }

  So (336,64) = 16.

• (-15,75) = (15,75):
  \eqalignno{ 75 = 5 ⋅\mathbf{15} + 0. & & }

  So (-15,75) = 15.

25.3 Computing LCMs

• \mathop{lcm}\nolimits (64,336) = 64 ⋅ 336∕(336,64) = 1344
• Both are prime, so \mathop{lcm}\nolimits (11,17) = 11 ⋅ 17 = 187
• \mathop{lcm}\nolimits (121,187) =\mathop{ lcm}\nolimits (1{1}^{2},11 ⋅ 17) = 1{1}^{2} ⋅ 17 = 2057
• \mathop{lcm}\nolimits (2025,648) =\mathop{ lcm}\nolimits ({3}^{3} ⋅ {5}^{2},{2}^{3} ⋅ {3}^{4}) = {2}^{3} ⋅ {3}^{4} ⋅ {5}^{2} = 16200

25.4 Linear Diophantine equations

• From a previous problem, we have that 336 = 64 ⋅ 5 + 16. Thus 336 ⋅ 1 + 64 ⋅-5 = 16 and 336 ⋅ 2 + 64 ⋅-10 = 32. So one solution is \mathbf{{x}_{0} = -10} and \mathbf{{y}_{0} = 2}. The general solution is x = {x}_{0} + t ⋅ 336∕(336,64) = -10 + 21t and y = {y}_{0} - t ⋅ 64∕(336,64) = 2 - 4t for any integer t. Another solution then is \mathbf{x(1) = -10 + 1 ⋅ 21 = 11} and \mathbf{y(1) = 2 - 4 ⋅ 1 = -2}.
• Here, (33,27) = (3 ⋅ 11,{3}^{3}) = 3. Now 3 ∤ 11, so there are no solutions.
• Now 31 is prime, so (31,27) = 1\mathrel{∣}11 and there are solutions. Running through the Euclidean algorithm we see that
  \eqalignno{ 31 & = 27 ⋅ 1 + 4, & & \cr 27 & = 4 ⋅ 6 + 3,\text{and} & & \cr 4 & = 3 ⋅ 1 + 1. & & }

  Starting from the bottom and substituting for the previous remainder,

  \eqalignno{ 4 + 3 ⋅ (-1) & = 1, & & \cr 4 + (27 + 4 ⋅ (-6)) ⋅-1 = 27 ⋅ (-1) + 4 ⋅ 7 & = 1, & & \cr 27 ⋅ (-1) + (31 + 27 ⋅ (-1)) ⋅ 7 = 31 ⋅ 7 + 27 ⋅ (-8) & = 1. & & \cr & & }

  We find that 31 ⋅ 7 + 27 ⋅ (-8) = 1, so 31x - 27y = 11 has an initial solution of \mathbf{{x}_{0} = 7 ⋅ 11 = 77} and \mathbf{{y}_{0} = -1 ⋅-8 ⋅ 11 = 88}.

  The general solutions have the form

  \eqalignno{ x = {x}_{0} + t {-27\over (31,27)} & = 77 - 27t,\text{ and} & & \cr y = {y}_{0} - t {31\over (31,27)} & = 88 - 31t, & & }

  Another solution is given by \mathbf{x(1) = 77 - 27 ⋅ 1 = 50} and \mathbf{y(1) = 88 - 31 ⋅ 1 = 57}.