유클리드 호제법을 a, b에 적용할 때 나오는 나머지 b=r0, r1, r2...에서 모든 i에 대해 r(i+2) 먼저 유클리드 호제법에서 r(i) = r(i+1)q(i+1) + r(i+2) 다.유클리드 호제법에선 모든 r >= 0이고, q>0이므로0 그리고 q(i+1)를 기준으로 경우를 나눠 살펴보자.if q(i+1) = 1?r(i) = r(i+1)q(i+1) + r(i+2) = r(i+1) + r(i+2)이다.여기서 r(i+1) > r(i+2) 이므로2r(i+2) 따라서 q=1이면 r(i+2)if q(i+1) >= 2?r(i+2) = r(i) - r(i+1)q(i+1)에서 q(i+1) >= 2 이므로r(i+1)q(i+1) >= 2r(i+1)즉, r(i) = r(i+2) + r(i+1)q(i+1) >=..