Check if two or three integers are coprime (relatively prime). Get GCD, prime factorizations, pairwise coprimality, and an interactive Venn diagram of common prime factors.
Two integers a and b are said to be coprime (or relatively prime) if their greatest common divisor (GCD) equals 1. In other words, they share no positive prime factors. For example, 8 and 15 are coprime because gcd(8,15)=1. Coprimality is fundamental in number theory, modular arithmetic, and modern cryptography (RSA, Diffie-Hellman).
gcd(a, b) = 1 ⇔ a and b are coprime
This tool extends the concept to three numbers: setwise coprime if gcd(a,b,c)=1, but pairwise coprimality requires every pair to be coprime. Our interactive Venn diagram visualizes the prime factor intersection — an empty common region indicates full pairwise coprimality.
Based on the ancient Euclidean algorithm (c. 300 BCE), our GCD computation is both efficient and exact. For prime factorization, we use trial division optimized up to √n, displaying exponents and distinct prime sets. The Euclidean algorithm steps are displayed to enhance learning. The concept of coprime numbers is deeply linked to Euler's totient function φ(n), which counts numbers ≤ n that are coprime to n, and to the RSA encryption system where the public exponent e must be coprime to φ(n).
In RSA, we choose two distinct primes p and q. The modulus N = p·q, and we select encryption exponent e such that gcd(e, φ(N)) = 1, where φ(N) = (p-1)(q-1). This coprimality condition ensures that a unique decryption exponent exists. Without it, the cryptosystem fails. Using our coprime checker, students and engineers can validate conditions before implementation. Additionally, the concept of coprime numbers appears in generating primitive Pythagorean triples and in the design of coprime sequences for signal processing.
The Euclidean algorithm is one of the oldest algorithms documented (Euclid's Elements, c. 300 BC). The term "coprime" was introduced in the 19th century by mathematicians like Gauss (Disquisitiones Arithmeticae). Modern references include Hardy & Wright's "An Introduction to the Theory of Numbers" and the On-Line Encyclopedia of Integer Sequences (OEIS). Our implementation follows rigorous integer arithmetic and is verified against known coprime pairs.
| Number pair (a,b) | GCD | Coprime? | Prime factors overlap |
|---|---|---|---|
| (8,15) | 1 | Yes | 2³ vs 3·5 → none |
| (18,24) | 6 | No | 2·3² , 2³·3 → common {2,3} |
| (7,13) | 1 | Yes | 7 and 13 → distinct primes |
| (6,10,15) | 1 setwise | Pairwise? No (gcd(6,10)=2) | Pairwise intersections exist |