number theory

Euclidean Algorithm - 유클리드 호제법

# Definition $ a = bq + r(0 \le r = b,$ $GCD(a, b) = GCD(a-b, b) $ $g=GCD(a,b),$ $ \ a = gA,$ $ \ b =gB$ 라 두자. $ GCD(a-b, b) $ $= GCD(g(A-B), gB) $ 이기에 A-B와 B가 서로소임을 보이면 Lemma 1은 증명된다. 귀류법으로 $ GCD(A-B, B) = g_{A,B},$ $A-B = g_{A,B}M,\ B $ $= g_{A,B}N,\ g_{A,B} \neq 1$ 를 만족하는 $\exist..