Mathematics 243, section 1 – Algebraic Structures Suggested Solutions, Problem Set 4 October 23, 2003

2.4/10. If b > 0 and a = qb + r (from division), then we want to show that gcd(a, b) = gcd(b, r).

We discussed one approach in the Problem Session. Here is a rather different way to do this one. Recall that if we define S_{a,b} = {ma+nb|m, n ∈ Z}, then the smallest (strictly) positive integer in S_{a,b} is d = gcd(a, b). The same is true for any two integers, so if we can show the two sets S_{a,b} = S_{b,r}, then the desired result follows. To show the equality, first note that any ma + nb ∈ S_{a,b} can be rewritten as:

\begin{aligned}ma + nb & = m(qb + r) + nb \\ & = (mq + n)b + mr, \end{aligned}

which is an element of S_{b,r}. Hence S_{a,b} ⊆ S_{b,r}. Conversely, any m′b + n′r can be rewritten as:

\begin{aligned}m′b + n′r & = m′b + n′(a − qb) \\ & = n′a + (m′ − qn′)b, \end{aligned}

which is an element of S_{a,b}. Hence S_{b,r} ⊆ S_{a,b}. So we have S_{b,r} = S_{a,b}, and gcd(b, r) = gcd(a, b).

2.4/11. The idea for this one is to consider the steps in the Euclidean algorithm and apply the result from problem 10 repeatedly:

a = q_{1}b + r_{1} ⇒ gcd(a, b) = gcd(b, r_{1})
b = q_{2}r_{1} + r_{2} ⇒ gcd(b, r_{1}) = gcd(r_{1}, r_{2})
⋮
r_{n−2} = q_{n}r_{n−1} + r_{n} ⇒ gcd(r_{n−2}, r_{n−1}) = gcd(r_{n−1}, r_{n})

(This can also be nicely phrased as a proof by induction!) Then assuming r_{n} is the last nonzero remainder, we have r_{n}|r_{n−1} in the next step so gcd(r_{n−1}, r_{n}) = r_{n}. Hence putting together the whole string of equalities,

gcd(a, b) = gcd(b, r_{1}) = gcd(r_{1}, r_{2}) = ⋯ = gcd(r_{n−1}, r_{n}) = r_{n}.

Note that it is this argument that shows the Euclidean algorithm actually “works”(!)

2.4/20 and 21. In the problem session, we worked out some of a “slick” way to solve 20 and 21 together. Namely (after multiplying by −1 as necessary) we can assume a, b > 0, and since d = gcd(a, b) satisfies d|(ab), we will have ab = md for some m ∈ Z. Then we just have to prove that the integer m satisfies the properties for a least common multiple given in problem 20.

(a) If we have “adjusted” a, b to make them positive, then no divisibility properties are changed and ab > 0, d > 0 imply m > 0.

(b) To show that a|m and b|m, note that d|a and d|b, so a = q_{1}d and b = q_{2}d for some integers q_{1}, q_{2}. Then substituting from a = q_{1}d into the equation ab = md gives (q_{1}d)b = md. We can cancel the d on both sides (since d > 0) to yield q_{1}b = m. Hence b|m. Similarly, substituting from b = q_{2}d into the equation ab = md gives a(q_{2}d) = md. We can cancel the d on both sides again to yield aq_{2} = m. Hence a|m.

(c) Now assume a|c and b|c. Then we must show m|c (where m is the integer from the equation ab = qm). We have c = an_{1} and c = bn_{2} for some integers n_{1}, n_{2} by hypothesis. Then we also know a = q_{1}d and b = q_{2}d for some integers q_{1}, q_{2} since d = gcd(a, b). Key observation: in these equations q_{1}, q_{2} must satisfy gcd(q_{1}, q_{2}) = 1. (Reason: if not, then we could factor an additional common divisor of a, b out of the q’s and d would not be the greatest common divisor). To use this observation, note that we can substitute for a, b in the equation ab = dm to get q_{1}q_{2}d^{2} = dm. Cancelling one factor of d implies:

(1)  q_{1}q_{2}d = m.

But now we also have from c = an_{1}, c = an_{2}: dq_{1}n_{1} = c = dq_{2}n_{2}, hence

(2)  q_{1}n_{1} = q_{2}n_{2}.

The key observation above says, for instance, that in (2) q_{2}|n_{1} (q_{2} has no factors > 1 in common with q_{1}, but it divides q_{1}n_{1}. Hence n_{1} = q_{2}k for some integer k. Therefore

c = an_{1} = (q_{1}d)(q_{2}k) = (q_{1}q_{2}d)k = mk.

(using (1)). Therefore m|c.

To show uniqueness, note that if m, m′ are two lcm’s of a, b, then property (c) says m|m′ and m′|m, so m = m′ (since both are positive).

Comments:

• There is also a nice way to use the fact that d = ma + nb for some integers m, n to show part (c) here.

• It is also possible to prove that there exists an integer satisfying these properties using a proof similar to what we did for the gcd: Namely, let

T_{a,b} = {c ∈ Z : a|c and b|c}

This is a set containing positive integers like the product ab. Hence the Well-Ordering property implies that T ∩ Z^{+} contains a smallest element. Let’s call that minimal strictly positive element m. Properties (a) and (b) are automatic for this m from the construction to show property (c) holds, take any c ∈ T_{a,b}, and divide m into it:

c = mq + r, 0 ≤ r ≤ m − 1

Since r = c−mq and c, m are in T_{a,b}, it is easy to see that a|r and b|r (like problem 16). So r ∈ T_{a,b}. But m was the smallest strictly positive element in T_{a,b}, and r ≤ m − 1. Hence r = 0, so m|c. (If you use this approach, though, then you still need to show that the formula in problem 21 holds!!!)