최대공약수(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 에 대하여 \lt math\gt ax + by = ( a , b ) }[/math]를 만족하는 정수 [math]\displaystyle{ x , y }[/math]가 존재한다. 또한 [math]\displaystyle{ x , y }[/math]가 임의의 정수일 때 [math]\displaystyle{ ( a , b ) | ax+by }[/math]이다.