위키백과

최대공약수: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
잔글 121.135.151.14 (토론)의 2개의 편집을 Jeresy723의 마지막 판으로 되돌림. (TW)
편집 요약 없음
1번째 줄:
[[수론]]에서, [[정수]]들의 '''공약수'''(公約數, {{llang|en|common divisor}})는 동시에 그들 모두의 [[약수]]인 정수다. 적어도 하나가 0이 아닌 정수들의 '''최대공약수'''(最大公約數, {{llang|en|greatest common divisor}}, 약자 GCD)는 공약수 가운데 가장 큰 하나다. [[다항식]]이나 [[환 (수학)|환]]의 원소에 대해서도 정의할 수 있다.
'''최대공약수'''(最大公約數,Greatest Common Divisor)란, [[0]]이 아닌 두 [[정수]]나 [[다항식]]의 공통되는 [[약수]] 중에서 가장 큰 수를 말한다.
두 정수 ''a''와 ''b''의 최대공약수를 기호로 <math>\gcd (a,b)</math>로 표기하거나, 더 간단히 <math>(a,b)</math>로도 표기한다. 예를 들면,
 
== 특징정의 ==
두 [[정수]] <math>n,m\in\mathbb Z</math>의 '''공약수'''는 <math>n</math>의 약수이자 <math>m</math>의 약수인 정수이다. 모두 0이지는 않은 두 정수 <math>n,m\in\mathbb Z</math>의 '''최대공약수'''는 다음과 같은 여러 정의가 있으며, 이들은 서로 [[동치]]이다.
* gcd(''a, b'')는 ''a''와 ''b''의 약수이다.
* <math>n</math>, <math>m</math>의 가장 큰 공약수
* 두 수 또는 다항식의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다.
* <math>n</math>, <math>m</math>의 공약수이자, <math>n</math>, <math>m</math>의 모든 공약수의 [[배수]]인 양의 정수
*: gcd(''a, b'') · lcm(''a, b'') = ''a·b''
* <math>n</math>, <math>m</math>의 정수 계수 선형 결합인 최소 양의 정수
* a와 b의 최대공약수 gcd(''a, b'')의 값은 ''ax'' + ''by'' 꼴의 수(''x, y''는 정수) 중 가장 작은 양수의 값과 같다.
모두 0이지는 않은 두 정수의 최대공약수는 항상 존재하며, 항상 유일하다. 기호는 <math>\gcd\{n,m\}</math> 또는 <math>(n,m)</math>.
* 만약 두 정수의 최대공약수가 1과 -1밖에 없는 경우, 이 두 수는 [[서로소 (수론)|서로소]]라고 부른다.
* 만약 두 다항식의 상수 이외의 최대공약수가 없을 경우, 이 두 다항식은 서로소라고 부른다.
 
비슷하게, 여러 정수 <math>n_1,n_2,\dots,n_k\in\mathbb Z</math>의 '''공약수'''는 공통 약수이며, 모두 0이지는 않은 여러 정수 <math>n_1,n_2,\dots,n_k\in\mathbb Z</math>의 '''최대공약수''' <math>\gcd\{n_1,n_2,\dots,n_k\}</math>는 다음과 같은 서로 [[동치]]인 정의가 있다. 이는 항상 유일하게 존재한다.
== 계산법 ==
* 가장 큰 공약수
* 공약수이자, 모든 공약수의 배수인 양의 정수
* 정수 계수 선형 결합인 최소 양의 정수
* (재귀적 정의) <math>\gcd\{\gcd\{\gcd\{\cdots\gcd\{\gcd\{n_1,n_2\},n_3\}\cdots\},n_{k-1}\}n_k\}</math>
 
최대공약수가 1인 정수들을 '''[[서로소 (수론)|서로소]]'''라고 한다.
두 수 a와 b의 최대공약수를 구하는 방법은 [[소인수 분해]]를 사용하는 방법과 [[유클리드 호제법]]이 있다.
 
== 성질 ==
두 수 192와 72의 최대공약수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.
최대공약수는 다음과 같은 성질들을 가진다. (여기서 최대공약수를 취하는 정수들은 적어도 하나가 0이 아니라고 가정한다.)
 
약수 관계는 최대공약수를 통해 다음과 같이 나타낼 수 있다.
<math>192=2^6 \times 3=2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 3</math>
:<math>n\mid m\iff\gcd\{n,m\}=n</math>
공약수는 최대공약수의 [[약수]]와 [[동치]]이다.
:<math>k\mid n,m\iff k\mid\gcd\{n,m\}</math>
:<math>k\mid n_1,n_2,\dots,n_t\iff k\mid\gcd\{n_1,n_2,\dots,n_t\}</math>
최대공약수는 정수 계수 선형 결합으로 나타낼 수 있는 최소 양의 정수이다.
:<math>\gcd\{n,m\}=\min\{an+bm>0\colon a,b\in\mathbb Z\}</math>
:<math>\gcd\{n_1,n_2,\dots,n_t\}=\min\{a_1n_1+a_2n_2+\cdots+a_tn_t>0\colon a_1,a_2,\dots,a_t\in\mathbb Z\}</math>
최대공약수는 곱셈에 대한 분배 법칙을 만족시킨다.
:<math>\gcd\{nk,mk\}=\gcd\{n,m\}k</math>
:<math>\gcd\{n_1k,n_2k,\dots,n_tk\}=\gcd\{n_1,n_2,\dots,n_k\}k</math>
:<math>\gcd\left\{\frac nk,\frac mk\right\}=\frac{\gcd\{n,m\}}k\qquad(k\mid n,m)</math>
:<math>\gcd\left\{\frac{n_1}k,\frac{n_2}k,\dots,\frac{n_t}k\right\}=\frac{\gcd\{n_1,n_2,\dots,n_t\}}k\qquad(k\mid n_1,n_2,\dots,n_t)</math>
특히, 정수들을 최대공약수로 나눈 몫들은 [[서로소 (수론)|서로소]]다.
:<math>\gcd\left\{\frac n{\gcd\{n,m\}},\frac m{\gcd\{n,m\}}\right\}=1</math>
:<math>\gcd\left\{\frac{n_1}{\gcd\{n_1,n_2,\dots,n_t\}},\frac{n_2}{\gcd\{n_1,n_2,\dots,n_t\}},\dots,\frac{n_t}{\gcd\{n_1,n_2,\dots,n_t\}}\right\}=1</math>
정수들 가운데 하나에서 다른 하나와 서로소인 약수를 지워도 최대공약수가 변하지 않는다.
:<math>\gcd\{m,k\}=1\implies\gcd\{nm,k\}=\gcd\{n,k\}</math>
:<math>\gcd\{m,k\}=1\implies\gcd\{n_1,\dots,n_jm,\dots,n_t,k\}=\gcd\{n_1,\dots,n_t,k\}</math>
[[소인수분해]]가 주어진 정수들의 최대공약수는 공통된 소인수의 최소 지수 거듭제곱의 곱이다. 두 정수의 경우 소인수분해가 다음과 같다고 하자.
:<math>n=p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t}</math>
:<math>m=p_1^{f_1}p_2^{f_2}\cdots p_t^{f_t}</math>
:<math>e_1,e_2,\dots,e_t,f_1,f_2,\dots,f_t\in\mathbb Z_{\ge0}</math>
그렇다면, 최대공약수는 다음과 같다.
:<math>\gcd\{n,m\}=p_1^{\min\{e_1,f_1\}}p_2^{\min\{e_2,f_2\}}\cdots p_t^{\min\{e_t,f_t\}}</math>
두 정수의 최대공약수와 [[최소공배수]]의 관계는 다음과 같다.
:<math>\gcd\{n,m\}\operatorname{lcm}\{n,m\}=nm</math>
 
== 계산 ==
<math>72=2^3 \times 3^2=2 \times 2 \times 2 \times 3 \times 3</math>
최대공약수는 각 정수의 약수를 구하고, 공통되는 약수를 구하고, 가장 큰 하나를 구하면 얻을 수 있다. 예를 들어 12와 18의 경우, 12의 모든 약수는 (±) 1, 2, 3, 4, 6, 12이며, 18의 모든 약수는 (±) 1, 2, 3, 6, 9, 18이므로, 공약수는 (±) 1, 2, 3, 6이다. 가장 큰 6이 바로 최대공약수이다. 최대공약수를 구하는 방법은 그 밖에 [[소인수분해]]를 통한 방법과 [[유클리드 호제법]]을 통한 방법이 있다.
 
=== 소인수분해 ===
{{본문|소인수분해}}
두 수 192와 72의 최대공약수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.
:<math>192=2^6 \times 3=2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 3</math>
:<math>72=2^3 \times 3^2=2 \times 2 \times 2 \times 3 \times 3</math>
구하고 나면, 두 소인수 분해 결과의 중복되는 부분을 찾아 서로 곱한다. 두 결과에서 2가 세 번 중복되어 나오고 3이 한번 중복되어 나왔다. 즉 <math>2 \times 2 \times 2 \times 3=24</math> 최대공약수가 24라는 결론이 나온다.
 
 
그러나 일반적으로 소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.
 
=== 유클리드 호제법 ===
 
{{본문|유클리드 호제법}}
똑같이 두 수 192와 72의 최대공약수를 이번에는 호제법으로 구하여 보자. 일단 192을 72로 나누어 나머지를 구한다.
:<math>192=72 \times 2+48</math>
이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.
:<math>72=48 \times 1+24</math>
이와 같은 연산을 나머지가 0이 될 때까지 반복한다.
:<math>48=24 \times 2+0</math>
나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다.
 
이를 수식화 한 것은 호제법 문서를 참조하라.
<math>192=72 \times 2+48</math>이다. 이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.
 
== 관련 개념 ==
<math>72=48 \times 1+24</math>이다. 이와 같은 연산을 나머지가 0이 될 때까지 반복한다. <math>48=24 \times 2+0</math> 나머지가 0이 되었으므로 연산을 중지한다.
임의의 [[환 (수학)|환]] 위에서 최대공약수를 정의할 수 있다.
이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다. 이를 수식화 한 것은 호제법 문서를 참조하라.
 
== 컴퓨터 프로그래밍 ==
나머지를 구하는 %연산을 번갈아가며 구한다.
 
다음은 재귀 호출을 사용한 간단한 구현이다(C/C++/C#/Java).
<source lang="c">
int gcd(int p, int q)
{
if (q == 0) return p;
return gcd(q, p%q);
}
</source>
 
다음은 재귀 호출 대신 [[while 루프]]로 대체하고 [[제네릭 프로그래밍]]을 적용한 C++ 구현이다.
 
<source lang="cpp">
#include <utility>
#include <iostream>
 
template <class _Ty>
_Ty gcd(_Ty a, _Ty b) {
if ( a < b ) std::swap(a,b);
while ( b > 0 ) {
_Ty c = b;
b = a % b;
a = c;
}
return a;
}
 
int main() {
std::cout << "gcd(2,4) = " << gcd(2,4) << std::endl;
return 0;
}
</source>
 
== 같이 보기 ==
* [[약수]]
* [[공약수]]
* [[최소공배수]]
 
== 외부바깥 링크고리 ==
* {{네이버캐스트|6415id=6451|저자=서보억|날짜=2011-10-10}}
 
[[분류:수론]]
원본 주소 "https://ko.wikipedia.org/wiki/최대공약수"