Breakdowns °GCD(r02r1) GCD(ro,I1)=GCD(Im-1,Im=r 0=q1r1+ 2=qm-1 Im- tr gm Im GCD(ro, r1=GCD(m-1, rm=rBreakdowns • GCD(r0 , r1 ) • GCD(r0 , r1 ) = GCD(rm-1 , rm) = rm • r0 = q1 r1 + r2 • r1 = q2 r2 + r3 • … • rm-2 = qm-1 rm-1 + rm • rm-1 = qm rm • GCD(r0 , r1 ) = GCD(rm-1 , rm) = rm