인 정수 를 와 의 공약수(common divisor)라고 한다.
또, 다음 세 조건을 만족시키는 정수 를 의 최대공약수(greatest common divisor)라 하고, 이것을 또는 로 나타낸다.
(ⅰ) ≥
(ⅱ) , 즉 는 와 의 공약수이다.
(ⅲ) 정수 에 대하여 이면 이다.
즉, 와 의 공약수는 모두 의 약수이다.
두 정수 에 대하여
인 정수 를 와 의 공배수(common multiple)라고 한다.
또 다음 세 조건을 만족시키는 정수 을 의 최소공배수(least common multiple)라 하고, 이것을 또는 로 나타낸다.
(ⅰ) ≥
(ⅱ) , 즉 는 와 의 공배수이다.
(ⅲ) 정수 에 대하여 이면 이다.
즉, 와 의 공배수는 모두 의 배수이다.
특히 인 경우에 최대공약수 는 의 양의 공약수 중에서 가장 크고, 또 최소공배수 는 의 양의 공배수 중에서 가장 작다.
[정리1] 두 정수 에 대하여 와 의 최대공약수 는 단 하나 존재한다.
그리고 ℤ ℤ ∈ ℤ 라고 하면,
ℤ ℤ ℤ 이고, 인 가 존재한다.1)
[증명] ℤ ℤ라고 하자. 임의의 두 정수 에 대하여 ⋅ ∈ ⋅ ∈
이므로 ℤ ⊂ ℤ ⊂ 이고 ≠ ∅이다. 그리고, 임의의 정수 에 대하여 ± ± ± ∈
1) 두 정수 와 의 최대공약수가 1일 때, 즉 일 때, 두 정수 는 서로 소(relatively prime)라고 한다.
이므로, 는 덧셈과 뺄셈에 관하여 닫혀 있으므로, ℤ ≥ 인 정수 가 존 재한다.
한편, ∈ ℤ ⊆ ℤ ∈ ℤ ⊆ ℤ이므로 이다. 또, ∈ ℤ 이므로 인 두 정수 가 존재한다. 따라서, 이면 이다. 그 러므로 는 의 최대공약수이다.
다음에, ′을 의 최대공약수라고 하면, 정의의 조건에 의하여
′ ′ ≥ ′≥ 이므로 ′이다.
[정리2] 두 정수 에 대하여 와 의 최소공배수 는 단 하나 존재하고 또 ℤ∩ℤ ℤ이다.
[증명] 먼저 ∈ ℤ∩ℤ이므로 ℤ∩ℤ ≠ ∅이다. 그리고 분명히 ℤ∩ℤ는 덧셈과 뺄셈에 대하여 닫혀 있으므로,
∈ ℤ∩ℤ ℤ ≥
인 정수 이 존재한다. 한편, ∈ ℤ ℤ∩ℤ이므로 이다.
그리고 이면, ∈ ℤ∩ℤ ℤ이므로 이다. 따라서 은 의 최소공 배수이다.
다음에 ′을 의 최소공배수라고 하면, 정의에 의하여 ′ ′ 이고 또
≥ ′≥ 이므로 ′이다.
[정리3] 유클리드의 알고리즘(Euclidean algorithm) 두 정수 에 대하여
라 할 때, 다음이 성립한다고 하자.
⋮ ⋮
⋮ ⋮
0
이 때, 이다. 그리고
≤ ≤
이라고 하면 다음이 성립한다.
≤ ≤
⋯
⋯
⋯
⋯
특히,
[증명] 나눗셈 알고리즘에 의하여 정수 ⋯ 과 ⋯ 이 존재하고,
⋯ 이 성립한다.
다음에 인 경우에 다음 등식이 성립한다.
∙ ∙
∙ ∙ 이제 ≤ ≤ 일 때, ⋯ 에 대하여 등식
가 성립한다고 가정하면 다음이 성립한다.
따라서 ⋯ 에 대하여 이다(박승안외1인, 2002)
유클리드 알고리즘이 실생활 문제를 푸는데 어떻게 활용될 수 있는지 살펴보자.
이번 주말에 실시하는 봉사 활동에 참여하는 학생 수가 남학생 5460명, 여학생 3234명이다. 각 조에 속하는 남학생과 여학생 각각의 인원수가 같도록 여러 개의 조로 나누어 봉사 활동을 실시할 때, 될수록 많은 조로 나누는 방법을 알아보자. 각 조에 속하는 남학생과 여학생 각각의 인원수가 같아야 하고, 될수록 많은 조로 나 누어야 하므로, 구하는 조의 수가 5460과 3234의 최대공약수이다. 5460과 3234 의 최대공약수는
× ×
× × × × ×
× × × ×
이므로, 42개의 조로 나누면 된다. 그런데 5460, 3234처럼 작은 수가 아니고 10자 리 이상의 큰 수가 나오면 소인수 분해 자체가 어렵기 때문에 위와 같은 방법으로 최대공약수를 구하는 것은 무리이다. 따라서 유클리드 알고리즘을 이용하여야만 구할 수 있다. 그러면 여기서 유클리드 알고리즘으로 구하는 방법에 대해서 살펴보 자.
우선 유클리드 알고리즘에 의해 다음의 식을 구할 수 있다.
5460=3234×1+2226 3234=2226×1+1008 2226=1008×1+ 210 1008= 210×4+168
210= 168×1+ 42 168= 42×4+ 0
위의 등식에 의해 우리는 42가 최대공약수라는 것을 알 수 있다.
주어진 두 수의 최대공약수를 구하기 위해 현행 중학교 교과서에서 제시된 방법은, 두 수를 소인수분해하여 공통으로 존재하는 소수들을 곱함으로써 최대공약수를 구 할 수 있다는 것이다. 이러한 방법과 비교하여 유클리드 알고리즘을 분석해 보면, 주어진 수의 크기가 작을 때는 유클리드 알고리즘의 유용성이 적다고 보여 질 수 있지만, 조금만 더 수가 커지면 중학교 교과서에 있는 것처럼 소인수 분해를 해서 최대공약수를 구한다는 것은 너무도 힘들 것이다. 이때에 유클리드 알고리즘의 유 용성이 빛을 발할 것이다(김영미, 2003).