Question

T'he goal of this problem is to establish the following remarkable result: Bezout's theorern. If a, be Z50, then 3x, y є Z such that gcd(a, b) = ax + by. Here ged(a, b) denotes the greatest common divisor of a and b (i.e. the largest positive integer that divides both a and b). Throughout this problem, we'll use the notation (a) Write down five numbers that live in 2Z +3Z. What's a simpler name for the set 2Z +3Z? Prove it. Hint: as a warm-up, show that if n E 27Z +3Z then 17n E 27Z+3Z. (This is just for your scratch-work)] (b) Given a, b E Z o, let d denote the smallest positive element of aZ + bZ. Prove that d | a and d | b. Hint: by the quotient-remainder theorem, we can rite a = qd+r What can you deduce about r?] (c) Given a, b e Zo, let d denote the smallest positive element of aZ+bZ. Suppose cE Zo is a common divisor of a and b, i.e. cla andc| b. Prove that e d (d) Prove Bézout's theorem (stated in the introduction to this problem). Your proof should be very short.

Answer 1

LI)

of a and b ? cla and 11b clan and ( l by 2 U Cl d