GCD Calculator — Greatest Common Divisor with Steps
Enter two positive integers to find their greatest common divisor (GCD) — the largest number that divides both exactly. The Euclidean algorithm steps are shown so you can see exactly how the answer is reached.
Largest integer that divides both numbers without a remainder
Divide 48 by 36
Divide 36 by 12
Remainder is 0 — GCD found
此計算機如何運作？
GCD(a, b) is found by the Euclidean algorithm: repeatedly replace (a, b) with (b, a mod b) until the remainder is 0; the last non-zero value is the GCD. For example, GCD(48, 36) = GCD(36, 12) = GCD(12, 0) = 12. LCM = (a × b) / GCD.
公式
How this is calculated
The greatest common divisor (GCD) of two integers is the largest integer that divides both without a remainder. It is also called the highest common factor (HCF) or greatest common factor (GCF). For example, GCD(48, 36) = 12, because 12 is the largest number that divides both 48 and 36 evenly.
This calculator uses the Euclidean algorithm, one of the oldest and fastest known algorithms. It works by repeatedly replacing the larger number with the remainder of dividing the two numbers: GCD(a, b) = GCD(b, a mod b), because any divisor of a and b is also a divisor of the remainder. When the remainder reaches 0, the other number is the GCD. The algorithm is guaranteed to terminate because remainders strictly decrease, and it runs in O(log min(a, b)) steps.
The calculator also shows the least common multiple (LCM) using the identity LCM(a, b) = (a × b) / GCD(a, b), which follows because the product of two integers equals the product of their GCD and LCM. Both results are exact integers — no rounding is involved.
常見問題
GCD (greatest common divisor) is the largest number that divides both integers evenly. LCM (least common multiple) is the smallest positive number that both integers divide into evenly. They are related by GCD × LCM = a × b.
GCD is used to simplify fractions (divide numerator and denominator by the GCD), find common denominators, solve Diophantine equations, and in cryptography (RSA key generation uses the extended Euclidean algorithm).
Yes. Greatest common divisor (GCD), highest common factor (HCF), and greatest common factor (GCF) all refer to the same value — the largest integer that divides a set of numbers without a remainder.
也稱為
TG we-Calculate Editorial Team. (2026). GCD Calculator — Greatest Common Divisor with Steps [Online calculator]. TG we-Calculate. https://we-calculate.com/zh-tw/calculator/gcd-calculator
TG we-Calculate Editorial Team. "GCD Calculator — Greatest Common Divisor with Steps." TG we-Calculate. 2026. https://we-calculate.com/zh-tw/calculator/gcd-calculator.
TG we-Calculate Editorial Team, "GCD Calculator — Greatest Common Divisor with Steps," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/zh-tw/calculator/gcd-calculator
@misc{wecalculate_gcd_calculator, title = {GCD Calculator — Greatest Common Divisor with Steps}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/zh-tw/calculator/gcd-calculator}}, year = {2026}, note = {TG we-Calculate} }
這個計算機對您有幫助嗎？