최대공약수

요약 2개 이상의 수의 공약수 중에서 최대인 수이다.

이를 테면, 18의 약수는 1, 2, 3, 6, 9, 18 이고,12의 약수는 1, 2, 3, 4, 6, 12 로서 6이 최대공약수이며, 이것을 (12,18)＝6으로 쓴다. 다른 공약수는 모두 6의 약수이다.

최대공약수를 구하는 방법은, 우선 소인수(素因數)로 분해하여 공통의 수를 택하여 곱해주면 된다. 예를 들면 (12,18)을 구할 경우 12＝2²×3, 18＝2×3²이므로 (12,18)＝2×3＝6이 된다. 또, 주어진 수가 커서 하기 곤란할 때에는 유클리드의 호제법을 이용하는 것이 더 간편하다.

두 수 A,B의 최대공약수를 G, 또 A,B를 각각 G로 나누었을 때의 몫을 a,b라 하면, A＝aG, B＝bG인 관계가 성립한다. 이 때 a, b는 서로 소(素), 즉 (a,b)＝1이다. 또 A,B의 최소공배수가 L이면, LG＝AB인 관계가 성립한다.

세 수의 경우 (A,B,C)＝((A,B),C), 즉 두 수의 최대공약수와 나머지 한 수의 최대공약수를 구하면 결국 세 수의 최대공약수가 된다. 네 수 이상에서도 마찬가지로 생각할 수가 있다. 최소공배수에서도 ［A,B,C］＝［［A,B］,C］가 성립한다.