Relatively Prime Calculator - GCD Coprime Checker

A relatively prime calculator is a number-theory tool that tells you whether two or more positive integers share any common factor greater than 1, using the Euclidean GCD test as its deciding rule. Two integers are called coprime (or relatively prime) when their only shared factor is 1, and a set is pairwise coprime when every pair satisfies that condition.

• • Homework and Exam Verification: Check a discrete-math or number-theory problem that asks 'are a and b relatively prime?' without re-deriving the Euclidean algorithm by hand.
• • Modular Arithmetic and CRT Preconditions: Confirm the coprime-modulus precondition for the Chinese Remainder Theorem, Euler's totient function, or a private-key RSA-CRT step.
• • Fraction Reduction and Simplification: Decide whether a numerator and denominator are already in lowest terms, because GCD = 1 is exactly the condition for an irreducible fraction.
• • Probability and Totient Counting: Estimate Euler's totient φ(n) by counting how many integers up to n are coprime to n, which is the probability that two random integers are coprime.

Relatively prime numbers are a foundational concept in number theory, and the GCD = 1 test is what unifies the simple two-number case with the more nuanced setwise and pairwise cases.

If you are still warming up on what 'prime' means on its own, the Prime Number Checker explains the primality test that the GCD routine leans on.

The calculator parses the input numbers, computes the GCD of the entire set, builds a pairwise GCD matrix, and reports a verdict, the matrix, and the list of shared prime factors.

• a, b, c, …: The input integers. Each must be a positive integer (≥ 1) and the set must contain between 2 and 10 numbers.
• gcd(a, b): The greatest common divisor of a and b, computed by the Euclidean algorithm in O(log min(a, b)) steps.
• setGcd: The GCD of the whole set, computed by chaining gcd across the inputs. The set is setwise coprime if and only if setGcd = 1.
• pairwise matrix: The matrix whose (i, j) entry is gcd(aᵢ, aⱼ). The set is pairwise coprime if and only if every off-diagonal entry equals 1.

The Euclidean algorithm is the workhorse of every coprime check. It runs in O(log n) steps and never has to factor the inputs, so it scales to integers far larger than the 10-number default.

The setwise-versus-pairwise distinction matters for problems with three or more numbers. A set like {4, 6, 21} has setGcd = 1 because the shared factor 2 in 4 and 6 is balanced by 21, but the pair (4, 6) shares 2, so the set is not pairwise coprime. The matrix is what makes the difference visible in one glance.

According to Wikipedia - Coprime integers, two integers a and b are called coprime or relatively prime if the only positive integer that divides both of them is 1, which is the same as saying their greatest common divisor is 1.

Use the result with the Prime Factorization Calculator to see the full prime factor lists that the Euclidean algorithm does not need to compute.

Four short definitions carry the entire test, so it helps to keep them straight before reading the verdict.

The probability that two random integers are coprime is 6/π², a result that comes from Euler's product formula. When you start picking random integers and asking whether they are coprime, the share that pass the test is around 60.8 percent.

The coprime-modulus precondition for the Chinese Remainder Theorem is the same GCD = 1 test applied to a list of moduli, so the routine that powers the relatively prime verdict is the same one the constructive CRT formula depends on. Pairwise coprime moduli give a unique CRT solution; setwise coprime moduli can leave the constructive proof ambiguous.

The coprime-modulus precondition for Chinese Remainder Calculator is the same GCD = 1 test applied to a list of moduli, so the routine that powers the relatively prime verdict is the same one the constructive CRT formula depends on.

Enter your integers one per line, then read the verdict, the GCD, the pairwise matrix, and the shared prime factors from the result panel.

1. 1 List the Integers: Type one positive integer per line in the text box. Add as many as you need, up to ten. The default is two numbers (8 and 15) so the result panel is meaningful from the first keystroke.
2. 2 Skip the Noise: Leave blank lines or start a line with '#' to add comments. The parser ignores them, so you can keep the input readable while you experiment.
3. 3 Read the Verdict: The result panel updates as you type. The verdict line gives a single word: Relatively prime, Not relatively prime, Setwise relatively prime, or Pairwise relatively prime.
4. 4 Inspect the Pairwise Matrix: The pairwise GCD matrix lists the GCD of every distinct pair. If every off-diagonal entry is 1, the set is pairwise coprime; the matrix is the audit trail behind the verdict.
5. 5 Check the Shared Prime Factors: The shared prime factor list is empty when the verdict is relatively prime. When the verdict is not relatively prime, the list names the prime factors that appear in every input.

If you enter '4\n6\n21' the calculator reports the verdict 'Setwise relatively prime', the set GCD of 1, a pairwise matrix that highlights the (4, 6) entry of 2, and a shared factor list of 'none'. The same set {4, 7, 27} flips to 'Pairwise relatively prime' because every off-diagonal entry drops to 1.

The same GCD = 1 test is the precondition for a modular inverse: an integer a has a multiplicative inverse modulo n exactly when gcd(a, n) = 1, so the Modulo Calculator accepts coprime inputs for its Modular Inverse mode and rejects the rest.

This relatively prime calculator replaces a hand-rolled Euclidean algorithm with a tool that delivers a verdict, the underlying GCD, and the pairwise matrix in one pass.

• • GCD-Based Verdict: The Euclidean algorithm is the canonical test, so the verdict is the same answer you would get from a hand calculation or a CAS system.
• • Pairwise and Setwise Coverage: The calculator reports the strict pairwise condition and the weaker setwise condition, so a single input handles both interpretations of the test.
• • Pairwise Matrix Output: The full pairwise GCD matrix is included in the result panel, so you can see exactly which pair breaks coprimality when the verdict is not what you expected.
• • Scales From a Pair to Ten Numbers: The same algorithm processes two numbers or up to ten. The default input of 8 and 15 is meaningful from the first keystroke, and adding more lines just extends the matrix.
• • Shared Prime Factor List: The shared prime factor line names the exact primes that appear in every input, so the result is auditable without re-running the prime factorization by hand.

Because the verdict comes from the GCD, the result is the same one the Greatest Common Factor Calculator would return for the same input.

Three input choices and one mathematical precondition control the verdict, and they are worth understanding before scaling the test up.

• • The calculator only handles positive integers. Negative inputs, zero, and non-integer rows are rejected, and the error message points to the offending line so the input can be cleaned up.
• • The verdict is based on the GCD, which is exact for positive integers. The shared prime factor list is also exact, but the calculator does not detect equality-only-by-construction patterns such as (p, p) where p is prime; it just reports the GCD of p, which is p, and the shared prime factors list of {p}.
• • The shared prime factor list is an intersection of prime factors, not an intersection of full factorizations. A set like {12, 18} shares the prime factors 2 and 3, but the calculator does not compute the full GCD of 6 as a number — the result panel reports the GCD value (6) directly.

Two even numbers cannot be coprime, so the verdict on the pair (4, 6) is always negative. With a single odd prime, the verdict depends on whether the prime divides the even input: 2 and 9 are coprime, 2 and 6 are not.

As published by Wolfram MathWorld - Relatively Prime, two integers are relatively prime when their greatest common divisor is 1, and a set of integers is pairwise coprime when every member is coprime to every other member.