GCD

The GCD (greatest common divisor) is the largest positive integer that divides two or more integers, computed efficiently with the Euclidean algorithm.

Purpose

To find the largest common factor of integers, used in fraction reduction and number theory.

Mechanism

Euclidean algorithm: gcd(a,b) = gcd(b, a mod b), until b=0. The extended Euclidean algorithm additionally finds Bezout coefficients x,y with ax+by=gcd(a,b), used for modular inverses. lcm(a,b) = |a×b|/gcd(a,b).

Use cases

Fraction reduction
Modular inverse computation
RSA key validation
Rational arithmetic

Examples

Input
```
gcd(48, 18)
```
Output
```
6
```
48=6×8, 18=6×3

Common errors

gcd with 0 left unhandled: gcd(a,0)=|a|, gcd(0,0)=0

Related terms

The LCM (least common multiple) is the smallest positive integer that is a multiple of two or more integers, computed via the GCD.

Modular Arithmetic

Modular arithmetic takes remainders after integer operations, keeping results within [0, n); it is the foundation of number theory and cryptography.

A prime number is a natural number greater than 1 divisible only by 1 and itself; it is the building block of number theory, and every integer factors uniquely into primes.

Related tools

Precision Calculator

High-precision arithmetic calculator. No floating-point errors. Free, private, 100% client-side.

References