Sign up

GCD / HCF

Find the greatest common divisor of two or more numbers.

Number Input

Separate two or more integers with commas or spaces.

Greatest Common Divisor
—

Calculation Breakdown:

Enter values to compute.

Euclidean Algorithm Steps
—
Find the Greatest Common Divisor using Euclidean algorithm.

About this topic

Greatest Common Divisor (GCD) The largest number that divides two integers evenly.

The GCD (or Highest Common Factor) is the largest positive integer that divides both numbers without leaving a remainder. It is used to simplify fractions and solve Diophantine equations.

Key formulas & rules

  • •Always non-negative
  • •GCD(a, 0) = |a|
  • •GCD(a, b) = GCD(b, a mod b)
  • •If GCD(a, b) = 1, they are coprime
  • •Calculated via Euclidean algorithm
  • •Works for multiple numbers

Examples

Input Output Note
GCD(12, 18) 6 Largest common divisor
GCD(7, 13) 1 Coprime
GCD(24, 36) 12 Standard
GCD(100, 10) 10 One divides the other

Real-world uses

Simplifying fractions Cryptography Gear ratios
The Euclidean Algorithm An ancient and efficient method to find the GCD.

Dating back to 300 BC, this algorithm repeatedly replaces the larger number with the remainder of dividing the larger by the smaller until the remainder is zero.

Key formulas & rules

  • •Requires only subtraction and division
  • •Very fast (logarithmic time)
  • •No factorization needed
  • •Terminates when remainder is 0
  • •Foundation of modern cryptography

Examples

Input Output Note
48 & 18 48=2(18)+12 Step 1
18 & 12 18=1(12)+6 Step 2
12 & 6 12=2(6)+0 Step 3
GCD 6 Last non-zero remainder

Real-world uses

RSA encryption Modular arithmetic Algorithm design
Common Divisors All numbers that divide a set of integers.

Any integer that divides two or more numbers without a remainder. The Greatest Common Divisor is the largest of these. Listing all common divisors helps verify the GCD.

Key formulas & rules

  • •Always includes 1
  • •The largest is the GCD
  • •Every common divisor divides the GCD
  • •Finite set of divisors
  • •Can be found by factoring
  • •Useful for grouping

Examples

Input Output Note
12 & 18 1, 2, 3, 6 GCD is 6
24 & 36 1, 2, 3, 4, 6, 12 GCD is 12
7 & 11 1 Coprime
10 & 20 1, 2, 5, 10 GCD is 10

Real-world uses

Grouping objects evenly Tiling patterns Harmonic ratios

Modes & formulas

1

GCD & Euclidean Steps

• The GCD is the largest positive integer that divides all of the given integers without leaving a remainder. • Enter two or more positive integers. • The calculator shows the step-by-step division process and a list of all common divisors.
GCD(a, b) = GCD(b, a mod b) until remainder = 0

The Euclidean algorithm repeatedly replaces the larger number with the remainder. When the remainder becomes 0, the other number is the GCD.

How to use it

Enter two or more integers separated by commas. The tool displays the GCD, all common divisors, and the step-by-step Euclidean algorithm.

Frequently asked questions

Can GCD be negative?
GCD is always defined as a non-negative integer. The tool takes absolute values before computing.
What is the GCD of 0 and any number?
GCD(0, n) = |n|, because every number divides 0.
What is the Greatest Common Divisor (GCD)?
The largest positive integer that divides two or more numbers without leaving a remainder.
What is another name for GCD?
It is also known as the Highest Common Factor (HCF) or Greatest Common Factor (GCF).
What is the Euclidean algorithm?
An ancient, efficient method to find the GCD. It repeatedly replaces the larger number with the remainder of dividing the larger by the smaller until the remainder is zero.
What does it mean if the GCD is 1?
It means the two numbers are coprime (relatively prime). They share no common factors other than 1.

Related calculators

Prime Number Check if a number is prime and find factors. Factorial Compute factorials for non-negative integers. LCM Find the Least Common Multiple of numbers. Random Number Generate random numbers within a specified range. Number Base Convert between Binary, Octal, Decimal, and Hexadecimal.
Read the full GCD / HCF guide — examples & 18 FAQs