공통인 약수 중 가장 큰 수
12의 양의 약수는 1, 2, 3, 4, 6, 12이고 18의 양의 약수는 1, 2, 3, 6, 9, 18이다. 공통인 약수 가운데 가장 큰 수는 6이므로 최대공약수는 6이다. 두 수 중 작은 수와 최대공약수가 항상 같은 것은 아니다.
소인수로 구하기
각 수를 소인수분해한 뒤 공통으로 들어 있는 소인수를 공통된 지수만큼 곱할 수 있다. 한쪽에만 있는 소인수까지 넣으면 다른 수를 나누어떨어지게 하지 못한다. 최대공약수에서는 두 수 모두에 들어 있는 부분을 찾는다.
나머지를 이용하기
양의 정수 a를 b로 나눈 나머지가 r이면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 관계를 반복하는 것이 유클리드 호제법이다. 나머지가 0이 되었을 때 마지막으로 나누는 데 사용한 수가 최대공약수다. 큰 수의 모든 약수를 나열하지 않고도 계산할 수 있다.
약분과 서로소
분자의 수와 분모의 수를 최대공약수로 나누면 분수를 기약분수로 만들 수 있다. 두 양의 정수의 최대공약수가 1이면 서로소라고 한다. 서로소인 두 수가 각각 반드시 소수일 필요는 없다.