Relatively Prime Calculator

About the Relatively Prime Calculator

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 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.

When This Page Helps

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.

How to Use the Inputs

1. Enter the first integer a in the "Number a" field or click a preset pair.
2. Enter the second integer b in the "Number b" field.
3. Read the GCD and coprime verdict cards — GCD = 1 means coprime.
4. Review the Euclidean algorithm step table for the full computation.
5. Compare prime factorizations — red chips mark shared primes.
6. Optionally enter a third number c to test pairwise coprimality.
7. Adjust "List coprimes up to" to explore coprime counts in a range.

Example Calculation

Tips & Best Practices

• Click a preset pair to load both coprime and non-coprime examples.
• Enter a third number c to test pairwise coprimality of three numbers simultaneously.
• The coprimality grid reveals the diagonal symmetry and patterns (e.g., Farey sequences, Stern-Brocot).
• If GCD ≠ 1, look at the red-highlighted shared primes to understand which factor prevents coprimality.
• The list of coprimes to a corresponds to the totient function — its count equals φ(a).
• Consecutive integers (n, n+1) are always coprime — verify this with any preset.

Coprimality in Number Theory

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.

Applications in Cryptography and Computing

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.

Coprimality Density and Open Questions

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.

Frequently Asked Questions

• What does relatively prime mean?

  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.

• How do I quickly check if two numbers are coprime?

  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.

• What is the difference between pairwise coprime and mutually 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.

• Why is coprimality important in cryptography?

  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.

• Are consecutive integers always coprime?

  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.

• Is 1 relatively prime to every number?

  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.