IMO 1959 Problem 1
The fraction
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 8m04s
Problem
Prove that $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.
Exploration
The fraction
$$\frac{21n+4}{14n+3}$$
is irreducible if and only if
$$\gcd(21n+4,14n+3)=1.$$
The natural first step is to compute this greatest common divisor through the Euclidean algorithm.
Try small cases.
For $n=1$,
$$\frac{25}{17},$$
and $\gcd(25,17)=1$.
For $n=2$,
$$\frac{46}{31},$$
and $\gcd(46,31)=1$.
For $n=3$,
$$\frac{67}{45},$$
and $\gcd(67,45)=1$.
For $n=4$,
$$\frac{88}{59},$$
and $\gcd(88,59)=1$.
For $n=5$,
$$\frac{109}{73},$$
and $\gcd(109,73)=1$.
No counterexample appears in the first five cases.
A direct Euclidean algorithm gives
$$(21n+4)-(14n+3)=7n+1.$$
Then
$$(14n+3)-2(7n+1)=1.$$
This identity is striking because it expresses $1$ as an integer linear combination of the numerator and denominator:
$$1=(14n+3)-2\big((21n+4)-(14n+3)\big).$$
Expanding,
$$1=3(14n+3)-2(21n+4).$$
Hence any common divisor of $21n+4$ and $14n+3$ must divide $1$, forcing the gcd to equal $1$.
A second possible approach is contradiction: suppose a common divisor $d>1$ exists. Since $d$ divides both linear forms, it divides their difference $7n+1$, and then also
$$(14n+3)-2(7n+1)=1,$$
which is impossible. This is essentially the same argument in a cleaner form.
The only step that could hide an error is the passage from divisibility of two numbers to divisibility of their integer linear combinations. That step must be justified explicitly.
Problem Understanding
The task is to prove that for every natural number $n$, the rational number
$$\frac{21n+4}{14n+3}$$
is already in lowest terms. Equivalently, we must show that the numerator and denominator share no common divisor larger than $1$.
This is a Type B problem, because the statement to be established is fixed in advance.
The mathematical objects involved are integers and divisibility. The quantity to be proved is
$$\gcd(21n+4,14n+3)=1$$
for all natural numbers $n$.
The main difficulty is that the numerator and denominator both depend on $n$, so checking examples does not establish the general statement. A naive factorization approach does not help because neither expression factors in a useful uniform way. The decisive idea is to use the Euclidean algorithm to transform the pair into a simpler pair whose greatest common divisor is easier to identify.
Proof Architecture
The proof will use two claims.
Claim 1
For every natural number $n$,
$$\gcd(21n+4,14n+3)=\gcd(14n+3,7n+1).$$
This follows because subtracting one integer from another does not change the set of common divisors.
Claim 2
For every natural number $n$,
$$\gcd(14n+3,7n+1)=1.$$
This follows because
$$(14n+3)-2(7n+1)=1,$$
so every common divisor must divide $1$.
The more delicate step is Claim 2, because the argument relies on the precise theorem that a common divisor of two integers divides every integer linear combination of them.
Solution
We shall prove that for every natural number $n$,
$$\gcd(21n+4,14n+3)=1.$$
This is equivalent to proving that the fraction
$$\frac{21n+4}{14n+3}$$
is irreducible.
We first verify the claim for the first five values of $n$.
For $n=1$,
$$\frac{21\cdot1+4}{14\cdot1+3}=\frac{25}{17},$$
and $\gcd(25,17)=1$.
For $n=2$,
$$\frac{46}{31},$$
and $\gcd(46,31)=1$.
For $n=3$,
$$\frac{67}{45},$$
and $\gcd(67,45)=1$.
For $n=4$,
$$\frac{88}{59},$$
and $\gcd(88,59)=1$.
For $n=5$,
$$\frac{109}{73},$$
and $\gcd(109,73)=1$.
These examples suggest the general statement.
Lemma 1
For every natural number $n$,
$$\gcd(21n+4,14n+3)=\gcd(14n+3,7n+1).$$
Proof
Let
$$d=\gcd(21n+4,14n+3).$$
Since $d$ divides both $21n+4$ and $14n+3$, it also divides their difference:
$$(21n+4)-(14n+3)=7n+1.$$
Hence $d$ is a common divisor of $14n+3$ and $7n+1$.
Conversely, let
$$e=\gcd(14n+3,7n+1).$$
Since $e$ divides both $14n+3$ and $7n+1$, it divides
$$(14n+3)+(7n+1)=21n+4.$$
Hence $e$ is a common divisor of $21n+4$ and $14n+3$.
The two pairs therefore have exactly the same common divisors, so their greatest common divisors are equal:
$$\gcd(21n+4,14n+3)=\gcd(14n+3,7n+1).$$
∎
This lemma establishes that the original pair may be replaced by a simpler one; skipping the reverse divisibility argument would not justify equality of the two greatest common divisors.
Lemma 2
For every natural number $n$,
$$\gcd(14n+3,7n+1)=1.$$
Proof
Let
$$d=\gcd(14n+3,7n+1).$$
Since $d$ divides both integers, it divides every integer linear combination of them. In particular,
$$(14n+3)-2(7n+1)=1.$$
Hence $d$ divides $1$.
The only positive divisor of $1$ is $1$, so
$$d=1.$$
Therefore,
$$\gcd(14n+3,7n+1)=1.$$
∎
This lemma establishes coprimality directly from an integer linear combination equal to $1$; merely observing that the numbers are close together would not prove irreducibility.
Combining Lemma 1 and Lemma 2 gives
$$\gcd(21n+4,14n+3)=1$$
for every natural number $n$.
Hence
$$\frac{21n+4}{14n+3}$$
is irreducible for every natural number $n$.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the claim that replacing
$$21n+4$$
by
$$(21n+4)-(14n+3)=7n+1$$
does not change the greatest common divisor. Re-derive this independently. If an integer $d$ divides both original numbers, then
$$d\mid\big((21n+4)-(14n+3)\big),$$
so
$$d\mid(7n+1).$$
Conversely, if $d$ divides both
$$14n+3 \quad\text{and}\quad 7n+1,$$
then
$$d\mid\big((14n+3)+(7n+1)\big)=21n+4.$$
A careless argument might prove only one direction and incorrectly conclude equality of gcds from a containment of divisor sets.
The second delicate step is the use of the linear combination
$$(14n+3)-2(7n+1)=1.$$
Recompute:
$$14n+3-14n-2=1.$$
The arithmetic is exact. Since any common divisor divides every integer linear combination, a common divisor must divide $1$. A careless argument could incorrectly write
$$(14n+3)-2(7n+1)=0$$
through an arithmetic slip, which would destroy the proof.
The third delicate point is whether positivity matters. The gcd is defined as a positive integer, and the only positive divisor of $1$ is $1$. Hence obtaining
$$d\mid1$$
forces
$$d=1,$$
with no further cases.
Alternative Approaches
A shorter proof uses the Euclidean algorithm in one chain:
$$\gcd(21n+4,14n+3) = \gcd\big((21n+4)-(14n+3),14n+3\big) = \gcd(7n+1,14n+3).$$
Then
$$14n+3-2(7n+1)=1,$$
so
$$\gcd(7n+1,14n+3)=1.$$
This proves irreducibility immediately.
Another approach argues by contradiction. Assume a common divisor $d>1$ exists. Since
$$d\mid(21n+4) \quad\text{and}\quad d\mid(14n+3),$$
one gets
$$d\mid(7n+1).$$
Then
$$d\mid\big((14n+3)-2(7n+1)\big)=1,$$
which contradicts $d>1$. The main proof is preferable because it explicitly identifies the gcd-preserving transformation and makes the logic completely transparent.