Natural Science1 최대공약수 알고리즘 유클리드 호제법 증명 유클리드 호제법의 증명최대공약수를 구하는 문제는 단순 하지만 이해가 안되서 찾아보다가 알게 되었습니다.철벽수학 성재혁 선생님 감사합니다. 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가 서로.. 2018. 10. 12. 이전 1 다음