TToolbox
gcd

GCD and LCM Calculator

Greatest common divisor and least common multiple

About this tool

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are fundamental mathematical pillars across elementary number theory, modern asymmetric cryptography (RSA keypair synthesis), aspect ratio simplification, and fractional arithmetic. Factoring large integers manually is painfully slow. This tool implements the classical Euclidean algorithm, supporting pairwise and multi-number array inputs to compute GCD, LCM, and prime factorizations in milliseconds.

How to Use This Tool (Step-by-Step)

1

Enter Two or More Integers

Type your target integers separated by commas, spaces, or line breaks (e.g., `24, 36, 60`) into the input field.

2

Instant Algorithmic Derivation

The engine executes the Euclidean algorithm alongside product identities to compute the GCD and LCM instantly.

3

Inspect Factors & Copy Output

Review the prime factor breakdown and step-by-step simplification logs. Copy the mathematical results with one click.

Euclidean Algorithm Engine

Implements Euclid's algorithm from 300 BC with logarithmic time complexity O(log min(a, b)), evaluating huge numbers in microseconds.

Multi-Number Arbitrary Array Support

Extends beyond pairwise arithmetic to accept arrays of 3, 5, or more integers via associative folding algorithms.

100% Client-Side Privacy

All arithmetic executes locally inside browser memory. Academic formulas and project numbers remain 100% private.

Number Theory Applications & Math Tips

  • •Simplify display aspect ratios with GCD: For 1920×1080, GCD is 120. Dividing both by 120 yields the familiar 16:9 widescreen ratio.
  • •Gear meshing periods via LCM: For gears with 12 and 30 teeth, LCM is 60. Gears align back to starting teeth every 60 teeth of travel.
  • •Coprime numbers protect HTTPS: When GCD(a, b) = 1, numbers are coprime. RSA encryption relies on picking coprime public exponents against totient functions.

Code & Transformation Examples

Multi-Number GCD & LCM Calculation Benchmark

Input Integer Array
24, 36, 60
Factorization & Computed Outputs
• 质因数分解 :
  24 = 2³ × 3
  36 = 2² × 3²
  60 = 2² × 3 × 5

• 最大公约数 (GCD) : 2² × 3 = 12 (公共质因数的最低次幂乘积)
• 最小公倍数 (LCM) : 2³ × 3² × 5 = 360 (所有质因数的最高次幂乘积)

* For any two numbers, the product identity holds universally: `a × b = GCD(a, b) × LCM(a, b)`.

JavaScript Euclidean Algorithm Snippet

Pairwise GCD and LCM
// 欧几里得辗转相除法
function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

// 利用乘积恒等式求 LCM
function lcm(a, b) {
  return (a * b) / gcd(a, b);
}
Array Array Reduction
// 借助 Array.reduce 推广到多个数字
function arrayGcd(arr) {
  return arr.reduce((acc, v) => gcd(acc, v));
}
console.log(arrayGcd([24, 36, 60])); // 输出: 12

* The Euclidean algorithm converges in dozens of steps even for billion-magnitude integers.

Frequently Asked Questions

Q: Why is the GCD of negative numbers always positive?

A: Number theory formally defines GCD and LCM as positive integers. Calculations evaluate absolute values, so results are strictly positive.

Q: What is the GCD if one of the numbers is zero?

A: Because any number divides zero (`0 = a × 0`), GCD(a, 0) strictly equals `|a|`. GCD(0, 0) is mathematically undefined.

Q: Will large numbers cause floating-point precision overflow during LCM?

A: The engine divides before multiplying (`(a / gcd) * b`) to avoid overflow, and seamlessly switches to native BigInt for arbitrary precision.

Related Tools

All processing happens locally in your browser. Your data is never uploaded to a server.
/