Chapter 29
Solutions for eighth week’s assignments

29.1 Exercises 5.3

Problem 62

If (p,q) = p, then p\mathrel{∣}q and q is a multiple of p.

Problem 66

We want the least common multiple of 6 and 10. The nights off intersect every 30 days. July has 31 days, so by this method their next shared day off is the 31^st. On the “trick question” side, though, they may have July 4^th off together\mathop{\mathop{…}}

Problem 70

Here we need the greatest common divisor, (60,72) = 12. So the longest common length is 1 foot.

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

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