Relatively Prime Calculator — Coprime Checker
Enter two positive integers to find out whether they are relatively prime (coprime) — meaning their only common factor is 1 — with the full Euclidean algorithm shown step by step.
Divide 35 by 12
Divide 12 by 11
Divide 11 by 1
Remainder is 0 — GCD = 1, so the numbers are relatively prime
How does this calculator work?
Two integers are coprime (relatively prime) if and only if their GCD equals 1. Use the Euclidean algorithm: repeatedly replace (a, b) with (b, a mod b) until b = 0; the last non-zero value is the GCD. If GCD = 1, the numbers are coprime and share no prime factors.
Formula
How this is calculated
Two integers are called relatively prime (or coprime) if the only positive integer that divides both of them is 1 — in other words, their Greatest Common Divisor (GCD) equals 1. This is a key property in number theory and is used throughout mathematics: a fraction is in lowest terms when its numerator and denominator are coprime; RSA encryption relies on picking two large coprime numbers; and the Chinese Remainder Theorem applies precisely when moduli are pairwise coprime.
This calculator uses the Euclidean algorithm to find the GCD. It works by repeatedly replacing the pair (a, b) with (b, a mod b) because any common divisor of a and b also divides the remainder a mod b. When the remainder reaches 0, the last non-zero value is the GCD. If that value is 1, the numbers are coprime; if it is greater than 1, they share at least one prime factor.
The algorithm is guaranteed to terminate because remainders strictly decrease, and it runs in O(log min(a, b)) steps — extremely efficient even for very large numbers. The Least Common Multiple (LCM) is also shown using the identity LCM(a, b) = (a × b) / GCD(a, b).
Frequently asked questions
Two integers are relatively prime (coprime) when they share no common factor greater than 1. For example, 35 and 12 are coprime because 35 = 5 × 7 and 12 = 2² × 3 share no prime factors. Note: neither number needs to be prime itself — "relatively prime" is a relationship between two numbers, not a property of a single number.
Yes. The integer 1 has no prime factors, so GCD(1, n) = 1 for every positive integer n. This means 1 is coprime to every positive integer.
The Euclidean algorithm finds GCD(a, b) by repeatedly computing remainders: replace (a, b) with (b, a mod b) until b = 0; at that point a is the GCD. It is one of the oldest algorithms in mathematics, described by Euclid around 300 BC, and remains the fastest general method for computing the GCD.
Also known as
TG we-Calculate Editorial Team. (2026). Relatively Prime Calculator — Coprime Checker [Online calculator]. TG we-Calculate. https://we-calculate.com/calculator/relatively-prime-calculator
TG we-Calculate Editorial Team. "Relatively Prime Calculator — Coprime Checker." TG we-Calculate. 2026. https://we-calculate.com/calculator/relatively-prime-calculator.
TG we-Calculate Editorial Team, "Relatively Prime Calculator — Coprime Checker," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/calculator/relatively-prime-calculator
@misc{wecalculate_relatively_prime_calculator, title = {Relatively Prime Calculator — Coprime Checker}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/calculator/relatively-prime-calculator}}, year = {2026}, note = {TG we-Calculate} }
Did this calculator help you?