1. If x | (a,b), then x | a and x | b, so x | qb and x | a – qb = r, so x | (b,r). If x | (b,r), x | b and x | r, so x | qb and hence x | r + qb = a, so x | (a,b). Consequently, (a,b) = (b,r).

3. There are multiple approaches, so I’ve done each of these differently.

187 = 11*17, 221 = 13*17, so (187,221) = 17.

6188 = 2*2*7*13*17. 2, 7, and 13 do not divide 4709, but 17 does, so (6188,4709) = 17.

314 = 159 + 155

159 = 155 + 4

155 = 38*4 + 3

4 = 3 + 1

3 = 3*1 + 0, so (314,159) = 1.

5. Since I used the Euclidean algorithm to find (314,159) in #3, I’ll do that one.

1 = 4 – 3, so \

1 = 4 – (155 – 38*4) = 39*4 – 155, so

1 = 39(159 – 155) – 155 = 39*159 – 40*155, so

1 = 39*159 – 40(314 – 159) = 79*159 – 40*314.

6. If ax + by = c has solutions in integers, then (a,b) | a, (a,b) | b implies

(a,b) | ax + by = c. If (a,b) | c, let c = (a,b)*d. There exist m, n such that

am + bn = (a,b), so amd + bnd = c. x = md, y = nd are solutions in integers to

ax + by = c.

7. d = (a,b). Let a = da^/, b = db^/. There exist m, n such that am + bn = d, so

a^/md + b^/nd = d implies a^/m +b^/n = 1, so (a^/,b^/) = 1.

8. Given ax + by = c and ax₀ + by₀ = c, let (a,b) = d. Dividing gives us

and . Subtracting gives us

. (*)

= 1 implies | (x – x₀), so x – x₀ = t. Substituting this into (*) gives

y – y₀.

12. Let m be the number of sides of the regular polygon. Triangulation gives you that each angle is , which must go evenly into 360. Let c = . Then

(180 – c)m = 360, so c and 180 – c must each go evenly into 360. The divisors of 360 are

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, and 360.

The pairs in the list c and 180 – c occur for c = 60, 120, and 90.

c =60 yields 120m = 360, m = 3, giving 6 equilateral triangles.

c = 120 yields 60m = 360, m = 6, giving 3 regular hexagons.

c = 90 yields 90m = 360, m = 4, giving 4 squares.