Prove the theorem we mentioned in class about how to get continued fractions expansions from the Euclidean algorithm. Namely, suppose a, b Z are integers with a, b 1. Suppose the Euclidean algorithm applied to a and b goes as

b =q1a + r1

a =q2r1 + r2

. . .

rn1 =qn+1rn

for some n 0. Show that b/a = [q1; q2, . . . , qn+1]