[정수론] 최대공약수(gcd) 와 선형조합(linear combination) 1부
Math/Numbers/Combinatorics2008. 4. 16. 01:39 |두 수의 최대공약수와 두수의 선형조합 사이의 밀접한 연관은 상당한 충격이었다. 단순한 직관만으로는 그 관계를 짐작하는 것이 쉽지 않기 때문이다. 기껏 떠올릴수 있는거라곤 gcd가 두수의 모든 선형조합을 나눌것이라는 것 정도???
아무튼, 최대공약수와 선형조합 사이의 관계는 정수론 뿐만 아니라, 집합론, 대수학 따위에서도 심심찮게 볼 수 있다는 것 만으로도, 중요성은 재삼 강조하지 않아도 될 것 같다.
그것은 다음과 같다.
증명.
a 와 b 의 선형조합중에서 양수인것들의 집합을 S 라고 하면, S = { ax + by > 0 | x , y ∈ Z } 이고 , 웰 오더링 프라퍼티에 의해 최소원소가 존재한다.
최소원소를 d = a x0 + b y0 라고 놓으면, 이제 우리가 보일것은 다음과 같다.
1) d 가 a 와 b 의 공약수 이며...
2) d 가 모든 공약수 중에 제일 크다.
세부 증명.
1) a 를 d 로 나누는 디비전 알고리듬을 생각하면... a = d q + r ( 0 <= r < d )
r 에 대해서 정리하면...
r = a - dq = a - (a x0 + b y0 ) q
= a ( 1 - q x0 ) + b ( - q y0 )
그러므로, r 이 0 보다 크다면 S 의 원소가 된다.
그런데, r 의 범위가 ( 0 <= r < d ) 이므로,
r 이 S 에 들어가게 된다면, d 가 최소라는 가정에 모순된다. 즉, r 은 0 이라는 말.
따라서, d 는 a 를 나눈다. 마찬가지로, b 도 나누게 되고.. 따라서, d 는 a 와 b 의 공약수이다.
2) a, b 의 임의의 양의 공약수를 c 라고 하면, c 는 a 도 나누고, b 도 나누기 때문에, 그것의 선형조합도 나누게 되고 따라서 d 도 나눈다.
다시 말해, a 와 b 의 모든 양의 공약수는 d 를 나눈다. 즉, d 보다 작거나 같다.
1) , 2) 에 의해 증명이 끝난다.
위 증명의 2) 로 부터 자명하지만, 굳이 명시적으로 다시 증명해보면 다음과 같이 할 수 있다.
따라서....
결과적으로, 다음의 중요한 사실을 알수 있다.
따라서...
증명은 a x0 + b y0 = (a,b) 에서, 양변을 (a,b) 로 나누면 a/ (a,b) 와 b/ (a,b) 가 서로소임을 알 수 있다.
역시, (a,b) 로 그냥 양변을 나누면 된다.
또다른 이야기로...
왜냐면, 선형조합이면 최대공약수의 배수이고 ( 즉, 최대공약수 보다 크거나 같다. ) 또한 공약수이므로 ( 즉, 최대공약수 보다 작거나 같다. ) 결과적으로 최대공약수가 된다.
이밖에도 많은 유용한 결과들이 유도된다. 나머지는 다음에 살펴보도록 한다.