Chapter 25
Solutions for eighth week’s assignments

Also available as PDF.

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 textbooks1 . 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
Problem 15
Problem 18
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

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

Prime factorizations:

Euclidean algorithm:

25.3 Computing LCMs

Compute the least common multiples:

25.4 Linear Diophantine equations

Find two integer solutions to each of the following, or state why no solutions exist: