1. 공약수와 공배수
최대공약수와 최소공배수를 이해하기 위해 먼저 공약수와 공배수를 알아보자.
공약수
두 수의 공통인 약수를 공약수라고 한다.
예를 들어 12와 18의 약수는 다음과 같다.
12의 약수
$$
1,\ 2,\ 3,\ 4,\ 6,\ 12
$$
18의 약수
$$
1,\ 2,\ 3,\ 6,\ 9,\ 18
$$
공통으로 나타나는 약수는
$$
1,\ 2,\ 3,\ 6
$$
이므로 이것이 공약수이다.
공배수
두 수의 공통인 배수를 공배수라고 한다.
예를 들어
12의 배수
$$
12,\ 24,\ 36,\ 48,\ 60,\ \cdots
$$
18의 배수
$$
18,\ 36,\ 54,\ 72,\ \cdots
$$
공통으로 나타나는 배수는
$$
36,\ 72,\ 108,\ \cdots
$$
이다.
2. 최대공약수
두 수 이상의 공약수 중 가장 큰 수를 최대공약수라고 한다.
기호로는
$$
\gcd
$$
또는
$$
GCD
$$
를 사용하기도 한다.
예제 1
12와 18의 최대공약수를 구하시오.
12의 약수
$$
1,\ 2,\ 3,\ 4,\ 6,\ 12
$$
18의 약수
$$
1,\ 2,\ 3,\ 6,\ 9,\ 18
$$
공약수
$$
1,\ 2,\ 3,\ 6
$$
가장 큰 공약수는
$$
6
$$
따라서 최대공약수는
$$
6
$$
이다.
3. 최소공배수
두 수 이상의 공배수 중 가장 작은 수를 최소공배수라고 한다.
기호로는
$$
\operatorname{lcm}
$$
또는
$$
LCM
$$
을 사용한다.
예제 2
12와 18의 최소공배수를 구하시오.
12의 배수
$$
12,\ 24,\ 36,\ 48,\ \cdots
$$
18의 배수
$$
18,\ 36,\ 54,\ 72,\ \cdots
$$
가장 작은 공배수는
$$
36
$$
이므로 최소공배수는
$$
36
$$
이다.
4. 소인수분해를 이용한 최대공약수
큰 수의 경우 약수를 모두 찾는 것은 어렵다.
이때 소인수분해를 이용하면 쉽게 구할 수 있다.
예제)
24와 36의 최대공약수를 구하시오.
먼저 소인수분해한다.
$$
24 = 2^3 \times 3
$$
$$
36 = 2^2 \times 3^2
$$
공통으로 있는 소인수만 선택한다.
$$
2^2,\ 3
$$
지수가 작은 것을 선택한다.
따라서
$$
\gcd(24,36)=2^2 \times 3
$$
$$
=4 \times 3
$$
$$
=12
$$
최대공약수 구하는 방법
-
각 수를 소인수분해한다.
-
공통으로 나타나는 소인수를 찾는다.
-
지수는 더 작은 것을 선택한다.
-
모두 곱한다.
5. 소인수분해를 이용한 최소공배수
예제)
24와 36의 최소공배수를 구하시오.
소인수분해
$$
24 = 2^3 \times 3
$$
$$
36 = 2^2 \times 3^2
$$
모든 소인수를 사용한다.
지수는 더 큰 것을 선택한다.
따라서
$$
\operatorname{lcm}(24,36)
=2^3 \times 3^2
$$
$$
=8 \times 9
$$
$$
=72
$$
최소공배수 구하는 방법
-
각 수를 소인수분해한다.
-
나타난 모든 소인수를 적는다.
-
지수는 더 큰 것을 선택한다.
-
모두 곱한다.
6. 최대공약수와 최소공배수의 관계
두 자연수 $$a$$, $$b$$에 대하여
$$
a \times b\gcd(a,b)\times\operatorname{lcm}(a,b)
$$
가 성립한다.
예제 3
24와 36에 대해 확인해 보자.
최대공약수
$$
12
$$
최소공배수
$$
72
$$
따라서
$$
12 \times 72=864
$$
한편
$$
24 \times 36=864
$$
두 값이 같음을 확인할 수 있다.
7. 최대공약수의 활용
예제 4
사과 24개와 배 36개를 남김없이 똑같이 나누어 담으려고 한다.
만들 수 있는 상자의 최대 개수는?
사과와 배가 모두 똑같이 나누어져야 하므로
$$
\gcd(24,36)
$$
을 구한다.
$$
\gcd(24,36)=12
$$
따라서
$$
12
$$
개의 상자를 만들 수 있다.
8. 최소공배수의 활용
예제 5
A 버스는 12분마다 출발하고
B 버스는 18분마다 출발한다.
두 버스가 동시에 출발한 후 다시 함께 출발하는 시간은?
$$
\operatorname{lcm}(12,18)
$$
을 구한다.
$$
12=2^2 \times 3
$$
$$
18=2 \times 3^2
$$
따라서
$$
\operatorname{lcm}=(12,18)2^2 \times 3^2=36
$$
즉,
$$
36
$$
분 후에 다시 함께 출발한다.
9. 예제 문제
예제 6
18과 30의 최대공약수를 구하시오.
$$
18=2 \times 3^2
$$
$$
30=2 \times 3 \times 5
$$
공통 인수
$$
2,\ 3
$$
따라서
$$
\gcd(18,30)=2 \times 3
6
$$
예제 7
18과 30의 최소공배수를 구하시오.
모든 소인수를 사용하면
$$
\operatorname{lcm}(18,30)=2 \times 3^2 \times 5
$$
$$
=90
$$
10. 핵심 정리
최대공약수
-
공약수 중 가장 큰 수
-
공통 소인수의 지수가 작은 것을 선택한다.
예)
$$
24=2^3 \times 3
$$
$$
36=2^2 \times 3^2
$$
$$
\gcd(24,36)=2^2 \times 3=12
$$
최소공배수
-
공배수 중 가장 작은 수
-
모든 소인수의 지수가 큰 것을 선택한다.
예)
$$
24=2^3 \times 3
$$
$$
36=2^2 \times 3^2
$$
$$
\operatorname{lcm}(24,36)=2^3 \times 3^2=72
$$
중요한 공식
$$
a \times b=\gcd(a,b)\times\operatorname{lcm}(a,b)
$$
최대공약수는 “공통 부분”,
최소공배수는 “모든 부분”을 사용한다는 점을 기억하자.