Relatively Prime
Check if two numbers are relatively prime using GCD. Free number theory calculator tells if a pair of integers shares only 1 as their common factor instantly.
About This Calculator
The Relatively Prime Calculator is a free online tool for students, teachers, and math enthusiasts to determine whether two positive integers are relatively prime (also called coprime or mutually prime). Two numbers are relatively prime when the only positive integer that divides both is 1, meaning their greatest common divisor (GCD) is 1. For example, 14 and 15 are relatively prime even though neither number is prime -- 14's factors are 1, 2, 7, 14 while 15's factors are 1, 3, 5, 15, and the only shared factor is 1.
This calculator uses the Euclidean algorithm, one of the oldest and most efficient methods for computing the GCD of two integers. The algorithm repeatedly applies the division algorithm: given two numbers a and b, compute a mod b, then replace a with b and b with the remainder, continuing until b becomes 0. At that point, a is the GCD. If the final GCD is 1, the numbers are relatively prime. This approach works for any pair of positive integers and produces results instantly.
The concept of coprime numbers is fundamental in number theory and has wide-ranging applications in cryptography (particularly RSA encryption where two large primes are multiplied and their coprimality with a chosen exponent ensures secure encryption), modular arithmetic, and abstract algebra. Understanding whether numbers are relatively prime helps students grasp deeper concepts in mathematics including the Chinese Remainder Theorem, Euler's totient function, and the structure of the integers modulo n.
Regional Notes
India (IN): Coprime numbers appear in the NCERT mathematics curriculum for Classes 6-10, typically introduced alongside prime factorization and HCF/LCM concepts. Students learn to check coprimality by comparing prime factor lists.
United States (US): The concept of relatively prime numbers is taught in middle school and high school math under the CCSS standards, often in the context of simplifying fractions and number theory. The term "coprime" is commonly used in competition math (AMC, AIME) and algebra courses.
United Kingdom (UK): The UK national curriculum covers co-prime numbers at Key Stage 3 and 4, where students learn to identify pairs of co-prime numbers and use prime factor decomposition. GCSE and A-Level exam boards frequently include coprime identification in number theory questions.
Frequently Asked Questions
What does it mean for two numbers to be relatively prime?
Two numbers are relatively prime (or coprime) when their greatest common divisor (GCD) is 1. This means they share no common prime factors other than 1. For example, 14 and 15 are relatively prime because their GCD is 1, even though neither number is prime itself.
How does the Relatively Prime Calculator work?
Enter two positive integers into the calculator. It computes the greatest common divisor (GCD) using the Euclidean algorithm. If the GCD equals 1, the numbers are relatively prime (coprime). If the GCD is greater than 1, they share a common factor and are not relatively prime.
Can two even numbers be relatively prime?
No, two even numbers cannot be relatively prime because they both share 2 as a common factor. Their GCD will always be at least 2, meaning they cannot be coprime. At least one of the numbers in a pair must be odd for them to be relatively prime.
Is 1 relatively prime to every number?
Yes, 1 is relatively prime to every integer. This is because the only positive divisor of 1 is 1 itself, so the GCD of 1 and any other number is always 1. This makes 1 coprime with all natural numbers.
What is the difference between pairwise coprime and setwise coprime?
A set of numbers is setwise coprime if the GCD of all numbers together is 1. A set is pairwise coprime if every pair of numbers within the set is coprime. For example, 21 is setwise coprime (GCD of all three is 1) but not pairwise coprime because 4 and 6 share factor 2.
Is this relatively prime calculator free to use?
Yes, all calculators on Calculy are completely free to use. There are no hidden fees, subscriptions, or usage limits. Simply enter your numbers and get instant results.
Can relatively prime numbers be negative?
The concept of relatively prime numbers typically applies to positive integers. However, in number theory, the definition can extend to negative integers as well. The GCD computation uses absolute values, so if |a| and |b| are coprime, then a and b are considered coprime regardless of sign.
What are some real-world applications of relatively prime numbers?
Relatively prime numbers have important applications in cryptography (RSA encryption relies on coprime numbers), modular arithmetic, music theory (frequency ratios), gear design (ensuring even wear), and computer science (hash functions and pseudorandom number generators).