서로소 계산기

서로소 계산기

선두 AI Skill PRO

계산 입력

공식

서로소⇔gcd⁡(a,b)=1\text{서로소} \iff \gcd\left(\text{a},\ \text{b}\right) = 1

계산 예

서로소⇔gcd⁡(84,126)=1=1\text{서로소} \iff \gcd\left(84,\ 126\right) = 1 = 1
사용 통계

광고

결과

84, 126: 서로소일까요?
아니요
gcd(84, 126) = 42
최대공약수 42
서로소 아니요 (gcd > 1)

이 페이지의 오류 신고

서로소 계산기란?

두 정수의 공약수가 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\)이며, 둘 중 어느 것도 소수가 아니지만 서로소입니다.

광고
공통 인수가 1뿐인 두 수를 겹치는 인수 집합으로 표현한 그림
두 수의 유일한 공통 인수가 1일 때 서로소이며, 따라서 \(\gcd(a,\ b) = 1\)입니다.

예제로 알아보기

a = 12, b = 35인 경우를 살펴봅시다. 12의 소인수는 2와 3이고, 35의 소인수는 5와 7입니다. 공통된 소인수가 없으므로 $$\gcd(12,\ 35) = 1$$ 따라서 12와 35는 서로소입니다. 반면 12와 18은 6이라는 공통인수를 가지므로 \(\gcd = 6\)이 되어 서로소가 아닙니다.

두 수를 gcd 1까지 줄이는 유클리드 호제법 단계
유클리드 호제법은 나머지가 \(\gcd = 1\)을 드러낼 때까지 두 수를 단계별로 줄입니다.

더 많은 서로소인 쌍의 예시

유클리드 알고리즘은 나머지가 0이 될 때까지 쌍 \((a,\ b)\)를 \((b,\ a \bmod b)\)로 반복적으로 대체합니다. 마지막 0이 아닌 나머지가 \(\gcd(a,b)\)이며, 그 값이 1일 정확히 그때 쌍이 서로소입니다.

예시 1 — 큰 서로소인 쌍: gcd(1071, 1024)

  1. \(1071 \bmod 1024 = 47\)
  2. \(1024 \bmod 47 = 37\)  (47 × 21 = 987이고 \(1024 - 987 = 37\)이기 때문)
  3. \(47 \bmod 37 = 10\)
  4. \(37 \bmod 10 = 7\)
  5. \(10 \bmod 7 = 3\)
  6. \(7 \bmod 3 = 1\)
  7. \(3 \bmod 1 = 0\) → 중지

마지막 0이 아닌 나머지는 \(1\)이므로 \(\gcd(1071, 1024) = \) 1. 판정: 1071과 1024는 서로소입니다(상호 소) — 둘 다 소수가 아니지만(\(1071 = 3 \times 3 \times 7 \times 17\)이고 \(1024 = 2^{10}\)), 공통 소인수를 가지지 않습니다.

예시 2 — 서로소가 아닌 쌍: gcd(84, 126)

  1. \(84 \bmod 126 = 84\), 따라서 첫 번째 단계는 쌍을 \((126,\ 84)\)로 단순히 교환합니다
  2. \(126 \bmod 84 = 42\)
  3. \(84 \bmod 42 = 0\) → 중지

마지막 0이 아닌 나머지는 \(42\)이므로 \(\gcd(84, 126) = \) 42. 판정: 84와 126은 서로소가 아닙니다. 인수분해로 확인: \(84 = 2^2 \times 3 \times 7\)이고 \(126 = 2 \times 3^2 \times 7\)이므로 공통 부분은 \(2 \times 3 \times 7 = 42\)입니다. 더 작은 수를 먼저 놓으면 하나의 추가 교환 단계만 필요합니다 — 알고리즘은 순서가 정해진 입력을 요구하지 않습니다.

예시 3 — 여전히 서로소인 두 합성수: gcd(25, 54)

  1. \(54 \bmod 25 = 4\)  (25 × 2 = 50이고 \(54 - 50 = 4\)이기 때문)
  2. \(25 \bmod 4 = 1\)  (4 × 6 = 24이고 \(25 - 24 = 1\)이기 때문)
  3. \(4 \bmod 1 = 0\) → 중지

마지막 0이 아닌 나머지는 \(1\)이므로 \(\gcd(25, 54) = 1\)입니다. 판정: 25와 54는 서로소입니다. 여기서 \(25 = 5^2\)이고 \(54 = 2 \times 3^3\)입니다. 소수 집합 \(\{5\}\)와 \(\{2, 3\}\)은 서로소입니다. 이것이 서로소성에 대한 핵심: 개별 수의 성질이 아니라 쌍의 성질입니다 — 어느 수도 소수일 필요가 없습니다.

광고

결과의 의미

계산기는 단일 숫자 \(d = \gcd(a,b)\)를 보고하며, 판정은 \(d\)가 1과 같은지 여부에 따릅니다. 각 경우는 표준 수론적 결과의 특정 집합을 가집니다.

gcd(a, b) = 1인 경우 — 수가 서로소

  • 분수 \(a/b\)는 이미 기약분수입니다. 분자와 분모에서 약분되는 1보다 큰 정수가 없습니다.
  • \(a\)는 \(b\)에 대한 곱셈 역원을 가집니다(그리고 \(b\)는 \(a\)에 대한 역원을 가집니다): 합동식 \(a \cdot x \equiv 1 \pmod b\)는 풀 수 있으며, 잉여 \(0, 1, \ldots, b-1\) 중에서 유일한 해가 있습니다. 이는 베주 항등식에서 따르며, 이는 다음을 만족하는 정수 \(x, y\)를 보장합니다: $$a x + b y = 1$$ 그 방정식을 \(\bmod b\)로 축약하면 \(a x \equiv 1\)이 남습니다. \(a = 25\), \(b = 54\)의 경우: \(25 \cdot 13 - 54 \cdot 6 = 325 - 324 = 1\)이므로 25의 mod 54 역원은 13입니다.
  • 최소공배수는 순수 곱입니다: \(\operatorname{lcm}(a,b) = a \cdot b\). 25와 54의 경우 \(\operatorname{lcm} = 25 \times 54 = 1350\)입니다.
  • 중국인의 나머지 정리는 법 \(a\)와 \(b\)에 적용됩니다. 모든 시스템 \(x \equiv r \pmod a\), \(x \equiv s \pmod b\)는 해를 가지며, \(a \cdot b\) modulo에서 유일합니다 — 예를 들어 법 25와 54에 대해 mod 1350으로 유일합니다.
  • 길이 \(b\)의 사이클 주위에서 \(a\)만큼 진행하면 모든 위치를 방문합니다. 배수 \(0, a, 2a, 3a, \ldots\)를 \(\bmod b\)로 축약하면 반복되기 전에 모든 \(b\) 잉여를 통과합니다. \(a\)는 전체 사이클을 생성합니다. gcd가 \(d > 1\)이었다면 보행은 \(d\)로 나누어지는 \(b/d\) 위치만 접할 것입니다.
  • 동등하게, \(a\)와 \(b\)의 소인수분해는 소수를 공유하지 않으며, \(a\)는 오일러 파이 \(\varphi(b)\)로 계산됩니다.

gcd(a, b) = d > 1인 경우 — 수가 서로소가 아님

  • 분수 \(a/b\)는 약분됩니다. 양쪽을 \(d\)로 나누면 \((a/d)\,/\,(b/d)\)를 얻고, 그 쌍은 서로소이므로 약분된 분수는 기약분수입니다. \(a = 84\), \(b = 126\), \(d = 42\)의 경우: \(84/126 = 2/3\)이고 \(\gcd(2,3) = 1\)입니다.
  • \(a\)의 \(\bmod b\) 역원이 존재하지 않습니다. 합동식 \(a \cdot x \equiv 1 \pmod b\)는 해가 없습니다. \(a x - 1\)의 모든 값이 \(b\)의 배수이면 \(d \mid 1\)을 강제하기 때문입니다. 더 일반적으로 \(a x \equiv c \pmod b\)는 \(d \mid c\)일 때만 풀 수 있으며, 그 경우 \(\bmod b\)에서 정확히 \(d\)개의 해를 가집니다.
  • 최소공배수는 곱보다 작습니다: \(\operatorname{lcm}(a,b) = \dfrac{a \cdot b}{d}\). 84와 126의 경우: \(\operatorname{lcm} = \dfrac{84 \times 126}{42} = \dfrac{10584}{42} = 252\)입니다.
  • 베주 항등식은 여전히 \(a x + b y = d\) 형태로 성립합니다 — \(a x + b y\)가 취할 수 있는 가장 작은 양수는 \(d\)이며, 1이 아닙니다. 중국인의 나머지 정리는 기본 형태로는 법 \(a\)와 \(b\)에 적용되지 않습니다.

경계 사례

  • \(\gcd(1, n) = 1\) (모든 정수 \(n\)에 대해)이므로 1은 0과 자신을 포함한 모든 것과 서로소입니다: \(\gcd(1,1) = 1\).
  • \(\gcd(0, n) = |n|\) (모든 정수가 0을 나누기 때문). 따라서 0은 1과 −1하고만 서로소입니다.
  • \(\gcd(0, 0)\)은 최대공약수가 없습니다 — 모든 정수가 0을 나누므로 공약수 집합은 무한합니다. 관례적으로 0으로 정의되며, 쌍 \((0,0)\)은 서로소가 아닙니다.
  • 부호는 무관합니다: \(\gcd(a,b) = \gcd(|a|, |b|)\)이므로 \(\gcd(-25, 54) = 1\)은 \(\gcd(25, 54) = 1\)과 마찬가지입니다.
  • 수가 자신과 서로소인 것은 \(|a| = 1\)일 때만입니다. \(\gcd(a,a) = |a|\)이기 때문입니다.

계산 규칙과 경계 사례

아래 사례는 모두 이 계산기로 실제 계산한 것이며, 결과 열은 계산기가 실제로 돌려준 값입니다.

사례입력결과
1과 91, 9예
0과 50, 5아니요

2026-11-08 확인

자주 묻는 질문

서로소인 수는 반드시 소수여야 하나요? 아닙니다. 서로소란 1보다 큰 공통인수가 없다는 뜻일 뿐, 각 수 자체가 소수일 필요는 없습니다(예: 8과 9).

1은 모든 수와 서로소인가요? 네. 어떤 정수 n에 대해서도 \(\gcd(1,\ n) = 1\)이므로, 1은 모든 정수와 서로소입니다.

짝수 두 개가 서로소일 수 있나요? 아닙니다. 모든 짝수는 공통인수 2를 가지므로, 두 짝수의 최대공약수는 최소 2 이상입니다.

최종 업데이트:

수학 및 통계 인기 계산기

수학 및 통계 계산기 전체 보기