Relatively Prime Calculator

What Are Relatively Prime Numbers?

Two integers a and b are called relatively prime (also known as coprime or mutually prime) when their greatest common divisor equals 1. The formal condition is: gcd(a, b) = 1. This means the two numbers share no common prime factor — the only positive integer that divides both is 1. The relatively prime calculator determines this relationship instantly using the Euclidean Algorithm.

The Core Formula and Derivation

The coprimality test reduces to a single computation:

gcd(a, b) = 1 if and only if a and b are relatively prime

The Euclidean Algorithm, attributed to Euclid circa 300 BCE, computes gcd(a, b) through successive division steps:

• Divide a by b to obtain quotient q and remainder r such that a = q · b + r.
• Replace a with b and b with r.
• Repeat until r = 0. The last nonzero value of b is gcd(a, b).

This algorithm runs in O(log min(a, b)) steps, making it efficient even for integers with hundreds of digits. According to Carnegie Mellon University's number theory course notes, the Euclidean Algorithm is one of the oldest and most fundamental computational tools in all of mathematics, predating modern algebra by over two millennia.

Worked Examples

Example 1: Relatively Prime Pair — 14 and 25

To test gcd(14, 25) using the Euclidean Algorithm:

• 25 = 1 · 14 + 11 → gcd(14, 11)
• 14 = 1 · 11 + 3 → gcd(11, 3)
• 11 = 3 · 3 + 2 → gcd(3, 2)
• 3 = 1 · 2 + 1 → gcd(2, 1)
• 2 = 2 · 1 + 0 → gcd = 1

Since gcd(14, 25) = 1, this pair is relatively prime. Their prime factorizations — 14 = 2 × 7 and 25 = 5² — share no common prime factors, confirming the result.

Example 2: Not Relatively Prime — 18 and 24

To test gcd(18, 24):

• 24 = 1 · 18 + 6 → gcd(18, 6)
• 18 = 3 · 6 + 0 → gcd = 6

Since gcd(18, 24) = 6 ≠ 1, these numbers share the common factor 6 and are not relatively prime. Their factorizations — 18 = 2 × 3² and 24 = 2³ × 3 — overlap at both 2 and 3.

Variables Explained

• a — First Integer: Any positive integer to be tested. The algorithm handles arbitrarily large values without loss of accuracy.
• b — Second Integer: The second positive integer in the pair. Input order does not affect the result because gcd(a, b) = gcd(b, a).
• mode — Output Mode: Controls what the calculator returns. Coprimality mode outputs 1 (coprime) or 0 (not coprime); GCD mode returns the actual greatest common divisor so users can inspect the shared factor directly.

Real-World Applications

Coprimality appears across mathematics, computer science, and engineering in ways that affect everyday technology:

• RSA Cryptography: The RSA algorithm requires the public exponent e and Euler's totient φ(n) to satisfy gcd(e, φ(n)) = 1. This ensures e has a multiplicative inverse modulo φ(n), enabling decryption. Without this condition, the private key cannot be constructed.
• Fraction Simplification: A fraction a/b is in lowest terms if and only if gcd(a, b) = 1. Reducing 12/18 yields 2/3 because gcd(12, 18) = 6; then gcd(2, 3) = 1 confirms full reduction.
• Gear Engineering: Coprime tooth counts ensure every tooth on one gear contacts every tooth on the mating gear before any pair repeats, distributing wear evenly and extending gear life.
• Chinese Remainder Theorem: As established in Penn Math's number theory lecture notes, the theorem guarantees a unique simultaneous solution modulo m₁ · m₂ · … · m_k only when all moduli are pairwise coprime — a result central to cryptographic protocols and computer algebra systems.
• Period Synchronization: Two periodic events with cycle lengths a and b next coincide after lcm(a, b) = a · b / gcd(a, b) steps. When gcd(a, b) = 1, this equals a · b — the maximum possible synchronization interval.

Key Properties of Coprime Integers

• Any two consecutive integers n and n + 1 are always relatively prime, since gcd(n, n + 1) = 1 for all positive integers n.
• The integer 1 is coprime to every positive integer.
• Two distinct prime numbers p and q are always coprime, because each has no divisors other than 1 and itself.
• If gcd(a, b) = d, then gcd(a/d, b/d) = 1 — dividing both numbers by their GCD always produces a coprime pair.
• Euler's totient function φ(n) counts the positive integers up to n that are coprime with n, making coprimality a cornerstone of modular arithmetic and public-key cryptography.