서로소 계산기란?
두 정수의 공약수가 1뿐일 때, 이 두 수를 서로소(영어로 coprime 또는 relatively prime)라고 합니다. 다시 말해 두 수의 최대공약수(GCD)가 정확히 1인 경우입니다. 이 계산기에 두 정수를 입력하면 두 수가 서로소인지 여부와 함께 최대공약수를 바로 알려 줍니다.
사용 방법
a와 b 입력란에 정수 두 개를 넣고 계산 버튼을 누르세요. 계산기는 유클리드 호제법으로 \(\gcd(a,\ b)\)를 구합니다. 최대공약수가 1이면 두 수는 서로소이고, 1이 아니라면 공통인수를 가지므로 서로소가 아닙니다. 서로소 여부는 절댓값에만 영향을 받으므로 음수 부호는 무시됩니다.
공식 풀이
유클리드 호제법은 두 번째 값이 0이 될 때까지 \((a,\ b)\)를 \((b,\ a \bmod b)\)로 계속 바꿔 나갑니다. 이때 마지막으로 남은 0이 아닌 값이 바로 최대공약수입니다.
$$\text{Coprime} \iff \gcd\left(a,\ b\right) = 1$$
이 최대공약수가 1일 때에만 두 수는 서로소가 됩니다. 예를 들어 8과 15는 공통된 소인수가 없으므로 \(\gcd = 1\)이며, 둘 중 어느 것도 소수가 아니지만 서로소입니다.
예제로 알아보기
a = 12, b = 35인 경우를 살펴봅시다. 12의 소인수는 2와 3이고, 35의 소인수는 5와 7입니다. 공통된 소인수가 없으므로 $$\gcd(12,\ 35) = 1$$ 따라서 12와 35는 서로소입니다. 반면 12와 18은 6이라는 공통인수를 가지므로 \(\gcd = 6\)이 되어 서로소가 아닙니다.
자주 묻는 질문
서로소인 수는 반드시 소수여야 하나요? 아닙니다. 서로소란 1보다 큰 공통인수가 없다는 뜻일 뿐, 각 수 자체가 소수일 필요는 없습니다(예: 8과 9).
1은 모든 수와 서로소인가요? 네. 어떤 정수 n에 대해서도 \(\gcd(1,\ n) = 1\)이므로, 1은 모든 정수와 서로소입니다.
짝수 두 개가 서로소일 수 있나요? 아닙니다. 모든 짝수는 공통인수 2를 가지므로, 두 짝수의 최대공약수는 최소 2 이상입니다.
