Coprime Calculator: Two Composite Numbers Can Still Be Coprime
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
A coprime calculator answers one question, and the surprising part is how often the intuitive answer is wrong. Are 8 and 9 coprime? Yes — even though neither is prime. Are 3 and 9 coprime? No — even though 3 is prime. Are 2,047 and 2,048 coprime? Yes, instantly, without factoring either one.
The word carries a trap. “Coprime” contains “prime”, so people read it as a claim about the individual numbers. It is not. It is a statement about the relationship between them: they have no prime factor in common. Everything below follows from that one sentence — the test, the sets where it goes strange, and the four or five things that quietly change the moment two numbers pass it.
Does “Coprime” Mean Both Numbers Are Prime?
No, and the four cases below cover every combination people expect to be impossible. Being prime is a property one number has on its own. Being coprime is something a pair has, and the two ideas barely overlap.
| Pair | Either one prime? | Coprime? | Why |
|---|---|---|---|
| 8, 9 | Neither | Yes | 2³ against 3² — different primes |
| 3, 9 | One is | No | 3 divides 9, so the gcd is 3 |
| 7, 13 | Both | Yes | two different primes always are |
| 11, 11 | Both | No | same prime twice — gcd is 11 |
Two primes are coprime only when they are different primes. And a composite number as chunky as 1,024 is coprime with 1,025 — 210 against 52 × 41. The sizes are irrelevant; only the prime lists matter, which is why the calculator prints those lists side by side instead of just handing you a verdict.
What a Coprime Calculator Actually Runs, and Why It Isn’t Factoring
There are two honest ways to check. Factor both numbers and compare the lists, or run the Euclidean algorithm and look at the last non-zero remainder. They always agree. They do not cost anything like the same.
Take 3,120 and 17, the pair that shows up in every RSA worked example. Factoring 3,120 by hand means grinding out 24 × 3 × 5 × 13 — five separate divisions before you even start comparing. Euclid takes three lines:
3120 = 183 × 17 + 9
17 = 1 × 9 + 8
9 = 1 × 8 + 1
8 = 8 × 1 + 0 → gcd = 1
Last non-zero remainder is 1, so 17 and 3,120 are coprime and RSA key generation can proceed. The reason this works is one line of algebra: any number dividing both 3,120 and 17 must also divide 3,120 − 183 × 17 = 9, so the problem shrinks without losing a single common divisor. Repeat until one side hits zero.
The gap widens fast. For numbers around 109, trial-division factoring needs up to about 31,600 test divisions; Euclid averages about 19. On the 2,048-bit numbers real cryptography uses, factoring is not slow — it is infeasible, while the coprimality check finishes in microseconds. If you want the gcd itself rather than the yes/no, the greatest common factor calculator runs the identical loop.
Why {6, 10, 15} Is Coprime but No Two of Them Are
Extend the question to three numbers and it splits in two, which almost nobody expects. Check 6, 10 and 15:
- gcd(6, 10) = 2 — they share a 2
- gcd(6, 15) = 3 — they share a 3
- gcd(10, 15) = 5 — they share a 5
- gcd(6, 10, 15) = 1 — no prime divides all three
So the set is setwise coprime (the gcd of everything is 1) while not a single pair inside it is coprime. The two conditions have different names because they have different uses, and using the weak one where the strong one is needed is a real bug, not a pedantic distinction.
The Chinese Remainder Theorem is where it bites. CRT lets you replace one big modulus with several small ones and solve independently — but only if the moduli are pairwise coprime. Feed it 6, 10 and 15 and it collapses: the system x ≡ 0 (mod 6), x ≡ 1 (mod 10) has no solution at all, because those two conditions disagree about x mod 2. The Chinese Remainder Theorem calculator rejects such a system for exactly this reason. Pairwise coprime implies setwise coprime; the reverse fails, and 6, 10, 15 is the smallest counterexample.
Five Things That Change the Moment gcd Hits 1
Coprimality is rarely the goal. It is the precondition that makes something else work. Here is what flips, using 8 and 15 (coprime) against 8 and 12 (gcd 4):
| Property | 8 and 15 (coprime) | 8 and 12 (gcd 4) |
|---|---|---|
| lcm | 120 = the plain product | 24, not 96 |
| Fraction a/b | 8/15 already reduced | 8/12 reduces to 2/3 |
| Inverse of a mod b | exists: 8 × 2 ≡ 1 (mod 15) | none exists |
| φ(ab) | φ(8)φ(15) = 4 × 8 = 32 | φ(96) = 32 ≠ φ(8)φ(12) = 16 |
| Remainder pair (x mod a, x mod b) | unique address for x mod 120 | collides — many x share a pair |
The inverse row is the one that shows up as an error message in real code. A modular inverse of a mod b exists if and only if gcd(a, b) = 1, no exceptions — try 8 mod 12 and every multiple of 8 you take mod 12 lands on 0, 4 or 8, never 1. That is the whole proof. The modular inverse calculator refuses the same inputs this page marks red.
Row four is worth a second look if you have ever wondered why φ is called multiplicative. The identity φ(ab) = φ(a)φ(b) is only true for coprime a and b — 8 and 12 break it by a factor of two. The Euler phi calculator counts those totients directly.
Roughly 61% of Random Pairs Turn Out Coprime
Pick two integers at random. The probability they are coprime converges to 6/π² ≈ 0.6079 — one of the prettier constants in number theory, and it drops out of a short argument. The chance both are even is 1/4, so the chance they avoid sharing a 2 is 1 − 1/4. Sharing a 3 costs 1/9, sharing a 5 costs 1/25, and the events are independent across distinct primes. Multiply:
(1 − 1/4)(1 − 1/9)(1 − 1/25)(1 − 1/49)… = 1/ζ(2) = 6/π²
Count it directly and the convergence is quick. Taking every ordered pair (a, b) with both values between 1 and N:
| N | Coprime pairs out of N² | Share |
|---|---|---|
| 10 | 63 | 63.0% |
| 100 | 6,087 | 60.9% |
| 1,000 | 608,383 | 60.8% |
Two practical readings. First, coprimality is common, so a “not coprime” verdict on numbers you expected to pass usually means you picked them from a structured set — all even, all multiples of 10, all from the same times table — rather than at random. Second, it is not so common that you can skip the check: two in five random pairs fail. Wikipedia’s article on coprime integers works through the density argument in full.
Where Coprimality Is a Hard Requirement
RSA key generation. The public exponent e must satisfy gcd(e, φ(n)) = 1, because the private key d is defined as the inverse of e modulo φ(n). Pick e = 65,537 — a prime, so it fails only when it happens to divide φ(n), which is rare enough that implementations just test and retry. The classroom version with n = 3,233, φ(n) = 3,120 and e = 17 is checkable by hand on this page.
Gear trains and wear. Give two meshing gears 12 and 18 teeth and gcd = 6, so each tooth on the small gear only ever meets 3 distinct partners; a burr grinds the same few teeth forever. Make it 12 and 17 and every tooth meets every tooth over one full cycle, spreading wear evenly. Machinists call the odd extra tooth a hunting tooth, and it is the same gcd = 1 condition wearing overalls.
Rhythm and timing. Two blinking indicators at 4 and 6 seconds resync every 12 seconds, not 24, because gcd = 2 halves the cycle. Coprime intervals — 4 and 7 — give the longest possible period, which is also why 13- and 17-year cicadas famously avoid predators on shorter cycles. Working the period out is just an LCM calculation, and the lcm equals the product exactly when the intervals are coprime.
Fractions in lowest terms. A fraction is fully reduced precisely when numerator and denominator are coprime. That is the definition, not a coincidence — which is why the simplify fractions calculator divides by the gcd and stops.
Shortcuts That Look Right and Aren’t
- “Both odd, so coprime.” 9 and 15 are both odd and share a 3. Avoiding 2 is one prime down and infinitely many to go. A quick divisibility check on 3, 5 and 7 catches most real cases.
- “One of them is prime, so coprime.” Only if that prime does not divide the other number. 5 and 35 fail; 5 and 36 pass.
- “They’re far apart, so coprime.” Distance is worthless — 100 and 1,000,000 share plenty. What matters is the difference: consecutive integers are always coprime, and if a divides both n and n+1 it divides 1.
- Forgetting the edge cases. gcd(1, n) = 1 for every n, so 1 is coprime with everything. gcd(0, n) = n, so 0 is coprime only with 1. And 11 with itself is not coprime — a number is coprime with itself only when it is 1.
- Assuming setwise implies pairwise. The 6, 10, 15 case above. If your algorithm needs independent moduli, test every pair, not the whole-set gcd.
The habit worth building is small: when a fraction refuses to simplify, when an lcm comes out smaller than the product, when a modular inverse errors out — all three are the same question wearing different clothes, and one gcd answers it.
