What Are Coprime Numbers? Simple Guide & Euclid's Trick
Learn what coprime numbers are, why numbers like 8 and 9 are coprime even without being prime, how Euclid's square-tiling trick works, and why random pairs are coprime 61% of the time.
When simplifying fractions, studying clock math, or learning how online encryption keeps passwords safe, you will often see the word “coprime” (or “relatively prime”).
What does it actually mean for two numbers to be coprime? Do either of them have to be prime numbers? And how can computers check giant numbers in less than a millisecond?
In this friendly guide, we explain coprime numbers in plain English, picture how the ancient Euclidean shortcut tiles a floor with squares, see how working backwards unlocks RSA security keys, and find out why picking two random numbers gives you a surprising link to π (3.14159...).
1. What Are Coprime Numbers?
Two whole numbers a and b are coprime if their Greatest Common Factor (GCF)—often written gcd(a, b)—is 1:
gcd(a, b) = 1
In everyday words: the two numbers have NO prime factors in common. The only positive whole number that divides evenly into both a and b is 1. Think of them as “factor strangers.”
Common Myth: Neither Number Has to Be Prime!
Many students assume that for two numbers to be coprime, at least one must be a prime number. That is false!
Take 8 and 9:
- Factors of
8:1, 2, 4, 8(8 = 2 × 2 × 2, composite) - Factors of
9:1, 3, 9(9 = 3 × 3, composite)
Both 8 and 9 are composite numbers—yet look at the factors they share: only 1! That means 8 and 9 are coprime (gcd(8, 9) = 1).
In fact, any two back-to-back numbers (n and n + 1) are ALWAYS coprime (14 and 15, 99 and 100, 1,000 and 1,001). Since they are only 1 step apart, no factor bigger than 1 can land on both!
2. Euclid’s Fast Trick (Using Floor Tiles!)
How do you quickly find the biggest shared factor of two bigger numbers like 252 and 105?
Around 300 BCE, Greek mathematician Euclid wrote down a super-simple rule in his book Elements:
Euclid’s Rule: Divide the bigger number
aby the smaller numberb, and keep the remainderr. Whatever shared factor divides bothaandbalso dividesbandr:gcd(a, b) = gcd(b, remainder)
Because the remainder shrinks at every step, repeating this division zooms down to 0 almost right away. The last non-zero remainder is the Greatest Common Factor!
Picture It as Tiling a Floor: gcd(252, 105)
Imagine covering a 252 × 105 rectangular room with the largest matching square tiles possible, without cutting a single tile:
- Lay down
105 × 105square tiles: Two105 × 105squares fit side by side (2 × 105 = 210):252 = 2 × 105 + 42That leaves an empty strip of floor sized105 × 42. - Fill the leftover strip with
42 × 42tiles: Two42 × 42squares fit inside (2 × 42 = 84):105 = 2 × 42 + 21Now only a tiny42 × 21strip is left. - Finish with
21 × 21tiles: Two21 × 21squares cover the rest with zero space left over:42 = 2 × 21 + 0 - Answer:
The largest square tile that fits both lengths cleanly is 21 × 21, so
gcd(252, 105) = 21. Since the biggest shared factor is21(not1),252and105are not coprime.
3. Working Backwards & Online Security Keys
If you trace Euclid’s division steps in reverse (a method called the Extended Euclidean Algorithm), you can always find two whole numbers x and y such that:
a × x + b × y = gcd(a, b)
When a and b are coprime (gcd(a, b) = 1), that becomes:
a × x + b × y = 1
Why Internet Locks Need Coprimes (RSA Security)
When websites lock messages with RSA encryption, they pick a public “lock” number e and create a matching private “unlock” number d. For that unlock key d to actually exist and reverse the lock in clock arithmetic, e must be coprime to a hidden secret count (p − 1)(q − 1).
Without gcd = 1, no unlock key would exist! Running Euclid’s steps backwards finds the exact private unlock key d in milliseconds.
4. Seeing Coprime Numbers on a Tree Grid
What do coprime numbers look like in space?
Pretend you are standing at the corner (0, 0) of a giant orchard where a tree grows at every whole-number grid spot (x, y). Which trees can you see directly, and which ones are hidden right behind a closer tree?
You have a clear line of sight to a spot (x, y) only when gcd(x, y) = 1!
If x and y share a factor g (say (6, 4) share 2), then the closer tree at (3, 2) stands right on the exact same line between you and (6, 4), blocking your view!
Surprising Fun Fact: ~60.79% Chance!
Suppose you reach into a jar and pull out two giant positive whole numbers completely at random. What are the odds they share zero factors (gcd = 1)?
- For any prime
p, the chance a random number divides bypis1 / p. - The chance both random numbers divide by
pis(1 / p) × (1 / p) = 1 / p². - So the chance
pdoes not divide both is1 − 1 / p².
For two numbers to be coprime, no prime can divide both of them. In 1734, Swiss mathematician Leonhard Euler proved that multiplying (1 − 1/2²) × (1 − 1/3²) × (1 − 1/5²) × ... across every prime number gives an exact famous fraction:
Chance two random numbers are coprime = 6 / π² ≈ 0.6079 (about 60.79%)
Roughly 3 out of every 5 random number pairs are coprime!
5. Clean Code in Python & JavaScript
Python (Euclid’s Shortcut + Reverse Solver)
def gcd(a: int, b: int) -> int:
"""Finds the Greatest Common Factor of a and b quickly."""
while b != 0:
a, b = b, a % b
return abs(a)
def are_coprime(a: int, b: int) -> bool:
"""Returns True if a and b share no factors except 1."""
return gcd(a, b) == 1
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""
Finds (g, x, y) such that a*x + b*y = g = gcd(a, b).
Helps find private unlock keys in RSA security.
"""
if b == 0:
return (abs(a), 1 if a >= 0 else -1, 0)
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return (g, x, y)
print(are_coprime(8, 9)) # True (both composite, GCF is 1)
print(are_coprime(14, 25)) # True (14=2*7, 25=5*5)
print(are_coprime(15, 25)) # False (both divide by 5)
JavaScript (BigInt Version for Giant Whole Numbers)
export function gcd(a, b) {
let x = BigInt(a);
let y = BigInt(b);
while (y !== 0n) {
const temp = y;
y = x % y;
x = temp;
}
return x < 0n ? -x : x;
}
export function areCoprime(a, b) {
return gcd(a, b) === 1n;
}
Quick Questions & Answers
Are all prime numbers coprime to each other?
Yes. Two different prime numbers only have 1 and themselves as factors, so the only factor they can share is 1 (for instance, gcd(7, 13) = 1).
Can two composite numbers be coprime?
Yes! Just like 8 (2 × 2 × 2) and 9 (3 × 3), two composite numbers are coprime whenever their prime factor lists don’t overlap.
Is 1 coprime to every number?
Yes. Since the only positive factor of 1 is 1, gcd(1, n) = 1 for every whole number n—even 1 itself (gcd(1, 1) = 1).
Try Our Interactive Calculators
- Check if two numbers are coprime step by step: Coprime Calculator
- Reduce fractions using prime factors: Fraction Prime Factorization
- Watch how prime keys lock messages: RSA Prime Demo Calculator
- Break any number into primes: Prime Factorization Calculator
Want to check a prime number right now?
Our free online calculator checks numbers up to 18 quintillion with 100% accuracy, giving you instant factor trees and clear step-by-step reasons.
Written in plain, friendly English and checked against trusted math research and automated tests.