편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
{{학술}} | |||
'''최대공약수'''(greatest common divisor, '''GCD''' 또는 '''gcd''')는 두 수의 공약수 중에서 가장 큰 양수를 말한다. 보통 정수 범위에서 정의되며, <math>\Bbb Q[x]</math>에서 정의하기도 한다. 기호로는 <math>\gcd\left(a,b\right)</math>로 표시하며, 더욱 줄이면 <math>\left(a,b\right)</math>로만 표시하는 경우도 있다. | '''최대공약수'''(greatest common divisor, '''GCD''' 또는 '''gcd''')는 두 수의 공약수 중에서 가장 큰 양수를 말한다. 보통 정수 범위에서 정의되며, <math>\Bbb Q[x]</math>에서 정의하기도 한다. 기호로는 <math>\gcd\left(a,b\right)</math>로 표시하며, 더욱 줄이면 <math>\left(a,b\right)</math>로만 표시하는 경우도 있다. | ||
16번째 줄: | 16번째 줄: | ||
여기서 위아랫줄 모두 같이 있는 숫자가 '''공약수'''가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. '''최대공약수'''는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. [[참 쉽죠?]] | 여기서 위아랫줄 모두 같이 있는 숫자가 '''공약수'''가 된다. 즉, 이 경우에는 1, 2, 3, 6이 공약수가 된다. '''최대공약수'''는, 찾은 공약수 중 가장 큰 것, 즉 이 경우에는 6이 최대공약수가 된다. [[참 쉽죠?]] | ||
하지만 두 수의 약수를 | 하지만 두 수의 약수를 찾는게 어렵다면 어떻게 될까? 2015와 246의 최대공약수를 [[약수]]를 나열하는 방법으로 찾으려면 한참이 걸릴 것이다. 이 문제를 해결하기 위한 방법이 바로 유클리드 호제법. 놀랍게도 기원전에 발견된 인류 '''최초의 알고리즘'''이라고 한다. 자세한 것은 아랫 문단의 유클리드 호제법 참조. | ||
== 성질 == | == 성질 == | ||
48번째 줄: | 48번째 줄: | ||
<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>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>가 최대공약수임을 보인다. | 한편 <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>가 최대공약수임을 보인다. | ||
== 유클리드 호제법 == | |||
== 다항식의 최대공약수 == | == 다항식의 최대공약수 == |