잔글 (→성질) |
잔글 (→성질) |
||
| 14번째 줄: | 14번째 줄: | ||
== 성질 == | == 성질 == | ||
* 최대공약수는 유일하다 | * 최대공약수는 유일하다 | ||
* | * 정수 <math>a , b </math>에 대하여 <math>ax + by = ( a , b )</math>를 만족하는 정수 <math>x , y </math>가 존재한다. 또한 <math>x , y </math>가 임의의 정수일 때 <math>( a , b ) | ax+by</math>이다. | ||
== 유클리드 호제법 == | == 유클리드 호제법 == | ||
2015년 6월 28일 (일) 10:58 판
최대공약수(greatest common divisor, GCD 또는 gcd)는 두 수의 공약수 중에서 가장 큰 양수를 말한다. 보통 정수 범위에서 정의되며, [math]\displaystyle{ \Bbb Q[x] }[/math]에서 정의하기도 한다.
정의
최대공약수는 다음과 같이 정의된다.
- [math]\displaystyle{ \gcd ( a , b ) = ( a , b ) : = \max\{d: \; d\in \Bbb N, \; d|a \text{ and } d|b\} }[/math]
정의에 따라 [math]\displaystyle{ d=\gcd(a,b) }[/math]는
- [math]\displaystyle{ d \ge 1 , d | a , d | b }[/math]
- [math]\displaystyle{ k | a, \; k | b \Leftrightarrow k | d }[/math]
를 만족한다.
성질
- 최대공약수는 유일하다
- 정수 [math]\displaystyle{ a , b }[/math]에 대하여 [math]\displaystyle{ ax + by = ( a , b ) }[/math]를 만족하는 정수 [math]\displaystyle{ x , y }[/math]가 존재한다. 또한 [math]\displaystyle{ x , y }[/math]가 임의의 정수일 때 [math]\displaystyle{ ( a , b ) | ax+by }[/math]이다.