서로소는 두 개 이상의 정수가 주어졌을 때, 그 정수들의 최대공약수가 1인 관계를 의미합니다. 즉, 두 수 사이에 공통된 약수가 1밖에 없는 경우를 말하죠. 예를 들어, 8과 15는 서로소 관계에 있습니다. 8의 약수는 1, 2, 4, 8이고, 15의 약수는 1, 3, 5, 15입니다. 두 수의 공통된 약수는 1뿐이므로 8과 15는 서로소입니다. 반면, 6과 9는 서로소가 아닙니다. 6의 약수는 1, 2, 3, 6이고, 9의 약수는 1, 3, 9입니다. 두 수의 공통된 약수가 1과 3이므로 최대공약수는 3이고, 따라서 서로소가 아닙니다.
서로소를 구하는 기본 원리
서로소를 구하는 가장 기본적인 방법은 두 수의 모든 약수를 나열하여 공통된 약수를 찾는 것입니다. 하지만 수가 커질수록 이 방법은 비효율적입니다. 따라서 우리는 최대공약수를 구하는 방법을 이용하여 서로소 관계를 파악할 수 있습니다. 두 수의 최대공약수가 1이면 두 수는 서로소입니다. 최대공약수를 구하는 대표적인 방법으로는 소인수분해와 유클리드 호제법이 있습니다.
1. 소인수분해를 이용한 서로소 판별
소인수분해는 어떤 자연수를 소수들의 곱으로 나타내는 방법입니다. 두 수의 소인수분해 결과에 공통된 소인수가 하나도 없다면, 그 두 수는 서로소입니다. 예를 들어, 12와 35를 살펴봅시다. 12를 소인수분해하면 2² × 3이 됩니다. 35를 소인수분해하면 5 × 7이 됩니다. 12와 35의 소인수분해 결과에는 공통된 소인수가 전혀 없습니다. 따라서 12와 35는 서로소입니다.
다른 예로, 10과 25를 봅시다. 10을 소인수분해하면 2 × 5가 되고, 25를 소인수분해하면 5²이 됩니다. 두 수 모두 소인수 5를 공통으로 가지고 있습니다. 따라서 10과 25는 서로소가 아닙니다.
2. 유클리드 호제법을 이용한 서로소 판별
유클리드 호제법은 두 수의 최대공약수를 효율적으로 구하는 알고리즘입니다. 두 수 a와 b(a > b)가 있을 때, a를 b로 나눈 나머지를 r이라고 합니다. 이때 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 과정을 나머지가 0이 될 때까지 반복하면, 마지막으로 0이 아닌 나머지가 최대공약수가 됩니다. 이 방법으로 구한 최대공약수가 1이면 두 수는 서로소입니다.
예를 들어, 48과 18의 최대공약수를 유클리드 호제법으로 구해봅시다.
- 48을 18로 나눕니다. 48 = 18 × 2 + 12
- 18을 나머지 12로 나눕니다. 18 = 12 × 1 + 6
- 12를 나머지 6으로 나눕니다. 12 = 6 × 2 + 0
나머지가 0이 되었으므로, 마지막으로 0이 아닌 나머지인 6이 48과 18의 최대공약수입니다. 최대공약수가 1이 아니므로 48과 18은 서로소가 아닙니다.
이번에는 17과 23의 최대공약수를 구해봅시다. 두 수 모두 소수이므로 서로소일 가능성이 높습니다.
- 23을 17로 나눕니다. 23 = 17 × 1 + 6
- 17을 나머지 6으로 나눕니다. 17 = 6 × 2 + 5
- 6을 나머지 5로 나눕니다. 6 = 5 × 1 + 1
- 5를 나머지 1로 나눕니다. 5 = 1 × 5 + 0
마지막으로 0이 아닌 나머지인 1이 17과 23의 최대공약수입니다. 최대공약수가 1이므로 17과 23은 서로소입니다.
서로소의 중요성
서로소 개념은 수학의 여러 분야에서 중요하게 활용됩니다. 예를 들어, 분수를 기약분수로 만들 때, 분자와 분모가 서로소인지 확인하는 과정이 필요합니다. 또한, 정수론에서는 서로소의 성질을 이용한 다양한 정리들이 존재합니다. 암호학에서도 서로소의 개념이 응용되기도 합니다. 따라서 두 수의 관계를 파악하고 더 깊은 수학적 이해를 돕는 데 있어 서로소를 구하는 방법을 아는 것은 매우 유용합니다.