"No Common Factor" in a Problem? Reach for Euclidean Algorithm or Coprimality

Read enough number theory problems and a specific phrase starts jumping off the page: "share no common factor" — or any cousin of it, like "are in lowest terms", "are relatively prime", "have no factor besides 1 in common", "are coprime". Every time that phrase appears, the same small toolkit solves the problem. You either run the Euclidean algorithm to check (or compute) the \gcd, or you invoke a coprimality property — usually Euclid's lemma, or Bezout's identity, or the fact that coprime factors can be separated. Mastering that mapping — from wording to tool — saves you from staring blankly at problems that look hard but aren't.

The cue and what it really says

When a problem says a and b share no common factor, mathematically it means

\gcd(a, b) = 1.

That single equation is the cue. Everything that follows in the problem — irreducible fractions, unique factorisations, divisors cleanly splitting — is downstream of \gcd(a, b) = 1. Writing the condition in this form is step one. Then you reach for one of three tools.

Tool 1: The Euclidean algorithm

Use this when the problem asks you to verify or compute whether two numbers share a factor. The Euclidean algorithm computes \gcd(a, b) in a handful of division steps, never touching prime factorisations. That matters for two reasons: it is fast even on numbers too big to factor, and the chain of remainders it produces is what proves Bezout's identity — that the \gcd can be written as ax + by for integers x, y.

Sample cues that point to the Euclidean algorithm:

"Show that 2n+1 and 3n+1 share no common factor for every positive integer n."
"Find the GCD of 462 and 1071."
"Prove that consecutive Fibonacci numbers are coprime."

In each case you write the division steps and read the last non-zero remainder. For the first:

\gcd(3n+1, 2n+1) = \gcd(2n+1, n) = \gcd(n, 1) = 1.

Why: 3n+1 = 1 \cdot (2n+1) + n, so the remainder is n. Then 2n+1 = 2 \cdot n + 1, remainder 1. And n = n \cdot 1 + 0. Last non-zero remainder is 1, so the GCD is 1.

Done. No prime factorisation of 2n+1 or 3n+1 required — the algorithm bypasses all of that.

Tool 2: Euclid's lemma and its corollaries

Use this when the problem gives you that two numbers are already coprime and wants you to conclude something about divisibility. The workhorse is Euclid's lemma:

\text{if } \gcd(a, b) = 1 \text{ and } a \mid bc, \text{ then } a \mid c.

In plain English: if a shares nothing with b, then any factor of a that appears in the product bc must have come from c, not b.

Sample cues:

"Given \gcd(p, q) = 1 and q \mid p^2 r, show q \mid r."
"Prove that if a prime p divides the product ab, then p \mid a or p \mid b."
"If \gcd(a, b) = 1, show that \gcd(a, b^k) = 1 for every k."

Each of these is a one-line Euclid's-lemma application. For the last:

Why: repeated use. \gcd(a, b) = 1 gives \gcd(a, b^2) = 1 by induction: any prime dividing both a and b^2 must — by the lemma — divide b, contradicting \gcd(a, b) = 1.

Tool 3: Bezout's identity

Use this when the cue includes coprimality and you need to produce a witness — that is, explicit integers x, y — or when you need to reason about linear combinations of a and b.

Bezout's identity: for any integers a, b with \gcd(a, b) = d, there exist integers x, y such that

ax + by = d.

In particular, \gcd(a, b) = 1 if and only if there exist x, y with ax + by = 1.

Sample cues that signal Bezout:

"Show that the fraction (n+1)/n is already in lowest terms."
"Find integers x, y such that 15x + 22y = 1."
"Prove that if \gcd(a, n) = 1, then a has a multiplicative inverse modulo n."

That last one is the foundation of modular inverses. Because ax + ny = 1, taking both sides mod n gives ax \equiv 1 \pmod{n} — so x is the inverse of a.

Deciding between the three tools

Here is the decision flow most fluent solvers run in their head:

Drag the slider across the four prompts. The three tools — the Euclidean algorithm, Euclid's lemma, and Bezout's identity — each attach to a different kind of question the problem is really asking. The cue in the problem statement tells you which to reach for first.

A worked example where recognition saves time

Problem: Show that $\dfrac{21n + 4}{14n + 3}$ is in lowest terms for every positive integer $n$

This is a famous problem (IMO 1959, Problem 1). In lowest terms means \gcd(21n+4, 14n+3) = 1 — the cue. Compute.

\gcd(21n+4, 14n+3)

= \gcd(14n + 3, \; 7n + 1)

Why: 21n + 4 = 1 \cdot (14n + 3) + (7n + 1).

= \gcd(7n + 1, \; 1)

Why: 14n + 3 = 2 \cdot (7n + 1) + 1.

= 1.

Done in three lines. Without the Euclidean reflex, students often try plugging in n = 1, 2, 3, \ldots and factor by hand, which is slow and doesn't prove anything for all n. With the reflex, the problem is mechanical.

What if the problem does not use the exact phrase?

The cue hides behind several disguises:

"a and b are relatively prime" — identical meaning.
"The fraction a/b is irreducible" or in lowest terms — means \gcd(a, b) = 1.
"a divides bc but not c" — often inviting an Euclid's lemma argument about what \gcd(a, b) must be.
"Prove that for every prime p dividing a, p \nmid b" — that is the primal definition of \gcd(a, b) = 1.

Train yourself to translate each of these to \gcd = 1 immediately. Once translated, the three tools above cover nearly every follow-up step.

What to not do

When you see "no common factor", resist two temptations:

Don't start factoring into primes. Often the numbers (like 21n + 4) depend on a parameter, and prime factorisation is either impossible or wildly case-heavy. The Euclidean algorithm works on the algebraic expressions directly.
Don't check small cases and declare victory. \gcd(21 \cdot 1 + 4, 14 \cdot 1 + 3) = \gcd(25, 17) = 1 is one data point. You need the Euclidean reduction to cover all n.

The one-line mental trigger

See "share no common factor" (or any synonym)? Write down \gcd(a, b) = 1. Then ask: am I computing it, using it, or producing a witness? Euclidean algorithm, Euclid's lemma, or Bezout — one of the three will finish the problem.