Check if two or more numbers are relatively prime (coprime), see Euclidean algorithm steps, prime factorizations, totient values, and coprimality grids.
Two integers are **relatively prime** (also called **coprime** or **mutually prime**) when their greatest common divisor (GCD) equals 1 — meaning they share no prime factors. This concept is fundamental throughout number theory, cryptography, and algebra.
Coprime pairs appear everywhere in mathematics. In RSA encryption the public exponent must be coprime to Euler's totient of the modulus. In modular arithmetic, multiplicative inverses exist only when the base and modulus are coprime. Fractions are in lowest terms precisely when numerator and denominator are coprime. The Chinese Remainder Theorem requires pairwise-coprime moduli.
This calculator lets you enter two (or three) integers and instantly see whether they are coprime, along with the full Euclidean-algorithm trace, prime-factorization comparison with shared primes highlighted, Euler's totient of each number, a full list of integers coprime to a within any range, and an interactive coprimality grid for visualising the pattern. Presets including both coprime and non-coprime pairs let you explore without typing.
Checking whether numbers are coprime is a core step in dozens of mathematical and computational contexts — from writing fractions in lowest terms to applying the Chinese Remainder Theorem. This calculator goes beyond a simple yes/no verdict: it shows the full Euclidean-algorithm trace, highlights shared prime factors, computes Euler's totient for each input, lists all coprimes within a range, and generates a colour-coded coprimality grid.
Students preparing for number-theory courses, competitive-math contests, or cryptography exams will find every intermediate value exposed and explained. Engineers working with modular arithmetic, hash designs, or random-number generators can quickly verify coprimality assumptions without coding a helper script.
Euclidean Algorithm: GCD(a, b) = GCD(b, a mod b) until remainder = 0. Two integers are relatively prime iff GCD(a, b) = 1. Euler's totient φ(n) counts integers in [1, n] coprime to n.
Result: Coprime (GCD = 1)
8 = 2³ and 15 = 3 × 5 share no prime factors, so GCD(8, 15) = 1 and they are relatively prime. LCM(8, 15) = 120 = 8 × 15. φ(8) = 4, φ(15) = 8.
Coprime integers form the backbone of many classical results. Euler's totient function φ(n) counts integers less than n that are coprime to it, and Euler's theorem states that \(a^{\varphi(n)} \equiv 1 \pmod{n}\) when a and n are coprime. The Chinese Remainder Theorem (CRT) guarantees a unique solution to a system of simultaneous congruences when all moduli are pairwise coprime. Bézout's identity says that GCD(a, b) = 1 implies integers x, y exist with ax + by = 1 — the foundation for computing modular inverses.
RSA key generation selects primes p, q, computes n = pq and φ(n) = (p−1)(q−1), then picks a public exponent e coprime to φ(n). The Extended Euclidean Algorithm finds d ≡ e⁻¹ (mod φ(n)). Hash-table design often uses table sizes coprime to stepping increments to ensure full coverage. Linear congruential generators require the multiplier and modulus to be coprime for maximum period.
The probability that two random integers are coprime is 6/π² ≈ 61 %, a beautiful link between number theory and analysis. This density is visible in the coprimality grid, where roughly 61 % of cells are green. Open questions include efficient coprimality testing for extremely large multi-prime moduli and generalizations of Euler's totient to algebraic number fields.
Two integers are relatively prime (coprime) when their greatest common divisor is 1 — they share no prime factors. Note that 1 is coprime to every integer.
Run the Euclidean algorithm: repeatedly divide the larger by the smaller and replace with the remainder. If the last nonzero remainder is 1, the numbers are coprime.
Pairwise coprime means every pair in the set has GCD 1. Mutually coprime (setwise coprime) means the GCD of all numbers together is 1. Pairwise coprime is the stronger condition.
In RSA, the public exponent e must be coprime to φ(n) so that a unique decryption exponent d exists. Without coprimality there is no modular inverse and the scheme fails.
Yes. Any common divisor d of n and n+1 must also divide (n+1) − n = 1, so d = 1. Consecutive integers are always coprime.
Yes. GCD(1, n) = 1 for all n, so 1 is coprime to every integer. This is why Euler's totient φ(n) always counts at least 1.