약수 개수와 유클리드 호제법 GCD·LCM 공식
1. 약수 개수와 소인수분해의 수학 공식
특정 거대한 수의 모든 약수를 하나씩 일일이 나누어 확인하려면 연산 자원과 시간이 많이 소모됩니다. 정수론은 소인수분해(Prime Factorization) 공식을 통해 이를 신속히 우회합니다.
약수 개수 산출 공식: 어떤 자연수 N이 다음과 같이 소인수분해될 때,
N = a^p × b^q × c^r × …(여기서 a, b, c는 서로 다른 소수이고, p, q, r은 자연수 지수입니다.)
약수의 총 개수 = (p + 1) × (q + 1) × (r + 1) × …계산 실무 예시 (72의 약수 개수 구하기):
- 소인수분해: 72 = 8 × 9 = 2^3 × 3^2
- 지수 대입: p = 3, q = 2
- 약수 개수: (3 + 1) × (2 + 1) = 4 × 3 = 12개 결과 해석: 72의 약수를 손가락으로 다 세지 않고도 공식에 의해 총 12개(
1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72)임을 확증할 수 있습니다.
2. 유클리드 호제법과 최대공약수·최소공배수 연산 공식
두 자연수의 최대공약수를 효율적으로 구하는 대표적인 프로그래밍 알고리즘이 기원전 300년경 확립된 유클리드 호제법(Euclidean Algorithm)입니다.
유클리드 호제법 재귀 공식
두 수 a와 b (a > b)에 대하여, a를 b로 나눈 나머지를 r이라고 할 때 다음의 항등식이 성립합니다.
GCD(a, b) = GCD(b, r)
이 나머지가 0이 되는 시점의 나누는 수가 두 수의 최종 최대공약수입니다.
- 예시 (GCD(120, 36) 구하기):
- 120 ÷ 36 = 3, 나머지 12 → GCD(120, 36) = GCD(36, 12)
- 36 ÷ 12 = 3, 나머지 0 → 나머지가 0이 되었으므로 마지막 제수인 12가 최종 최대공약수입니다.
최소공배수 연산 공식
최대공약수(GCD)를 알면 최소공배수(LCM)는 아래의 비례 항등 공식으로 즉시 치환됩니다.
LCM(a, b) = (a × b) ÷ GCD(a, b)
약수·GCD·LCM 계산기 활용 가이드
복잡한 여러 자릿수 소인수분해를 하거나 유클리드 나눗셈 루프를 손으로 반복하기 번거롭다면 전용 정수론 계산 도구를 활용해 보세요.
무료 · 가입 불필요 · 두 숫자 입력 즉시 약수 목록 및 GCD, LCM 자동 연산
도구 사용 방법은 매우 명확하게 구축되어 있습니다.
- 숫자 입력: 계산을 원하는 두 자연수를 각각 숫자 A, 숫자 B 입력창에 기입합니다(1 ~ 1,000만 범위).
- 입력과 동시에 상세 분석 영역에 A와 B 각각의 약수 목록, 공약수 목록, 소인수분해 결과가 표출됩니다.
- 동시에 상단 결과 카드에 최대공약수(GCD)와 최소공배수(LCM) 수치가 굵은 강조 카드로 도출되고, 소인수를 이용한 계산 과정도 단계별로 함께 확인할 수 있습니다.
정리
약수와 최대공약수, 최소공배수는 기초 산수처럼 보이지만 분수의 사칙연산, 컴퓨터 진법 비트 연산, 정보 보안 키 암호화 등 디지털 세계의 뼈대를 이루는 필수 셈법입니다. 여러 자릿수의 수동 계산은 실수가 섞이기 쉬운 만큼, 계산기로 유클리드 호제법 결과를 대조해 두면 수치 오차를 빠르게 확인할 수 있습니다.
무료 · 가입 불필요 · 두 숫자 입력 즉시 약수 목록 및 GCD, LCM 자동 연산
자주 묻는 질문
최대공약수가 1인 두 자연수를 무엇이라고 부르고 왜 중요한가요?
최대공약수가 1 이외에 존재하지 않는 두 수의 관계를 수학적으로 서로소(Relatively Prime / Coprime)라고 부릅니다.
- 서로소는 분수를 더 이상 쪼갤 수 없는 기약분수로 약분할 때 핵심적인 기준점이 됩니다.
- 특히 컴퓨터 암호학(RSA)에서는 큰 소수 두 개를 골라 그 곱(n)을 구하고, n에서 파생된 값과 서로소 관계에 있는 정수를 공개키 생성에 사용합니다. 이처럼 서로소 판정은 암호 키를 만드는 과정의 기본 전제가 됩니다.
세 개 이상의 숫자(예: A, B, C)의 최대공약수와 최소공배수는 어떻게 연산하나요?
이 계산기는 두 수를 한 번에 입력받으므로, 세 수 이상은 두 수씩 순차적으로 넣어 결과를 이어 붙이는 방식으로 확인합니다.
최대공약수 공식 확장:
GCD(A, B, C) = GCD(GCD(A, B), C)(즉, A와 B를 먼저 계산기에 넣어 최대공약수를 구한 뒤, 그 결과값과 C를 다시 계산기에 넣으면 세 수 전체의 최대공약수를 구할 수 있습니다.)
최소공배수 공식 확장:
LCM(A, B, C) = LCM(LCM(A, B), C)같은 방식으로 A·B의 최소공배수를 먼저 구하고, 그 값을 C와 함께 다시 계산기에 넣으면 숫자가 몇 개든 순차적으로 확장할 수 있습니다.
이 글은 유클리드 호제법 등 정수론 표준 수학 이론을 참조하여 정보 제공용으로 작성되었습니다.