Math
Relatively Prime Calculator
Enter two or more whole numbers to find out if they are relatively prime, which means their greatest common divisor is 1.
The Euclidean algorithm is written out division by division so you can follow how the gcd is found, and when the numbers share a factor the prime factorizations show exactly which primes they have in common. Switch to the totient mode to count how many integers from 1 to n are coprime to n using φ(n) = n × Π(1 - 1/p).
Two or more positive whole numbers separated by commas or spaces. Up to 10^12 each.
Try an example
Result
Result
—
- Greatest common divisor
- —
- Prime factorizations
- —
- Shared prime factors
- —
- Also
- —
Student quick launch
Grade planning, algebra checks, and formulas students reach for most.
Study path
Use this calculator with
Follow these when you want the formula behind the answer, a short lesson, or nearby tools in the same topic.
What the relatively prime calculator solves
Two integers are relatively A whole number above 1 whose only factors are 1 and itself., or coprime, when the only positive number dividing both is 1. Neither has to be prime itself: 15 and 28 are coprime even though 15 = 3 × 5 and 28 = 2^2 × 7, because they share no prime. Coprime pairs matter for reducing fractions, for the Chinese remainder theorem, for RSA key generation, and for knowing when lcm(a, b) equals a × b. This calculator runs the Euclidean algorithm to find the The largest number that divides evenly into every number in a set. and shows the factorizations so the shared primes, if any, are visible.
| Pair | Factorizations | gcd | Relatively prime? |
|---|---|---|---|
| 15, 28 | 3 × 5 and 2^2 × 7 | 1 | yes |
| 12, 18 | 2^2 × 3 and 2 × 3^2 | 6 | no (share 2 and 3) |
| 8, 9 | 2^3 and 3^2 | 1 | yes |
| 7, 21 | 7 and 3 × 7 | 7 | no |
| 1, 100 | 1 and 2^2 × 5^2 | 1 | yes (1 is coprime to everything) |
| 6, 10, 15 | 2 × 3, 2 × 5, 3 × 5 | 1 as a set | yes as a set, but not pairwise |
Set-wise vs pairwise coprime
Three or more numbers can have gcd 1 as a group while some pairs still share a factor: 6, 10, and 15 have gcd 1, yet gcd(6, 10) = 2. Such a set is relatively prime but not pairwise coprime. The calculator reports both, because the Chinese remainder theorem and many counting arguments need the stronger pairwise condition.
Euler's totient φ(n)
φ(n) counts the integers from 1 to n that are coprime to n. For a prime p, φ(p) = p - 1. In general factor n and multiply by (1 - 1/p) for each distinct prime: φ(36) = 36 × (1 - 1/2) × (1 - 1/3) = 36 × 1/2 × 2/3 = 12, and indeed 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 are the twelve numbers coprime to 36. The totient sets the size of the multiplicative group mod n and appears in Euler's theorem a^φ(n) ≡ 1 (mod n), the engine behind RSA.
How to use it
- Choose the coprime check and enter two or more whole numbers, or choose the totient mode and enter n.
- Read the verdict and the gcd; the shared prime factors line names the culprits when the numbers are not coprime.
- Open Show the work to follow the Euclidean divisions, or the φ(n) product formula step by step.
How to read the answer
A gcd of 1 means relatively prime; anything larger is the biggest shared factor and the shared primes line breaks it into primes. For three or more numbers, check the pairwise line before using results that require pairwise coprimality. In totient mode, φ(n) is the count of numbers in 1…n coprime to n; n - φ(n) share a factor with n, and φ(n) = n - 1 exactly when n is prime.
Common mistakes and edge cases
- Thinking coprime numbers must be prime. 8 and 9 are coprime and neither is prime.
- Assuming a set with gcd 1 is pairwise coprime; 6, 10, 15 is the standard counterexample.
- Stopping the Euclidean algorithm one step early; the gcd is the last non-zero remainder.
- Using φ(n) = n - 1 for composite n; that only holds for primes.
- Multiplying (1 - 1/p) once per prime power instead of once per distinct prime: 36 = 2^2 × 3^2 uses (1 - 1/2)(1 - 1/3) once each.
Worked examples
15 and 28
No shared primes: coprime.
Result
Yes, relatively prime
12 and 18
gcd 6: not coprime.
Result
No, not relatively prime
1 and 100
1 is coprime to everything.
Result
Yes, relatively prime
6, 10, 15
gcd 1 as a set but not pairwise.
Result
Yes, relatively prime
Large coprime pair
999,999,937 (prime) and 1,000,000,000.
Result
Yes, relatively prime
φ(36)
36 × 1/2 × 2/3 = 12.
Result
12
φ(97)
Prime, so 96.
Result
96
φ(1)
1 by convention.
Result
1
Only one number
Need at least two.
Result
Error
Frequently asked questions
What does relatively prime mean?+
Two integers are relatively prime (coprime) when their greatest common divisor is 1, i.e. they share no prime factor. 15 and 28 are relatively prime; 12 and 18 are not.
Do relatively prime numbers have to be prime?+
No. 8 and 9 are both composite and still coprime. Conversely, two different primes are always coprime.
How do I check if two numbers are coprime?+
Run the Euclidean algorithm: divide, take the remainder, repeat. If the last non-zero remainder is 1, they are coprime. Or factor both and look for a shared prime.
Is 1 relatively prime to every number?+
Yes, gcd(1, n) = 1 for every n, including n = 1.
What is the difference between coprime and pairwise coprime?+
A set is coprime if the gcd of all of them is 1; pairwise coprime requires every pair to have gcd 1. 6, 10, 15 is coprime but not pairwise coprime.
What is Euler's totient function?+
φ(n) is the number of integers from 1 to n that are coprime to n. φ(36) = 12, φ(97) = 96. It is computed from the prime factorization as n × Π(1 - 1/p).
Why does the lcm equal the product for coprime numbers?+
Because lcm(a, b) × gcd(a, b) = a × b, and the gcd is 1. So lcm(15, 28) = 420.
About this calculator
- Written by
- mathcheck editorial team
- Last reviewed
- September 4, 2026
Method
- Uses the values entered by the user and stable formulas documented on the page.
Related calculators
GCF Calculator
Find the greatest common factor (GCF, also called GCD or HCF) of any list of whole numbers with three worked methods: listing factors, the prime-factorization table, and Euclid's division algorithm.
LCM Calculator
Find the least common multiple (LCM) of any list of whole numbers with three worked methods: listing multiples, the prime-factorization exponent table, and lcm(a, b) = a × b ÷ gcf(a, b) using Euclid's algorithm.
Prime Factorization Calculator
Factor a positive integer into primes and show the factor tree style division steps.
Chinese Remainder Theorem Calculator
Solve systems of simultaneous congruences with the Chinese remainder theorem: checks the moduli are pairwise coprime, builds the N_i, the modular inverses, and the sum step by step, returns the smallest solution and the general solution mod N, and handles non-coprime moduli when the system is consistent.
Modular Exponentiation Calculator
Compute a^b mod n exactly for big numbers using square-and-multiply with every squaring and reduction tabulated, find a modular inverse a^-1 mod n with extended Euclid steps, or the ordinary multiplicative inverse (reciprocal) of a number.
Prime Number Calculator
Test whether a number is prime (up to 24 digits, exactly), see the trial-division or Miller–Rabin reasoning, get the prime factorization for composites, the nearest primes above and below, or list all primes in a range.
Last updated: September 4, 2026