Exploring Number Theory: Understand Euclidean Algorithm with IMO 1959 Problem 1

Number Theory is one of the most fascinating and ancient branches of mathematics. In this post, we'll delve into a classic problem from the International Mathematical Olympiad (IMO) 1959, exploring fundamental concepts such as divisibility, greatest common divisors (gcd), and the Euclidean algorithm. This will serve as a strong foundation for understanding more advanced topics in Number Theory.

The Problem: Prove Irreducibility of a Fraction

The problem asks us to prove that the fraction:

$\frac{21 n+4}{14 n+3}$

is irreducible for every natural number $n$. In other words, we need to show that the greatest common divisor (gcd) of the numerator $21 n+4$ and the denominator $14 n+3$ is always 1, meaning these two terms share no common factors for any natural number $n$.

What Does "Irreducible" Mean?

A fraction is irreducible if its numerator and denominator share no common factors other than 1. For example, the fraction $\frac{10}{14}$ is reducible because both 10 and 14 share the factor 2. After dividing both by their gcd (2), we get $\frac{5}{7}$, which is the irreducible form of $\frac{10}{14}$.
In this problem, we're asked to show that no matter which $n$ is chosen, the fraction $\frac{21 n+4}{14 n+3}$ cannot be reduced, meaning the gcd of $21 n+4$ and $14 n+3$ is 1 for all $n$.

Watch the Video

Key Idea: GCD and the Euclidean Algorithm

To solve this, we can use the Euclidean algorithm, a systematic method for finding the gcd of two numbers by repeatedly applying the division lemma. Let's walk through the key steps to understand the solution.

Step 1: Division Lemma

The division lemma states that for any two integers $a$ and $b$, there exist integers $q$ and $r$ such that:

$$
b=a q+r
$$

where $r$ is the remainder when $b$ is divided by $a$. This allows us to express any number as a multiple of another, plus a remainder.

Step 2: Applying the Euclidean Algorithm

We want to compute the gcd of $21 n+4$ and $14 n+3$ by performing successive subtractions, which is at the heart of the Euclidean algorithm.

First, compute the difference between the numerator and the denominator:

$$
(21 n+4)-(14 n+3)=7 n+1
$$

So, we now need to find the gcd of $14 n+3$ and $7 n+1$. Applying the Euclidean algorithm again:

$$
(14 n+3)-2(7 n+1)=1
$$

Now, we see that the gcd of $7 n+1$ and 1 is clearly 1 . Hence, the gcd of $21 n+4$ and $14 n+3$ is also 1 . This confirms that the fraction is irreducible for any $n$.

Why This Problem Matters

This problem provides a beautiful introduction to Number Theory by illustrating how simple concepts like gcd, divisibility, and the Euclidean algorithm can be used to solve complex problems. It opens the door to deeper explorations into prime numbers, modular arithmetic, and advanced number-theoretic functions.

The Power of Number Theory

The IMO 1959 problem showcases the elegance and depth of Number Theory. By understanding the fundamental ideas of gcd and using the Euclidean algorithm, we can solve challenging problems and gain a deeper appreciation for the mathematical structures that govern numbers.

For those interested in diving deeper, there are excellent resources and courses available online to further explore Number Theory. Whether you're preparing for mathematical competitions or simply want to expand your knowledge, mastering these basic ideas will provide a strong foundation for future mathematical adventures.