Co-Prime Checker
Check whether two given numbers are co-prime or relatively prime using this simple checker.
Share
https://www.solvezi.com/number-theory/co-prime-checker
Check whether two given numbers are co-prime or relatively prime using this simple checker.
https://www.solvezi.com/number-theory/co-prime-checker
Two numbers are called co-prime (or relatively prime) if their Greatest Common Divisor (GCD) is 1. This means they share no common prime factors.
For example, 8 and 15 are co-prime because GCD(8, 15) = 1. However, 12 and 18 are not co-prime because GCD(12, 18) = 6.
Key insight: Co-prime numbers don't need to be prime themselves! They just need to have no common factors.
✓ Co-Prime Pairs:
(8, 15), (9, 14), (21, 22), (35, 36)
✗ Not Co-Prime:
(12, 18), (15, 25), (21, 28), (30, 45)
Most efficient way to find GCD.
Check for common prime factors.
Any two consecutive integers are co-prime.
1Euclidean Algorithm Steps:
1Euclidean Algorithm Steps:
1Euclidean Algorithm Steps:
1Euclidean Algorithm Steps:
| Property | Description | Example |
|---|---|---|
| GCD = 1 | The defining property | GCD(8, 15) = 1 |
| No common primes | Share no prime factors | 8 = 2³, 15 = 3 × 5 |
| Consecutive numbers | Always co-prime | n and n+1 |
| 1 is special | 1 is co-prime with every number | GCD(1, n) = 1 |
| Prime pairs | Two different primes | (13, 17), (19, 23) |
| Euler's totient | φ(n) counts co-primes < n | φ(8) = 4 |
Uses co-prime numbers for encryption keys
Numerator & denominator must be co-prime
Multiplicative inverses require co-prime
Co-prime step sizes hit all numbers
No! Any two even numbers share at least a factor of 2, so their GCD is at least 2.
Yes! GCD(1, n) = 1 for any positive integer n, so 1 is co-prime with everything.
Primes are numbers with exactly 2 factors. Co-prime is a relationship between two numbers that share no common factors.
Euler's totient function φ(n) counts numbers less than n that are co-prime to n. Example: φ(8) = 4 (1,3,5,7).
GCD(a, b) = 1 ⟺ a and b are co-prime
Where GCD is the Greatest Common Divisor