## Chapter 29Solutions for eighth week’s assignments

Also available as PDF.

### 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 31st. On the “trick question” side, though, they may have July 4th 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

Compute the following using both the prime factorization method and the Euclidean algorithm:

• (720,241)
• (64,336)
• (-15,75)

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

Compute the least common multiples:

• \mathop{lcm}\nolimits (64,336)
• \mathop{lcm}\nolimits (11,17)
• \mathop{lcm}\nolimits (121,187)
• \mathop{lcm}\nolimits (2025,648)
• \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