최대공약수・최소공배수 계산기

유클리드 알고리즘으로 최대공약수(GCD)와 최소공배수(LCM)를 단계별로 계산합니다.

최대공약수・최소공배수 계산기이란?

최대공약수(GCD)와 최소공배수(LCM)는 초등 정수론에서 가장 중요한 두 개념으로, 중학교에서의 분수 약분부터 인터넷을 보호하는 암호화 알고리즘까지 다양한 응용 분야를 가지고 있습니다.

기원전 300년경 유클리드가 설명한 유클리드 알고리즘은 수학에서 가장 오래되고 효율적인 알고리즘 중 하나입니다. O(log(min(a,b))) 단계로 GCD를 계산하며, 매우 큰 숫자에 대해서도 빠르게 종료됩니다. 이 알고리즘은 나머지가 0이 될 때까지 GCD(a, b) = GCD(b, a mod b) 항등식을 반복적으로 적용합니다.

이 계산기는 두 숫자에 대한 완전한 유클리드 알고리즘을 단계별로 보여주며, 일반화 GCD(a, b, c) = GCD(GCD(a, b), c)를 사용하여 여러 숫자 목록에 대한 GCD와 LCM도 계산합니다.

공식

유클리드 알고리즘:

GCD(a, b) = GCD(b, a mod b) b = 0까지

GCD로부터 LCM 구하기:

LCM(a, b) = |a × b| / GCD(a, b)

여러 숫자의 경우:

GCD(a, b, c) = GCD(GCD(a, b), c)

LCM(a, b, c) = LCM(LCM(a, b), c)

계산 방법

두 개의 양의 정수 a와 b를 입력하세요.
정수 나눗셈 적용: a = q×b + r.
a를 b로, b를 r로 바꿉니다. r = 0이 될 때까지 반복합니다.
마지막 0이 아닌 나머지가 GCD입니다.
기본 항등식을 사용하여 LCM = |a × b| / GCD를 계산합니다.
세 개 이상의 숫자에는 "여러 숫자" 모드를 사용하세요.

예시

GCD(48, 18) 구하기: 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. GCD = 6. LCM = |48×18|/6 = 864/6 = 144. 확인: 144/48 = 3 ✓, 144/18 = 8 ✓.

주요 용어 설명

GCD: 두 숫자를 나머지 없이 나누는 가장 큰 정수
LCM: 두 숫자 모두로 나누어 떨어지는 가장 작은 양의 정수
서로소: GCD = 1인 두 숫자, 공통 소인수 없음
유클리드 알고리즘: 반복된 나눗셈으로 GCD를 계산하는 고대 알고리즘
모듈로 연산: a mod b는 a를 b로 나눈 나머지
나누어떨어짐: b/a에 나머지가 없으면 a가 b를 나눔

일반적인 사용 사례

분수 약분: GCD(a, b)로 둘 다 나누어 a/b를 약분
분모가 다른 분수 덧셈: 분모의 LCM 구하기
일정 관리: 두 반복 이벤트가 다음에 동시에 발생하는 시점 찾기
RSA 키 생성: 지수 e가 φ(n)과 서로소인지 확인
기계 공학의 기어비 문제
타일 패턴 디자인: 가장 작은 반복 단위 찾기

자주 묻는 질문

최대공약수(GCD)란 무엇이며 어떻게 계산하나요?

최대공약수(GCD)는 a와 b를 나머지 없이 나누는 가장 큰 양의 정수입니다. 유클리드 알고리즘은 b = 0이 될 때까지 (a, b)를 (b, a mod b)로 반복하여 교체하여 효율적으로 계산합니다. 마지막 0이 아닌 값이 GCD입니다.

최소공배수(LCM)란 무엇이며 어디에 사용되나요?

최소공배수(LCM)는 a와 b 모두로 나누어 떨어지는 가장 작은 양의 정수입니다. 분모가 다른 분수의 덧셈, 일정 문제, 음악 이론에 사용됩니다.

GCD와 LCM의 관계는 무엇인가요?

GCD(a, b) × LCM(a, b) = |a × b|입니다. GCD를 알면 LCM은 간단히 |a × b| / GCD(a, b)입니다. 이는 배수를 나열하는 것보다 효율적입니다.

서로소(Co-prime)란 무엇을 의미하나요?

두 숫자가 서로소(상대적으로 소수)라는 것은 GCD가 1이라는 뜻입니다. 즉, 공통 소인수가 없습니다. 서로소 관계는 모듈러 산술, 암호학, 중국인의 나머지 정리에서 기본이 됩니다.

최대공약수・최소공배수 계산기