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

위키백과, 우리 모두의 백과사전.
내용 삭제됨 내용 추가됨
잔글 121.135.151.14 (토론)의 2개의 편집을 Jeresy723의 마지막 판으로 되돌림. (TW)
편집 요약 없음
1번째 줄: 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라는 결론이 나온다.
구하고 나면, 두 소인수 분해 결과의 중복되는 부분을 찾아 서로 곱한다. 두 결과에서 2가 세 번 중복되어 나오고 3이 한번 중복되어 나왔다. 즉 <math>2 \times 2 \times 2 \times 3=24</math> 최대공약수가 24라는 결론이 나온다.



그러나 일반적으로 소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.
그러나 일반적으로 소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.


=== 유클리드 호제법 ===

{{본문|유클리드 호제법}}
똑같이 두 수 192와 72의 최대공약수를 이번에는 호제법으로 구하여 보자. 일단 192을 72로 나누어 나머지를 구한다.
똑같이 두 수 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>


== 같이 보기 ==
== 같이 보기 ==
* [[약수]]
* [[공약수]]
* [[최소공배수]]
* [[최소공배수]]


== 외부 링크 ==
== 바깥 고리 ==
* {{네이버캐스트|6415}}
* {{네이버캐스트|id=6451|저자=서보억|날짜=2011-10-10}}

[[분류:수론]]

2017년 6월 27일 (화) 02:26 판

수론에서, 정수들의 공약수(公約數, 영어: common divisor)는 동시에 그들 모두의 약수인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수(最大公約數, 영어: greatest common divisor, 약자 GCD)는 공약수 가운데 가장 큰 하나다. 다항식이나 의 원소에 대해서도 정의할 수 있다.

정의

정수 공약수의 약수이자 의 약수인 정수이다. 모두 0이지는 않은 두 정수 최대공약수는 다음과 같은 여러 정의가 있으며, 이들은 서로 동치이다.

  • , 의 가장 큰 공약수
  • , 의 공약수이자, , 의 모든 공약수의 배수인 양의 정수
  • , 의 정수 계수 선형 결합인 최소 양의 정수

모두 0이지는 않은 두 정수의 최대공약수는 항상 존재하며, 항상 유일하다. 기호는 또는 .

비슷하게, 여러 정수 공약수는 공통 약수이며, 모두 0이지는 않은 여러 정수 최대공약수 는 다음과 같은 서로 동치인 정의가 있다. 이는 항상 유일하게 존재한다.

  • 가장 큰 공약수
  • 공약수이자, 모든 공약수의 배수인 양의 정수
  • 정수 계수 선형 결합인 최소 양의 정수
  • (재귀적 정의)

최대공약수가 1인 정수들을 서로소라고 한다.

성질

최대공약수는 다음과 같은 성질들을 가진다. (여기서 최대공약수를 취하는 정수들은 적어도 하나가 0이 아니라고 가정한다.)

약수 관계는 최대공약수를 통해 다음과 같이 나타낼 수 있다.

공약수는 최대공약수의 약수동치이다.

최대공약수는 정수 계수 선형 결합으로 나타낼 수 있는 최소 양의 정수이다.

최대공약수는 곱셈에 대한 분배 법칙을 만족시킨다.

특히, 정수들을 최대공약수로 나눈 몫들은 서로소다.

정수들 가운데 하나에서 다른 하나와 서로소인 약수를 지워도 최대공약수가 변하지 않는다.

소인수분해가 주어진 정수들의 최대공약수는 공통된 소인수의 최소 지수 거듭제곱의 곱이다. 두 정수의 경우 소인수분해가 다음과 같다고 하자.

그렇다면, 최대공약수는 다음과 같다.

두 정수의 최대공약수와 최소공배수의 관계는 다음과 같다.

계산

최대공약수는 각 정수의 약수를 구하고, 공통되는 약수를 구하고, 가장 큰 하나를 구하면 얻을 수 있다. 예를 들어 12와 18의 경우, 12의 모든 약수는 (±) 1, 2, 3, 4, 6, 12이며, 18의 모든 약수는 (±) 1, 2, 3, 6, 9, 18이므로, 공약수는 (±) 1, 2, 3, 6이다. 가장 큰 6이 바로 최대공약수이다. 최대공약수를 구하는 방법은 그 밖에 소인수분해를 통한 방법과 유클리드 호제법을 통한 방법이 있다.

소인수분해

두 수 192와 72의 최대공약수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.

구하고 나면, 두 소인수 분해 결과의 중복되는 부분을 찾아 서로 곱한다. 두 결과에서 2가 세 번 중복되어 나오고 3이 한번 중복되어 나왔다. 즉 최대공약수가 24라는 결론이 나온다.

그러나 일반적으로 소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.

유클리드 호제법

똑같이 두 수 192와 72의 최대공약수를 이번에는 호제법으로 구하여 보자. 일단 192을 72로 나누어 나머지를 구한다.

이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.

이와 같은 연산을 나머지가 0이 될 때까지 반복한다.

나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다.

이를 수식화 한 것은 호제법 문서를 참조하라.

관련 개념

임의의 위에서 최대공약수를 정의할 수 있다.

같이 보기

바깥 고리