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

두 양의 정수의 최대공약수와 최소공배수를 계산하고, 유클리드 호제법 과정을 단계별로 확인합니다.

계산 방식

공식

\text{GCD}(a,b) = \text{GCD}(b,\; a \bmod b)

\text{LCM}(a,b) = \frac{a \times b}{\text{GCD}(a,b)}

변수, 기호, 단위

$a$: 첫 번째 양의 정수
$b$: 두 번째 양의 정수

계산 방식 설명

계산기는 먼저 유클리드 호제법으로 최대공약수를 구합니다. 나머지를 반복해서 계산하고, 나머지가 0이 되면 마지막 0이 아닌 값이 GCD입니다. 그런 다음 두 수의 곱과 GCD-LCM 항등식으로 LCM을 구합니다.

유클리드 점화식에 따라 $(a,b)$ 를 $(b,\; a \bmod b)$ 로 바꾸고 $b = 0$ 이 될 때까지 반복합니다. 남은 $a$ 가 GCD입니다. LCM은 $a \times b = \text{GCD}(a,b) \times \text{LCM}(a,b)$ 에서 구합니다.

자주 묻는 질문

최대공약수란 무엇인가요?

최대공약수는 두 정수를 모두 나머지 없이 나누는 가장 큰 양의 정수입니다. GCD라고도 합니다.

최소공배수란 무엇인가요?

최소공배수는 두 정수의 공통 배수 중 가장 작은 양의 정수입니다. LCM이라고도 합니다.

유클리드 호제법은 어떻게 작동하나요?

큰 수를 작은 수로 나눈 나머지를 다음 단계에 사용하며, 나머지가 0이 될 때까지 반복합니다. 마지막 0이 아닌 나머지가 최대공약수입니다.

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

양의 정수 a와 b에 대해 a x b = GCD(a,b) x LCM(a,b)가 성립합니다.

서로소란 무엇인가요?

두 수의 최대공약수가 1이면 서로소입니다. 즉 1 이외의 공통인수가 없습니다.

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

계산 방식

자주 묻는 질문

관련 계산기

모든 계산기

계산을 시작할까요?