Relatively Prime Calculator

Enter two integers to find their greatest common divisor (GCD) via the Euclidean algorithm and determine whether they are relatively prime (coprime), plus their LCM and reduced ratio.

Quick Facts

Coprime condition
gcd(a, b) = 1
Two integers are relatively prime when they share no common positive factor other than 1.
Euclidean algorithm
gcd(a, b) = gcd(b, a mod b)
Repeatedly replace the larger number with the remainder until it reaches 0.
LCM relation
lcm(a, b) = |a × b| / gcd(a, b)
Relatively prime numbers have an LCM equal to the plain product |a × b|.

Your Results

Calculated
Greatest Common Divisor
-
gcd(a, b)
Relatively Prime?
-
Yes when gcd(a, b) = 1
Least Common Multiple
-
lcm(a, b) = |a×b| / gcd(a, b)
Reduced Ratio a : b
-
a/gcd : b/gcd, in lowest terms

Ready

Enter two integers, then press Calculate.

How the Relatively Prime Calculator works

Two integers a and b are relatively prime (also called coprime) when their greatest common divisor is 1: gcd(a, b) = 1. This has nothing to do with whether a or b are prime themselves — it only means they share no common positive factor larger than 1. This calculator computes gcd(a, b) with the Euclidean algorithm, reports whether the pair is relatively prime, and also derives the least common multiple (LCM) and the reduced ratio a : b.

The Euclidean algorithm

The fastest way to find gcd(a, b) is the Euclidean algorithm: divide the larger number by the smaller one and keep the remainder, then repeat with (smaller number, remainder) until the remainder hits 0 — the last nonzero remainder is the GCD. For example, gcd(14, 9): 14 mod 9 = 5, then 9 mod 5 = 4, then 5 mod 4 = 1, then 4 mod 1 = 0, so gcd(14, 9) = 1, which means 14 and 9 are relatively prime. The calculator uses negative-safe absolute values, so gcd(-14, 9) still returns 1.

Determining if two numbers are relatively prime

Once gcd(a, b) is known, the relatively-prime check is simple: if the GCD equals 1, the numbers are relatively prime; any GCD greater than 1 means they share that value as a common factor and are not relatively prime. From the same GCD, the calculator derives two useful bonus values: the LCM, using lcm(a, b) = |a × b| / gcd(a, b), and the fully reduced ratio a/gcd(a,b) : b/gcd(a,b), which is exactly how you would simplify the fraction a/b to lowest terms.

Common mistakes

  • Confusing "relatively prime" with "prime": 14 and 9 are relatively prime even though neither is a prime number — relatively prime describes a pair, not a single number's primality.
  • Assuming shared even/odd parity matters: two odd numbers can still share a large common factor (15 and 9 both share 3), and one even plus one odd number can still be relatively prime (8 and 9).
  • Forgetting the zero case: gcd(0, n) = |n|, so 0 is relatively prime only to 1 or -1, and gcd(0, 0) is undefined.

Real-world applications

  • Simplifying fractions to lowest terms uses the same GCD computed here — divide numerator and denominator by gcd(a, b).
  • Cryptography (including RSA key generation) relies on choosing exponents that are relatively prime to a modulus.
  • Gear and pulley design uses coprime tooth counts so that two meshing gears don't repeatedly pair the same teeth, spreading out wear evenly.
  • Scheduling and cycle problems (for example, finding when two repeating events next align) use the LCM, which is smallest when the two numbers are relatively prime.

Frequently Asked Questions

What does it mean for two numbers to be relatively prime?
Two integers a and b are relatively prime (also called coprime) when their greatest common divisor is 1, that is gcd(a,b) = 1. They share no common positive factor other than 1, even though neither number needs to be prime itself. For example, 14 and 9 are relatively prime because gcd(14,9) = 1, even though 14 = 2×7 and 9 = 3×3 share no common prime factors.
How do you calculate the GCD to check if two numbers are relatively prime?
The fastest method is the Euclidean algorithm: repeatedly replace the larger number with the remainder of dividing it by the smaller number until the remainder is 0. The last nonzero value is the GCD. For example, gcd(14,9): 14 mod 9 = 5, 9 mod 5 = 4, 5 mod 4 = 1, 4 mod 1 = 0, so gcd(14,9) = 1, confirming they are relatively prime.
Are two prime numbers always relatively prime?
Yes, unless they are the same prime number. Any two distinct primes are always relatively prime because a prime's only positive divisors are 1 and itself, so two different primes share no common factor besides 1. A prime is not relatively prime to itself, since gcd(p,p) = p, not 1.
Can zero or negative numbers be relatively prime?
Negative integers are handled using absolute values, so gcd(-14, 9) = gcd(14, 9) = 1. Zero is a special case: gcd(0, n) = the absolute value of n, so 0 is relatively prime only to 1 or -1; it is never relatively prime to any other nonzero number, and gcd(0,0) is undefined.

Related calculators