최대공약수와 최소공배수

최대공약수(greatest common divisor)란

우선 먼저 공약수에 대해 알아보면, 공약수란 두 숫자 사이에 공통으로 존재하는 약수를 의미합니다.

예를들어, 10과 15는 공통적으로 5라는 약수를 가지고 있고, 이것을 공약수라고 합니다.

그리고 공약수 중에서 가장 큰 숫자를 최대공약수라고 합니다.

 

최대공약수를 구하는 방법

1. 최대공약수를 구하는 방법은 두 숫자의 약수를 모두 쓴 다음 공약수를 찾아서 가장 큰 값을 찾아준다.

2. 소인수분해를 통해서 공통된 인수를 골라서 남겨준다.

 

예시)

36과 60의 최대공약수를 구하면

우선 먼저 36과 60을 소인수분해 합니다.

 

\(36=2\times2\times3\times3=2^2\times3^2\)

\(60=2\times2\times3\times5=2^2\times3\times5\)

 

그리고, 공통된 인수를 최대한 모두 선택합니다.

2는 최대 \(2^2\)까지 공통적으로 가지며, 3은 \(3^1\)만을 공통적으로 가지고,

5는 공통인수가 아닙니다. 즉, 최대공약수는 결국...

\(2^2\times3=12\)가 됩니다.

 

말하자면, 인수의 '교집합'이라고 생각하면 되겠습니다.

 

---

최소공배수(least common multiple)란

위의 개념과 마찬가지로, 두 수의 공통적인 배수를 공배수라고 합니다.

공배수는 무한히 많이 존재하는데, 공배수 중에서 제일 작은 공배수는 1개로 유일하며

그것을 최소공배수라고 합니다.

 

최소공배수 구하는 방법

최대공약수를 구할때와 마찬가지로 소인수분해를 한 다음 두 수 의 약수를 모두 포함시켜 만들면 됩니다.

 

예시)

36과 60의 최소공배수를 구하면

역시 우선 먼저 36과 60을 소인수분해 합니다.

 

\(36=2\times2\times3\times3=2^2\times3^2\)

\(60=2\times2\times3\times5=2^2\times3\times5\)

 

그리고, 두 숫자의 인수를 모두 포함시킬 수 있도록 합니다.

2는 \(2^2\)가 같으므로 \(2^2\)를, 3은 \(3^2\)에 3이 포함되므로 \(3^2\)을,

5는 공통인수가 없으므로 5를 포함하여 계산하면,

 

최소공배수\(=2^2\times3^2\times5=180\)

 

말하자면, 인수들의 '합집합'이라고 생각하면 되겠습니다.

 

---

최대공약수와 최소공배수의 관계

a와 b의 최대공약수와 최소공배수를 곱하면 어떻게 될까?

결론부터 말하면 두 수의 곱인 ab의 값이 됩니다.

 

증명)

A. 36과 60의 최대공약수는 12, 최소공배수는 180

그리고 그 곱은 \(12\times180=2160\)

 

B. 36과 60의 곱은 

\(36\times60=2160\)

 

A = B

 

 

다시말해, 최대공약수(교집합)과 최소공배수(합집합) 사이의 곱은

결국 각 숫자의 곱과 마찬가지입니다.