Introduction

Two integers are co-prime if their greatest common divisor is 1. The efficient way to check that is not to list all factors, but to compute the GCD directly with the Euclidean algorithm and compare the result to 1.

Use the Euclidean Algorithm

The Euclidean algorithm is the standard solution because it reduces the problem quickly using repeated remainder operations. Instead of checking every possible divisor, it repeatedly replaces the pair (a, b) with (b, a % b) until the second value becomes zero.

If the final non-zero value is 1, the numbers are relatively prime.

For example, check 35 and 64:

• '64 % 35 = 29'
• '35 % 29 = 6'
• '29 % 6 = 5'
• '6 % 5 = 1'
• '5 % 1 = 0'

The last non-zero value is 1, so 35 and 64 are co-prime.

This method is efficient because the numbers shrink fast. Its running time is logarithmic in practice and in theory, which is far better than trial division over a large range.

A Simple Python Implementation

You can implement the algorithm in a few lines:

1def are_coprime(a: int, b: int) -> bool:
2    a = abs(a)
3    b = abs(b)
4
5    while b != 0:
6        a, b = b, a % b
7
8    return a == 1
9
10
11print(are_coprime(35, 64))
12print(are_coprime(21, 14))

This works for positive or negative integers because the sign does not affect common divisors. Taking the absolute value up front keeps the logic clear.

In real Python code, the built-in math.gcd is even simpler:

1import math
2
3def are_coprime(a: int, b: int) -> bool:
4    return math.gcd(a, b) == 1
5
6
7print(are_coprime(14, 25))
8print(are_coprime(14, 21))

If your goal is just correctness and clarity, math.gcd is the best default.

Why Factorization Is Usually the Wrong Tool

A common beginner approach is to factor both numbers and compare the factor lists. That can work for small integers, but it is more work than necessary and gets expensive quickly.

For example, factorization forces you to answer questions you do not actually need. To decide whether two numbers are co-prime, you do not need every prime factor. You only need to know whether the final GCD is 1.

That is why the Euclidean algorithm appears in cryptography, modular arithmetic, and competitive programming. It gives the exact answer with minimal extra work.

Extended Cases and Shortcuts

A few observations are useful in practice:

• consecutive integers are always co-prime
• if both numbers are even, they are not co-prime
• if math.gcd(a, b) > 1, they share a factor and the check is finished

You can also use the GCD result for more than a boolean answer. If the numbers are not relatively prime, the GCD tells you the largest divisor they share.

1import math
2
3a = 84
4b = 30
5g = math.gcd(a, b)
6
7if g == 1:
8    print("co-prime")
9else:
10    print(f"not co-prime, gcd = {g}")

That is often useful for debugging numeric algorithms or simplifying fractions.

Common Pitfalls

The most common mistake is trying every divisor from 2 up to the smaller number. That works, but it is unnecessarily slow for large inputs.

Another issue is forgetting edge cases. For example, 0 is not co-prime with most numbers because gcd(0, n) is |n|, not 1. Also, 1 is co-prime with every integer except 0 if you follow the standard GCD-based definition carefully.

Negative inputs also confuse some implementations. Common divisors are usually discussed for positive integers, but code should normalize signs so the result is stable.

Finally, do not confuse co-prime with prime. Two numbers can be composite and still be relatively prime. For example, 8 and 15 are not prime numbers, but they are co-prime because their GCD is 1.

Summary

• Two integers are co-prime when their GCD is 1.
• The Euclidean algorithm is the efficient standard way to check that.
• In Python, math.gcd(a, b) == 1 is the clearest solution.
• Factorization is usually unnecessary and slower.
• Handle edge cases such as 0, negative values, and the difference between prime and co-prime.