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

두 개 이상의 양의 정수에 대해 최소공배수(LCM)와 최대공약수(GCD)를 즉시 계산하세요. 소인수분해, 유클리드 호제법 풀이 과정, 공약수·공배수 목록을 한눈에 확인할 수 있습니다.

첫 번째 수

두 번째 수

최소공배수(LCM)와 최대공약수(GCD)란?

최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 정수를 동시에 나누어떨어지게 하는 가장 큰 양의 정수입니다. 예를 들어 12와 18의 최대공약수는 6입니다. 최소공배수(LCM, Least Common Multiple)는 두 개 이상의 정수의 공통 배수 중 가장 작은 양의 정수입니다. 12와 18의 최소공배수는 36입니다. 최대공약수와 최소공배수는 수학의 정수론에서 핵심적인 개념으로, 한국 수학 교육과정에서는 초등학교 5학년 '약수와 배수' 단원에서 처음 배우고, 중학교 1학년 '소인수분해' 단원에서 심화 학습합니다. 분수의 통분과 약분, 비율 계산, 일정 동기화 등 일상생활과 학문 전반에서 폭넓게 활용됩니다.

최소공배수와 최대공약수 계산 방법

최대공약수와 최소공배수를 구하는 대표적인 방법으로는 유클리드 호제법과 소인수분해법이 있습니다.

최대공약수(GCD) 구하기

유클리드 호제법: GCD(a, b) = GCD(b, a mod b), 나머지가 0이 될 때까지 반복. 예) GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6

소인수분해법: 각 수를 소인수분해한 뒤, 공통 소인수를 가장 작은 지수로 곱합니다. 예) 48 = 2⁴ × 3, 18 = 2 × 3², GCD = 2¹ × 3¹ = 6

최소공배수(LCM) 구하기

공식법: LCM(a, b) = |a × b| / GCD(a, b). 예) LCM(12, 18) = |12 × 18| / 6 = 216 / 6 = 36

소인수분해법: 각 수를 소인수분해한 뒤, 모든 소인수를 가장 큰 지수로 곱합니다. 예) 12 = 2² × 3, 18 = 2 × 3², LCM = 2² × 3² = 36

최대공약수와 최소공배수의 관계: LCM(a, b) × GCD(a, b) = |a × b|. 이 공식은 두 수에 대해 항상 성립합니다.

계산 방법 비교

최대공약수와 최소공배수를 구하는 여러 방법의 특징을 비교합니다.

방법	설명	적합한 경우
유클리드 호제법	두 수의 나눗셈에서 나머지를 반복적으로 구하여 최대공약수를 찾는 방법입니다. 나머지가 0이 되면 그때의 나누는 수가 최대공약수입니다.	두 수의 최대공약수를 빠르게 구할 때, 큰 수에 적합
소인수분해법	각 수를 소수의 곱으로 분해한 뒤, 공통 소인수의 곱(GCD) 또는 모든 소인수의 최대 지수 곱(LCM)으로 구하는 방법입니다.	풀이 과정을 시각적으로 이해할 때, 여러 수의 GCD/LCM 동시 계산
연속 나눗셈법 (사다리 나눗셈)	공통 소인수로 동시에 나누어가며 최대공약수와 최소공배수를 구하는 방법입니다. 한국 초등수학 교과서에서 주로 가르치는 방법입니다.	초등학생 학습용, 여러 수를 한꺼번에 계산할 때
나열법	각 수의 약수 또는 배수를 직접 나열하여 공통된 약수(GCD) 또는 공통된 배수(LCM) 중 적절한 값을 찾는 방법입니다.	작은 수의 계산, 개념 이해 단계의 기초 학습

최소공배수·최대공약수 계산의 한계

최소공배수와 최대공약수 계산기는 매우 유용하지만, 다음과 같은 제한 사항을 알아두시기 바랍니다:

큰 수의 처리

입력값이 매우 클 경우(수십 자릿수 이상) 소인수분해에 시간이 오래 걸리거나 정밀도 문제가 발생할 수 있습니다. JavaScript의 정수 안전 범위(2⁵³ - 1)를 초과하는 수는 정확한 결과를 보장할 수 없습니다.

음수 처리

최대공약수와 최소공배수는 양의 정수에 대해 정의됩니다. 음수가 입력되면 절댓값을 사용하여 계산하지만, 수학적으로 엄밀한 정의와 다를 수 있습니다.

0의 처리

GCD(a, 0) = a, LCM(a, 0) = 0이라는 규약을 따르지만, 0을 포함한 최소공배수는 수학적으로 의미가 제한적입니다.

소수(실수) 입력 불가

이 계산기는 양의 정수만 지원합니다. 소수나 분수를 입력하면 오류가 발생합니다. 분수의 최소공배수가 필요한 경우 분모끼리의 최소공배수를 활용하세요.

계산 복잡도

유클리드 호제법의 시간 복잡도는 O(log(min(a,b)))로 매우 효율적이지만, 소인수분해는 큰 수에 대해 O(√n)의 시간이 필요합니다. 수백 자릿수의 소인수분해는 현재 기술로도 실질적으로 불가능합니다.

고급 알고리즘

기본 유클리드 호제법 외에도 다양한 고급 알고리즘이 존재합니다:

•확장 유클리드 호제법: GCD(a, b) = ax + by를 만족하는 x, y를 함께 구합니다. 모듈러 역원 계산, RSA 암호화 키 생성에 핵심적으로 사용됩니다.
•이진 GCD 알고리즘 (슈타인 알고리즘): 나눗셈 대신 비트 연산(시프트)만 사용하여 GCD를 구합니다. 나눗셈이 느린 하드웨어에서 효율적입니다.
•폴라드 로 알고리즘: 큰 합성수의 소인수를 확률적으로 찾는 알고리즘입니다. 소인수분해법으로 GCD를 구할 때 보조적으로 활용할 수 있습니다.

분야별 최소공배수·최대공약수 활용

최소공배수와 최대공약수는 수학뿐 아니라 다양한 분야에서 활용됩니다.

수학 교육

한국 수학 교육과정에서 약수와 배수는 초등학교 5학년에서 처음 등장하며, 중학교 1학년 '소인수분해' 단원에서 유클리드 호제법과 함께 심화 학습합니다. 분수의 통분(공통 분모 = 분모의 LCM)과 약분(분자·분모를 GCD로 나눗셈)은 중학교 수학 전반에서 필수적인 기본 연산입니다.

수능 수학에서도 정수의 성질, 약수와 배수 관련 문제가 출제됩니다. 특히 수열의 일반항 구하기, 정수 조건 판별, 경우의 수 계산 등에서 GCD와 LCM 개념이 간접적으로 활용됩니다.

프로그래밍과 알고리즘

유클리드 호제법은 프로그래밍의 기본 알고리즘 중 하나입니다. 재귀 함수와 반복문의 대표적 예제로 교육에 활용되며, 코딩 테스트(삼성 SW 역량테스트, 카카오 코딩테스트 등)에서 빈출됩니다.

해시 테이블의 크기 결정, 화면 해상도 비율 계산(예: 1920×1080의 GCD = 120, 비율 16:9), 스케줄링 알고리즘, 분산 시스템의 데이터 파티셔닝에도 GCD와 LCM이 사용됩니다.

암호학

RSA 암호화 알고리즘에서 확장 유클리드 호제법은 개인 키를 생성하는 데 핵심적으로 사용됩니다. 두 큰 소수 p, q의 곱 n = p × q에서 오일러 토션트 함수 값과 공개 키 e의 모듈러 역원을 구할 때 확장 유클리드 호제법이 필요합니다.

서로소(GCD = 1) 판별은 암호학에서 키의 유효성을 검증하는 기본 조건입니다. 또한 디피-헬만 키 교환, 타원 곡선 암호학 등 현대 암호 체계의 수학적 기반에도 정수론의 GCD 개념이 깊이 관여합니다.

일상생활

일정 동기화 문제에서 최소공배수가 활용됩니다. 예를 들어 A 버스가 15분 간격, B 버스가 20분 간격으로 운행할 때, 두 버스가 동시에 출발하는 주기는 LCM(15, 20) = 60분입니다. 공장의 생산 라인 동기화, 신호등 주기 설정에도 같은 원리가 적용됩니다.

최대공약수는 균등 분배 문제에서 활용됩니다. 사과 24개와 귤 36개를 최대한 많은 사람에게 남김없이 골고루 나누려면 GCD(24, 36) = 12명에게 나눌 수 있습니다. 타일 깔기, 포장 용지 자르기 등 최대 크기의 정사각형을 구하는 문제에도 GCD가 쓰입니다.

최소공배수와 최대공약수를 배우는 이유

최소공배수와 최대공약수는 수학의 기초 개념 중 하나로, 분수의 통분과 약분에 직접 활용됩니다. 통분할 때 분모의 최소공배수를 공통 분모로 사용하고, 약분할 때 분자와 분모의 최대공약수로 나눕니다. 이러한 연산은 수능, 모의고사, 내신 시험에서 꾸준히 출제되는 핵심 영역입니다.

실생활에서도 최소공배수와 최대공약수는 다양하게 활용됩니다. 버스 배차 간격이 각각 12분, 18분인 두 노선이 동시에 출발한 후 다시 동시에 도착하는 시간은 최소공배수인 36분 후입니다. 바둑판 모양으로 타일을 깔 때 가장 큰 정사각형 타일의 한 변 길이는 가로와 세로의 최대공약수입니다.

프로그래밍과 컴퓨터 과학에서도 최대공약수 알고리즘은 핵심적입니다. 유클리드 호제법은 가장 오래된 알고리즘 중 하나이며, RSA 암호화, 해시 함수, 데이터 분할 등 다양한 분야에서 활용됩니다. 코딩 테스트와 알고리즘 대회에서도 자주 출제되는 기본 알고리즘입니다.

이 계산기는 누가 사용하면 좋을까?

초등학교 5~6학년과 중학생이 약수와 배수, 소인수분해를 학습하거나 수학 숙제를 풀 때 유용합니다. 풀이 과정을 단계별로 확인할 수 있어 개념 이해에 도움이 됩니다.

수능, 모의고사, 내신 시험을 준비하는 고등학생과 수험생이 빠르게 답을 검증하거나 풀이 방법을 확인할 때 활용할 수 있습니다.

프로그래머, 공학자, 데이터 분석가 등 실무에서 정수론적 계산이 필요한 전문가도 빠른 계산과 검증 도구로 활용할 수 있습니다.

최소공배수·최대공약수 계산 방법 비교

최소공배수와 최대공약수를 구하는 다양한 도구와 방법을 비교합니다.

방법	접근 방식	장점	단점
손 계산 (종이+펜)	소인수분해, 유클리드 호제법, 나열법 등을 직접 수행	풀이 과정을 완전히 이해 가능, 시험에서 직접 활용, 추가 도구 불필요	큰 수일수록 시간이 오래 걸림, 계산 실수 가능성, 소인수분해가 어려운 수 존재
공학용 계산기	내장된 GCD/LCM 함수 사용 (대부분의 공학용 계산기 지원)	빠르고 정확한 결과, 시험에서 사용 가능(허용 시), 휴대 가능	풀이 과정 미표시, 두 수만 계산 가능한 경우 많음, 소인수분해 미지원
프로그래밍 언어	Python의 math.gcd(), Java의 BigInteger.gcd() 등 내장 함수 사용	매우 큰 수도 정확하게 처리, 자동화·반복 계산에 적합, 확장 알고리즘 구현 가능	프로그래밍 지식 필요, 환경 설정 필요, 비전문가 접근성 낮음
Wolfram Alpha	자연어로 'GCD of 48 and 18' 입력	풀이 과정 상세 제공, 수학적 표기법 지원, 관련 수학 정보 풍부	인터넷 연결 필요, 무료 사용 제한, 한국어 지원 부족
온라인 GCD/LCM 계산기	웹 브라우저에서 숫자를 입력하고 결과 확인	즉시 사용 가능, 소인수분해·풀이 과정 제공, 여러 수 동시 계산 지원	인터넷 연결 필요, 시험 중 사용 불가, 사이트마다 기능 차이

손 계산 (종이+펜)

접근 방식: 소인수분해, 유클리드 호제법, 나열법 등을 직접 수행
장점: 풀이 과정을 완전히 이해 가능, 시험에서 직접 활용, 추가 도구 불필요
단점: 큰 수일수록 시간이 오래 걸림, 계산 실수 가능성, 소인수분해가 어려운 수 존재

공학용 계산기

접근 방식: 내장된 GCD/LCM 함수 사용 (대부분의 공학용 계산기 지원)
장점: 빠르고 정확한 결과, 시험에서 사용 가능(허용 시), 휴대 가능
단점: 풀이 과정 미표시, 두 수만 계산 가능한 경우 많음, 소인수분해 미지원

프로그래밍 언어

접근 방식: Python의 math.gcd(), Java의 BigInteger.gcd() 등 내장 함수 사용
장점: 매우 큰 수도 정확하게 처리, 자동화·반복 계산에 적합, 확장 알고리즘 구현 가능
단점: 프로그래밍 지식 필요, 환경 설정 필요, 비전문가 접근성 낮음

Wolfram Alpha

접근 방식: 자연어로 'GCD of 48 and 18' 입력
장점: 풀이 과정 상세 제공, 수학적 표기법 지원, 관련 수학 정보 풍부
단점: 인터넷 연결 필요, 무료 사용 제한, 한국어 지원 부족

온라인 GCD/LCM 계산기

접근 방식: 웹 브라우저에서 숫자를 입력하고 결과 확인
장점: 즉시 사용 가능, 소인수분해·풀이 과정 제공, 여러 수 동시 계산 지원
단점: 인터넷 연결 필요, 시험 중 사용 불가, 사이트마다 기능 차이

최소공배수·최대공약수 학습 가이드

학습 단계별로 최소공배수와 최대공약수 개념을 효과적으로 익히는 방법을 안내합니다.

기초 단계 (초등 5~6학년)

1약수와 배수의 개념을 정확히 이해합니다. 12의 약수는 1, 2, 3, 4, 6, 12이고, 3의 배수는 3, 6, 9, 12, 15, ...입니다.
2두 수의 공약수와 공배수를 나열법으로 직접 구해봅니다. 12와 18의 공약수는 1, 2, 3, 6이고 최대공약수는 6입니다.
3연속 나눗셈법(사다리 나눗셈)으로 GCD와 LCM을 구하는 연습을 합니다. 교과서에서 가장 먼저 배우는 방법입니다.
4실생활 문제를 통해 개념을 적용합니다. '가로 12cm, 세로 18cm 직사각형에 가장 큰 정사각형 타일을 빈틈없이 깔려면 타일 한 변은 몇 cm?'

중급 단계 (중학교~고등학교)

1소인수분해법으로 GCD와 LCM을 구합니다. 각 수를 소인수의 곱으로 표현하고, GCD는 공통 소인수의 최소 지수, LCM은 모든 소인수의 최대 지수를 사용합니다.
2유클리드 호제법의 원리를 이해하고 적용합니다. GCD(a, b) = GCD(b, a mod b)를 나머지가 0이 될 때까지 반복합니다.
3GCD와 LCM의 관계식 LCM(a, b) × GCD(a, b) = a × b를 증명 없이 활용하여 빠르게 계산합니다.
4세 수 이상의 GCD와 LCM을 순차적으로 구합니다. GCD(a, b, c) = GCD(GCD(a, b), c), LCM(a, b, c) = LCM(LCM(a, b), c).

심화 단계 (대학·전문가)

1확장 유클리드 호제법을 이해하고 ax + by = GCD(a, b)를 만족하는 x, y를 구합니다. 모듈러 역원 계산에 필수적입니다.
2다항식의 GCD를 구하는 방법을 학습합니다. 다항식에도 유클리드 호제법을 적용할 수 있으며, 이는 대수학과 기호 연산의 핵심입니다.
3정수론에서 GCD의 일반화(이상, 유일 인수분해 정역 등)를 학습합니다. 추상대수학에서 GCD 개념이 어떻게 확장되는지 이해합니다.
4암호학에서의 활용을 실습합니다. RSA 키 생성 과정에서 확장 유클리드 호제법으로 개인 키 d를 구하는 과정을 직접 구현해 봅니다.

학습 팁

최소공배수와 최대공약수를 잘 이해하려면 다양한 수에 대해 직접 손으로 계산하는 연습이 가장 효과적입니다. 소인수분해표를 만들어 패턴을 파악하고, 유클리드 호제법의 각 단계를 표로 정리하면 이해가 깊어집니다. 온라인 계산기는 답을 검증하는 보조 도구로 활용하고, 반드시 풀이 과정을 스스로 재현할 수 있어야 합니다.

최소공배수·최대공약수 관련 추가 정보

최대공약수와 최소공배수 개념은 초등학교 수학에서 시작하지만, 고등 수학과 대학 수학에서도 계속 확장됩니다. 정수론, 추상대수학, 환론(Ring Theory)에서 최대공약수는 이상(ideal)의 개념으로 일반화되며, 다항식의 GCD는 대수학과 기호 연산의 핵심입니다.

주의 사항

최대공약수와 최소공배수는 양의 정수에 대해 정의됩니다. 0이 포함되면 GCD(a, 0) = a이고 LCM(a, 0) = 0이라는 규약을 따릅니다.
매우 큰 수의 경우 계산에 시간이 걸릴 수 있습니다. 일반적인 수학 문제에서 다루는 범위 내에서 사용하는 것을 권장합니다.
세 개 이상의 수에 대한 최대공약수와 최소공배수는 두 수씩 순차적으로 계산합니다. 예를 들어 GCD(a, b, c) = GCD(GCD(a, b), c)입니다.

이 계산기는 교육 목적으로 제공되며, 학습 보조 도구로 활용하시기 바랍니다. 시험에서는 직접 풀이 과정을 작성해야 하므로, 풀이 과정을 이해하는 데 중점을 두세요.

최소공배수·최대공약수 자주 묻는 질문

최대공약수(GCD)는 두 수 이상을 동시에 나누어떨어지게 하는 가장 큰 양의 정수이고, 최소공배수(LCM)는 두 수 이상의 공통 배수 중 가장 작은 양의 정수입니다. 예를 들어 12와 18의 경우, 공약수는 1, 2, 3, 6이므로 GCD는 6이고, 공배수는 36, 72, 108, ...이므로 LCM은 36입니다. GCD는 약분에, LCM은 통분에 주로 사용됩니다. 두 수의 관계식으로 GCD(a, b) × LCM(a, b) = a × b가 성립합니다.

소인수분해법으로 LCM을 구하려면 다음 단계를 따릅니다. 먼저 각 수를 소인수분해합니다. 예) 24 = 2³ × 3, 36 = 2² × 3². 다음으로 등장하는 모든 소인수를 찾고(2, 3), 각 소인수에 대해 가장 큰 지수를 선택합니다. 2의 최대 지수는 3, 3의 최대 지수는 2입니다. 마지막으로 이들을 곱합니다: LCM = 2³ × 3² = 8 × 9 = 72. 이 방법은 세 수 이상에도 동일하게 적용할 수 있어 범용적입니다.

유클리드 호제법은 기원전 300년경 유클리드가 '원론'에서 기술한 최대공약수 계산 알고리즘입니다. 원리는 간단합니다: GCD(a, b) = GCD(b, a mod b)를 나머지가 0이 될 때까지 반복합니다. 예를 들어 GCD(252, 105)를 구하면: 252 = 105 × 2 + 42 → GCD(105, 42), 105 = 42 × 2 + 21 → GCD(42, 21), 42 = 21 × 2 + 0 → GCD = 21. 이 알고리즘의 시간 복잡도는 O(log(min(a,b)))로 매우 효율적이며, 현존하는 가장 오래된 알고리즘 중 하나입니다.

두 양의 정수 a, b에 대해 GCD(a, b) × LCM(a, b) = a × b가 항상 성립합니다. 이 공식을 활용하면 GCD를 알 때 LCM을 빠르게 구할 수 있습니다: LCM(a, b) = (a × b) / GCD(a, b). 예를 들어 GCD(12, 18) = 6이면, LCM(12, 18) = (12 × 18) / 6 = 36입니다. 주의할 점은 이 공식은 두 수에 대해서만 성립하며, 세 수 이상에서는 직접 적용할 수 없습니다. 세 수의 LCM은 LCM(a, b, c) = LCM(LCM(a, b), c)로 순차 계산합니다.

세 수 이상의 GCD와 LCM은 두 수씩 순차적으로 계산합니다. GCD(a, b, c) = GCD(GCD(a, b), c)이고, LCM(a, b, c) = LCM(LCM(a, b), c)입니다. 예를 들어 GCD(12, 18, 24)를 구하면: GCD(12, 18) = 6, GCD(6, 24) = 6. LCM(12, 18, 24)를 구하면: LCM(12, 18) = 36, LCM(36, 24) = 72. 소인수분해법도 동일하게 적용됩니다. 12 = 2² × 3, 18 = 2 × 3², 24 = 2³ × 3에서 GCD = 2¹ × 3¹ = 6, LCM = 2³ × 3² = 72입니다.

분모가 다른 분수를 더하거나 뺄 때 공통 분모가 필요합니다. 가장 효율적인 공통 분모는 분모들의 최소공배수입니다. 예를 들어 5/12 + 7/18을 계산할 때, LCM(12, 18) = 36이 공통 분모가 됩니다. 5/12 = 15/36, 7/18 = 14/36이므로, 15/36 + 14/36 = 29/36입니다. 최소공배수를 공통 분모로 사용하면 불필요하게 큰 수를 다루지 않아도 되므로 계산이 간결해집니다.

분수를 약분하려면 분자와 분모의 최대공약수로 각각 나누면 됩니다. 예를 들어 48/60을 약분하면, GCD(48, 60) = 12이므로 48/60 = (48÷12)/(60÷12) = 4/5입니다. 약분 결과 분자와 분모가 서로소(GCD = 1)이면 더 이상 약분할 수 없는 기약분수가 됩니다. 여러 단계로 나누어 약분하는 것보다 최대공약수로 한 번에 약분하는 것이 효율적이고 실수를 줄일 수 있습니다.

최소공배수는 주기적 사건의 동시 발생 시점을 구하는 데 사용됩니다. 예를 들어 신호등 A가 30초, 신호등 B가 45초 주기로 바뀌면 LCM(30, 45) = 90초마다 동시에 바뀝니다. 최대공약수는 균등 분배 문제에 활용됩니다. 사과 48개와 배 72개를 최대한 많은 바구니에 똑같이 나눠 담으려면 GCD(48, 72) = 24개의 바구니가 필요하며, 각 바구니에 사과 2개, 배 3개가 들어갑니다. 그 외에도 톱니바퀴 맞물림, 음악의 박자 맞추기, 건축 자재 절단 등에 활용됩니다.

GCD(Greatest Common Divisor), GCF(Greatest Common Factor), HCF(Highest Common Factor)는 모두 같은 개념의 다른 이름입니다. 한국어로는 '최대공약수'로 통일되어 있어 혼동이 적지만, 영어 교재에서는 지역과 교과서에 따라 다른 용어를 사용합니다. 한국 수학 교육과정에서는 '최대공약수'라는 단일 용어를 사용하며, 영어 표기로는 GCD가 가장 일반적입니다. 대학 수학과 프로그래밍에서는 주로 GCD를 표준으로 사용합니다.

RSA 암호화 알고리즘에서 최대공약수는 핵심적인 역할을 합니다. RSA 키 생성 시, 공개 키 e와 오일러 토션트 함수 값 phi(n)이 서로소(GCD = 1)인지 확인해야 합니다. 개인 키 d는 확장 유클리드 호제법으로 e × d ≡ 1 (mod phi(n))을 만족하는 d를 구하여 생성합니다. 또한 디피-헬만 키 교환 프로토콜에서도 GCD 기반의 수학적 성질이 보안의 기반이 됩니다. 현대 인터넷 보안(HTTPS, 전자서명, 인증서)의 수학적 토대에 GCD 개념이 깊이 관여합니다.