유클리드 호제법 (+ 유클리드의 소수의 무한성 증명)

https://ddddewang.tistory.com/entry/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95%EC%9D%98-%EC%A6%9D%EB%AA%85-GCDabGCDbab

유클리드 호제법의 증명 | GCD(a,b)=GCD(b,a%b)

 

 

유클리드 호제법: 두 양의 정수 혹은 두 다항식의 최대공약수를 구하는 방법으로 a,b (a>b)일 때 a = bq + r (0<r<a)라고 한다면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 것

gcd(a,b) = gcd(b, r)과 같다는 것

*gcd(greatest common divisor): 최대공약수, commond divisor은 공약수

 

참고로 호제는 서로 나누기 때문에 붙여진 이름이라고 함 호제라는 단어가 따로 있지는 않음 (출처는 나무위키)

 

증명

a와 b의 최대공약수를 G라고 하자 ( gcd(a, b) = G, 그리고 gcd(b, r) = G' 라고 하자)

a = AG

b = BG

(A, B는 임의의 수)

전제 1)이때 A와 B는 서로소이며 A와 B 사이에서는 공약수가 없다 (G가 최대공약수이기 때문)

 

위의 a = bq + r을 변형해보면

AG = BGq + r

r = AG - BGq

r = G(A - Bq)

즉 r은 공약수로 G를 가진다 (이때까진 G가 r의 최대공약수인지는 모름)

 

이때 b와 r의 최대공약수가 G가 되려면 (A - Bq)와 b는 서로소여야 한다

 

이것을 귀류법으로 증명하기 위해

A - Bq = mt

b = nt

라고 하자 (이때 t는 공약수로 t라는 공약수가 존재한다고 하자, 즉 G가 r의 최대공약수가 아니라고 가정)

 

A - mtq = nt

A = nt + mtq

A = t(n + mq)

 

이때

B = nt 이므로

 

A와 B는 서로소라는 전제1을 위반하게 된다

 

즉 b와 A-Bq는 서로소이다

 

고로 a와 b의 최대공약수 또한 G이고 b와 r의 최대공약수 또한 G이다

 

즉 G(a, b) = G(a, a%b)이다

 

+ 소수의 무한성 증명

https://blog.naver.com/minsur30/220974405012

유클리드의 소수의 무한성 증명과 윌슨의 정리

 

 

요약

1. 핵심은 두 양의 정수 a 와 b가 G라는 최대공약수를 가질 때 a와 b는 서로소 A, B를 가지게 되는데 이때 r도 요래저래 해보면 공약수 G를 가진다 이때 G가 만약 r의 최대공약수가 아니라고 가정한다면 A, B가 서로소라는 전제를 위반하게 되므로 G는 r에서 또한 최대공약수이다

2. 소수가 유한하다고 가정하고 모든 소수를 곱한 다음 + 1을 해보자 그러면 이 수는 모든 소수로 나누어지지 않으므로 소수가 되므로 모든 소수를 곱한 수는 모순이 됨 그러므로 소수는 유한하지 않음