최대공약수: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
|||
1번째 줄:
'''최대공약수'''(最大公約數)란, [[0]]이 아닌 두 [[정수]]나 [[다항식]]의 공통되는 [[약수]] 중에서 가장 큰 수를 말한다.
두 정수 ''a''와 ''b''의 최대공약수를 기호로 <math>\gcd ( == 특징 ==
* gcd(''a, b'')는 ''a''와 ''b''의 약수이다.
* 두 수 또는 다항식의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다.
*: gcd(''a, b'') · lcm(''a, b'') = ''a·b''
* a와 b의 최대공약수 gcd(''a, b'')의 값은 ''ax'' + ''by'' 꼴의 수(''x, y''는 정수) 중 가장 작은 양수의 값과 같다.
* 만약 두 정수의 최대공약수가 1과 -1밖에 없는 경우, 이 두 수는 [[서로소 (수론)|서로소]]라고 부른다.
* 만약 두 다항식의 상수 이외의 최대공약수가 없을 경우, 이 두 다항식은 서로소라고 부른다.
== 계산법 ==
두 수 a와 b의 최대공약수를 구하는 방법은 [[소인수분해]]를 사용하는 방법과 [[유클리드 호제법]]이 있다.
두 수 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이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다. 이를 수식화 한 것은 호제법 문서를 참조하라.
== 컴퓨터 프로그래밍 ==
| |||