유클리드 호제법의 증명
최대공약수를 구하는 문제는 단순 하지만 이해가 안되서 찾아보다가 알게 되었습니다.
철벽수학 성재혁 선생님 감사합니다.
GCD( A, B ) = GCD ( B , MOD( A,B ) ) 임을 증명하면 된다.
A = B*q + r 이라고 쓸 수 있다. 만약 A > B라면 아니면 바꿔주면 됨 // r = MOD(A,B)
A 와 B의 최대공약수는
A = n*k , B = m*k // ( m, n 은 서로소 ) 라고 가정할 수 있다.
그러면 r = A-Bq = nk - mkq 라고 쓸 수 있고
r = ( n - mq) k 여기서 r은 A의 공약수 임을 알게 된다.
B와 r의 최대공약수가 k가 되면 됨으로
B = m*k 에서 m 과 n-mg 가 서로소임을 증명하면 된다.
귀류법을 통해 m 과 n-mg가 서로소가 아니라면
m = xG / n-mg = yG
n - xGg = YG
n = (Y+xg)G // 이는 m = xG가 되므로 맨 처음 m,n 이 서로소라고 가정한 것에 모순된다.
증명끝
댓글