Coprime — Definition, Formula & Examples

Coprime (also called relatively prime) describes two integers whose only shared positive factor is 1. For example, 8 and 15 are coprime because no integer greater than 1 divides both of them.

Two integers $a$ and $b$ are coprime if and only if $\gcd(a, b) = 1$ , where $\gcd$ denotes the greatest common divisor.

Key Formula

\gcd(a,\, b) = 1

Where:

$a, b$ = Two integers being tested
$\gcd$ = Greatest common divisor function

How It Works

To check whether two numbers are coprime, find their greatest common factor (GCF). If the GCF is 1, they are coprime; if it is anything larger, they are not. You can find the GCF by listing factors, using prime factorization, or applying the Euclidean algorithm. Note that the numbers themselves do not need to be prime — 8 and 15 are both composite, yet they are coprime.

Worked Example

Problem: Determine whether 35 and 24 are coprime.

Step 1: Find the prime factorization of each number.

35 = 5 \times 7, \quad 24 = 2^3 \times 3

Step 2: Identify any shared prime factors. The primes of 35 are 5 and 7; the primes of 24 are 2 and 3. There is no overlap.

Step 3: Since the two factorizations share no prime factors, their GCF is 1.

\gcd(35,\, 24) = 1

Answer: Yes, 35 and 24 are coprime.

Why It Matters

Coprimality is central to simplifying fractions: a fraction

\frac{a}{b}

is already in lowest terms exactly when

a

and

b

are coprime. It also underpins modular arithmetic and RSA encryption, where choosing coprime numbers is a required step in generating secure keys.

Common Mistakes

Mistake: Assuming both numbers must be prime for them to be coprime.

Correction: Coprime refers to the relationship between two numbers, not to the numbers individually. Two composite numbers like 8 and 15 can be coprime because they share no common factor other than 1.