잔글 (→성질) |
(내용 추가) |
||
| 1번째 줄: | 1번째 줄: | ||
{{학술}} | {{학술}} | ||
'''최대공약수'''(greatest common divisor, '''GCD''' 또는 '''gcd''')는 두 수의 공약수 중에서 가장 큰 양수를 말한다. 보통 정수 범위에서 정의되며, <math>\Bbb Q[x]</math>에서 정의하기도 한다. | '''최대공약수'''(greatest common divisor, '''GCD''' 또는 '''gcd''')는 두 수의 공약수 중에서 가장 큰 양수를 말한다. 보통 정수 범위에서 정의되며, <math>\Bbb Q[x]</math>에서 정의하기도 한다. 기호로는 <math>\gcd\left(a,b\right)</math>로 표시하며, 더욱 줄이면 <math>\left(a,b\right)</math>로만 표시하는 경우도 있다. | ||
== 정의 == | == 정의 == | ||
최대공약수는 다음과 같이 정의된다. | 최대공약수는 다음과 같이 정의된다. | ||
: <math>\gcd ( a , b ) = ( a , b ) : = \max\{d: \; d\in \Bbb N, \; d|a \text{ and } d|b\}</math> | : <math>\gcd\left( a , b \right) = \left( a , b \right) : = \max\{d: \; d\in \Bbb N, \; d|a \text{ and } d|b\}</math> | ||
정의에 따라 <math>d=\gcd(a,b)</math>는 | 정의에 따라 <math>d=\gcd\left(a,b\right)</math>는 | ||
* <math>d \ge 1 , d | a , d | b</math> | * <math>d \ge 1 , d | a , d | b</math> | ||
* <math>k | a, \; k | b \Leftrightarrow k | d</math> | * <math>k | a, \; k | b \Leftrightarrow k | d</math> | ||
를 만족한다. | 를 만족한다. | ||
== 찾는 법 == | |||
예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다. | |||
{{인용문2|12: 1, 2, 3, 4, 6, 12 <br/> 18: 1, 2, 3, 6, 9, 18}} | |||
여기서 위아랫줄 모두 같이 있는 숫자가 '''공약수'''가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. '''최대공약수'''는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. [[참 쉽죠?]] | |||
하지만 두 수의 약수를 찾는게 어렵다면 어떻게 될까? 2015와 246의 최대공약수를 [[약수]]를 나열하는 방법으로 찾으려면 한참이 걸릴 것이다. 이 문제를 해결하기 위한 방법이 바로 유클리드 호제법. 놀랍게도 기원전에 발견된 인류 '''최초의 알고리즘'''이라고 한다. 자세한 것은 아랫 문단의 유클리드 호제법 참조. | |||
== 성질 == | == 성질 == | ||
1. 최대공약수는 유일하다 | |||
2. <math>\gcd\left(a,b\right)\geq1</math> | |||
3. <math>\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right)</math> | |||
4. <math>\gcd\left(a,0\right)=\left|a\right|</math> | |||
5. <math>d=\gcd\left(a,b\right)</math>라 하면, <math>\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1</math> | |||
6. 임의의 정수 <math>k</math>에 대하여, <math>\gcd\left(a,b\right)=\gcd\left(a+kb,b\right)</math> | |||
7. 정수 <math>a , b </math>에 대하여 <math>ax + by = \gcd\left( a , b \right)</math>를 만족하는 정수 <math>x , y </math>가 존재한다. 또한 <math>x , y </math>가 임의의 정수일 때 <math>\gcd\left( a , b \right) | ax+by</math>이다. | |||
== 증명 == | |||
2. <math>1\mid a,1\mid b</math>이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, <math>\gcd\left(a,b\right)\geq1</math>. | |||
3. <math>x\mid a</math>와 <math>x\mid -a</math>는 동치이다. 그런데 <math>\left|a\right|</math>는 <math>a</math> 또는 <math>-a</math>이므로 <math>a</math>와 <math>\left|a\right|</math>는 같은 [[약수]]를 갖는다. 마찬가지로, <math>b</math>와 <math>\left|b\right|</math>는 같은 약수를 갖는다. 따라서, <math>x</math>가 <math>a</math>와 <math>b</math>의 공약수라는 것은 <math>\left|a\right|</math>와 <math>\left|b\right|</math>의 공약수라는 사실과 동치이다. <math>\therefore\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right)</math> | |||
4. 3번으로 부터, <math>\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)</math>이다. <math>\left|a\right|\cdot0=0</math>이므로, <math>\left|a\right|\mid0</math>. 또한, <math>\left|a\right|\mid\left|a\right|</math>이므로, <math>\left|a\right|</math>는 <math>\left|a\right|</math>와 0의 공약수이다. 그러므로 <math>\left|a\right|\leq\gcd\left(\left|a\right|,0\right)</math>이다. 그런데 <math>\gcd\left(\left|a\right|,0\right)\mid\left|a\right|</math>이므로, <math>\gcd\left(\left|a\right|,0\right)\leq\left|a\right|</math>. 위 두 부등식으로 부터 <math>\gcd\left(\left|a\right|,0\right)=\left|a\right|</math>. 다시 한번 2번으로 부터, <math>\gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)=\left|a\right|</math>. | |||
5. <math>a=dm, b=dn</math>라 하면, <math>\gcd\left(\frac{a}{d},\frac{b}{d}\right)=\gcd\left(m,n\right)</math>이다. 양의 정수 <math>p</math>가 <math>p\mid m,p\mid n</math>를 만족한다고 하자. 그러면 <math>m=pe,n=pf</math>를 만족하는 정수 <math>e,f.</math>가 존재한다. 따라서, <math>a=dpe,b=dpf</math>이고 <math>dp</math>는 <math>a,b</math>의 공약수이다. 한편, <math>d</math>는 최대공약수이므로, <math>d\geq dp</math>. 따라서 <math>p\leq1</math>이고 <math>p=1</math>일 수 밖에 없다. 이로써 보이고자 하는 바가 증명되었다. | |||
6. 만약 <math>x</math>가 <math>a,b</math>의 공약수라면, <math>x\mid a,x\mid b</math>이다. 따라서 <math>x\mid kb</math>이고, <math>x\mid a+kb</math>이다. 따라서 <math>x</math>는 <math>a+kb</math>와 <math>b</math>의 공약수이다. | |||
역으로, <math>x</math>가 <math>a+kb</math>와 <math>b</math>의 공약수라면, <math>x\mid a+kb, x\mid b</math>이다. 따라서 <math>x\mid kb</math>이고, <math>x\mid\left(\left(a+kb\right)-kb\right)=a</math>이다. 즉, <math>x</math>는 <math>a,b</math>의 공약수이다. 따라서 <math>a,b</math>와 <math>a+kb,b</math>는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다. | |||
7. 집합 <math>A=\left\{ax+by|x,y\in\right.</math>ℤ, <math>\left.ax+by>0\right\}</math>를 생각하자. 집합 <math>A</math>는 [[자연수]]의 부분집합이고 공집합이 아니므로 well-ordering 원리에 의해 가장 작은 원소가 존재한다. 이를 <math>d</math>라 하면 적당한 정수 <math>x,y</math>에 대해 <math>d=ax+by</math>이다. 여기서 <math>d</math>가 최대공약수임을 보이면 증명이 끝난다. | |||
<math>d>0</math>이므로, [[나눗셈 정리]]에 의하여 <math>a=qd+r,\,0\leq r< d</math>인 정수 <math>q,r</math>가 존재한다. 그러면 <math>r=a-qd=a-q\left(ax+by\right)=a\left(1-qx\right)-b\left(qy\right)</math>이므로 <math>r> 0</math>이면 <math>r\in A</math>이고, <math>r< d</math>가 되어 <math>d</math>가 가장 작은 원소라는 사실에 모순된다. 따라서 <math>r=0</math>이고, <math>d\mid a</math>이다. 마찬가지로 <math>d\mid b</math>이다. 즉, <math>d\mid\gcd\left(a,b\right)</math>. | |||
한편 <math>e</math>가 <math>a,b</math>의 공약수라면 <math>e\mid\left(ax+by\right)</math>이고,<ref>5번 성질 참조</ref> <math>ax+by=d</math>이므로 <math>e\mid d</math>, 즉 <math>e\leq d</math>이다. 이는 곧 <math>d</math>가 최대공약수임을 보인다. | |||
== 유클리드 호제법 == | == 유클리드 호제법 == | ||
| 20번째 줄: | 53번째 줄: | ||
== 다항식의 최대공약수 == | == 다항식의 최대공약수 == | ||
[[ | == 관련 항목 == | ||
* [[약수]] | |||
* [[나눗셈 정리]] | |||
* [[최소공배수]] | |||
[[분류:정수론]] | [[분류:정수론]] | ||
{{각주}} | |||
2015년 7월 25일 (토) 07:29 판
최대공약수(greatest common divisor, GCD 또는 gcd)는 두 수의 공약수 중에서 가장 큰 양수를 말한다. 보통 정수 범위에서 정의되며, [math]\displaystyle{ \Bbb Q[x] }[/math]에서 정의하기도 한다. 기호로는 [math]\displaystyle{ \gcd\left(a,b\right) }[/math]로 표시하며, 더욱 줄이면 [math]\displaystyle{ \left(a,b\right) }[/math]로만 표시하는 경우도 있다.
정의
최대공약수는 다음과 같이 정의된다.
- [math]\displaystyle{ \gcd\left( a , b \right) = \left( a , b \right) : = \max\{d: \; d\in \Bbb N, \; d|a \text{ and } d|b\} }[/math]
정의에 따라 [math]\displaystyle{ d=\gcd\left(a,b\right) }[/math]는
- [math]\displaystyle{ d \ge 1 , d | a , d | b }[/math]
- [math]\displaystyle{ k | a, \; k | b \Leftrightarrow k | d }[/math]
를 만족한다.
찾는 법
예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다.
12: 1, 2, 3, 4, 6, 12
18: 1, 2, 3, 6, 9, 18
여기서 위아랫줄 모두 같이 있는 숫자가 공약수가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. 최대공약수는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. 참 쉽죠?
하지만 두 수의 약수를 찾는게 어렵다면 어떻게 될까? 2015와 246의 최대공약수를 약수를 나열하는 방법으로 찾으려면 한참이 걸릴 것이다. 이 문제를 해결하기 위한 방법이 바로 유클리드 호제법. 놀랍게도 기원전에 발견된 인류 최초의 알고리즘이라고 한다. 자세한 것은 아랫 문단의 유클리드 호제법 참조.
성질
1. 최대공약수는 유일하다
2. [math]\displaystyle{ \gcd\left(a,b\right)\geq1 }[/math]
3. [math]\displaystyle{ \gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right) }[/math]
4. [math]\displaystyle{ \gcd\left(a,0\right)=\left|a\right| }[/math]
5. [math]\displaystyle{ d=\gcd\left(a,b\right) }[/math]라 하면, [math]\displaystyle{ \gcd\left(\frac{a}{d},\frac{b}{d}\right)=1 }[/math]
6. 임의의 정수 [math]\displaystyle{ k }[/math]에 대하여, [math]\displaystyle{ \gcd\left(a,b\right)=\gcd\left(a+kb,b\right) }[/math]
7. 정수 [math]\displaystyle{ a , b }[/math]에 대하여 [math]\displaystyle{ ax + by = \gcd\left( a , b \right) }[/math]를 만족하는 정수 [math]\displaystyle{ x , y }[/math]가 존재한다. 또한 [math]\displaystyle{ x , y }[/math]가 임의의 정수일 때 [math]\displaystyle{ \gcd\left( a , b \right) | ax+by }[/math]이다.
증명
2. [math]\displaystyle{ 1\mid a,1\mid b }[/math]이므로, 두 수의 최대공약수는 1보다 크거나 같다. 즉, [math]\displaystyle{ \gcd\left(a,b\right)\geq1 }[/math].
3. [math]\displaystyle{ x\mid a }[/math]와 [math]\displaystyle{ x\mid -a }[/math]는 동치이다. 그런데 [math]\displaystyle{ \left|a\right| }[/math]는 [math]\displaystyle{ a }[/math] 또는 [math]\displaystyle{ -a }[/math]이므로 [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ \left|a\right| }[/math]는 같은 약수를 갖는다. 마찬가지로, [math]\displaystyle{ b }[/math]와 [math]\displaystyle{ \left|b\right| }[/math]는 같은 약수를 갖는다. 따라서, [math]\displaystyle{ x }[/math]가 [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ b }[/math]의 공약수라는 것은 [math]\displaystyle{ \left|a\right| }[/math]와 [math]\displaystyle{ \left|b\right| }[/math]의 공약수라는 사실과 동치이다. [math]\displaystyle{ \therefore\gcd\left(a,b\right)=\gcd\left(\left|a\right|,\left|b\right|\right) }[/math]
4. 3번으로 부터, [math]\displaystyle{ \gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right) }[/math]이다. [math]\displaystyle{ \left|a\right|\cdot0=0 }[/math]이므로, [math]\displaystyle{ \left|a\right|\mid0 }[/math]. 또한, [math]\displaystyle{ \left|a\right|\mid\left|a\right| }[/math]이므로, [math]\displaystyle{ \left|a\right| }[/math]는 [math]\displaystyle{ \left|a\right| }[/math]와 0의 공약수이다. 그러므로 [math]\displaystyle{ \left|a\right|\leq\gcd\left(\left|a\right|,0\right) }[/math]이다. 그런데 [math]\displaystyle{ \gcd\left(\left|a\right|,0\right)\mid\left|a\right| }[/math]이므로, [math]\displaystyle{ \gcd\left(\left|a\right|,0\right)\leq\left|a\right| }[/math]. 위 두 부등식으로 부터 [math]\displaystyle{ \gcd\left(\left|a\right|,0\right)=\left|a\right| }[/math]. 다시 한번 2번으로 부터, [math]\displaystyle{ \gcd\left(a,0\right)=\gcd\left(\left|a\right|,0\right)=\left|a\right| }[/math].
5. [math]\displaystyle{ a=dm, b=dn }[/math]라 하면, [math]\displaystyle{ \gcd\left(\frac{a}{d},\frac{b}{d}\right)=\gcd\left(m,n\right) }[/math]이다. 양의 정수 [math]\displaystyle{ p }[/math]가 [math]\displaystyle{ p\mid m,p\mid n }[/math]를 만족한다고 하자. 그러면 [math]\displaystyle{ m=pe,n=pf }[/math]를 만족하는 정수 [math]\displaystyle{ e,f. }[/math]가 존재한다. 따라서, [math]\displaystyle{ a=dpe,b=dpf }[/math]이고 [math]\displaystyle{ dp }[/math]는 [math]\displaystyle{ a,b }[/math]의 공약수이다. 한편, [math]\displaystyle{ d }[/math]는 최대공약수이므로, [math]\displaystyle{ d\geq dp }[/math]. 따라서 [math]\displaystyle{ p\leq1 }[/math]이고 [math]\displaystyle{ p=1 }[/math]일 수 밖에 없다. 이로써 보이고자 하는 바가 증명되었다.
6. 만약 [math]\displaystyle{ x }[/math]가 [math]\displaystyle{ a,b }[/math]의 공약수라면, [math]\displaystyle{ x\mid a,x\mid b }[/math]이다. 따라서 [math]\displaystyle{ x\mid kb }[/math]이고, [math]\displaystyle{ x\mid a+kb }[/math]이다. 따라서 [math]\displaystyle{ x }[/math]는 [math]\displaystyle{ a+kb }[/math]와 [math]\displaystyle{ b }[/math]의 공약수이다. 역으로, [math]\displaystyle{ x }[/math]가 [math]\displaystyle{ a+kb }[/math]와 [math]\displaystyle{ b }[/math]의 공약수라면, [math]\displaystyle{ x\mid a+kb, x\mid b }[/math]이다. 따라서 [math]\displaystyle{ x\mid kb }[/math]이고, [math]\displaystyle{ x\mid\left(\left(a+kb\right)-kb\right)=a }[/math]이다. 즉, [math]\displaystyle{ x }[/math]는 [math]\displaystyle{ a,b }[/math]의 공약수이다. 따라서 [math]\displaystyle{ a,b }[/math]와 [math]\displaystyle{ a+kb,b }[/math]는 같은 공약수 집합을 가지므로 최대공약수도 같아야 한다.
7. 집합 [math]\displaystyle{ A=\left\{ax+by|x,y\in\right. }[/math]ℤ, [math]\displaystyle{ \left.ax+by\gt 0\right\} }[/math]를 생각하자. 집합 [math]\displaystyle{ A }[/math]는 자연수의 부분집합이고 공집합이 아니므로 well-ordering 원리에 의해 가장 작은 원소가 존재한다. 이를 [math]\displaystyle{ d }[/math]라 하면 적당한 정수 [math]\displaystyle{ x,y }[/math]에 대해 [math]\displaystyle{ d=ax+by }[/math]이다. 여기서 [math]\displaystyle{ d }[/math]가 최대공약수임을 보이면 증명이 끝난다. [math]\displaystyle{ d\gt 0 }[/math]이므로, 나눗셈 정리에 의하여 [math]\displaystyle{ a=qd+r,\,0\leq r\lt d }[/math]인 정수 [math]\displaystyle{ q,r }[/math]가 존재한다. 그러면 [math]\displaystyle{ r=a-qd=a-q\left(ax+by\right)=a\left(1-qx\right)-b\left(qy\right) }[/math]이므로 [math]\displaystyle{ r\gt 0 }[/math]이면 [math]\displaystyle{ r\in A }[/math]이고, [math]\displaystyle{ r\lt d }[/math]가 되어 [math]\displaystyle{ d }[/math]가 가장 작은 원소라는 사실에 모순된다. 따라서 [math]\displaystyle{ r=0 }[/math]이고, [math]\displaystyle{ d\mid a }[/math]이다. 마찬가지로 [math]\displaystyle{ d\mid b }[/math]이다. 즉, [math]\displaystyle{ d\mid\gcd\left(a,b\right) }[/math]. 한편 [math]\displaystyle{ e }[/math]가 [math]\displaystyle{ a,b }[/math]의 공약수라면 [math]\displaystyle{ e\mid\left(ax+by\right) }[/math]이고,[1] [math]\displaystyle{ ax+by=d }[/math]이므로 [math]\displaystyle{ e\mid d }[/math], 즉 [math]\displaystyle{ e\leq d }[/math]이다. 이는 곧 [math]\displaystyle{ d }[/math]가 최대공약수임을 보인다.
유클리드 호제법
다항식의 최대공약수
관련 항목
각주
- ↑ 5번 성질 참조