HyeunJae's Blog HyeunJae's Blog

A와 B사이의 gcd (A > B) 의 값은 B 와 A와 B의 나머지(r)의 gcd와 같다는 성질은 고등학교 과정에서 배웠을것이다. 이번 글은 유클리드 호제법을 귀류법을 통해서 증명을 해보겠다. A = aG , B = bG 라고 두면 (G는 공통된 수) A와 B가 최대공약수가 될려면 a,b 가 서로소가 되야한다. A를 B로 나누고 나눈 몫이 q 나머지가 r 이라고 하면 A = q*B+r 이 되고 aG = q*bG+r이 된다. 정리하면 r = (a-q*b)G 꼴이되고 B = bG 가 나온다. 이때 유클리드 호제법이 성립할려면 (a-q*b)와 b가 서로소가 되야만 하는데 귀류법을 통해 조건을 부정해서 증명할 수 있다. 따라서 귀류법에 의하면(a-q*b)와 b가 서로소가 아니게 되는데 서로소가 아니라면 (a ..