IMO 1959 P1

---

Problem Statement

Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

Problem Link

Solution

$$n \in \mathbb{N}$$ $$\text {RTP: } gcd(21n + 4, 14n +3) = 1$$ $$\text {From Euclidean algorithm: } gcd(a, b) = \begin{cases} a, & \text{if } b = 0 \\ gcd(b, a\mod b), & \text{otherwise} \\ \end{cases}$$ $$ = gcd(21n + 4, 14n + 3) = gcd(14n + 3, \; (21n + 4)\mod (14n + 3))$$ $$ = gcd(14n + 3, 7n + 1) = gcd(7n + 1, \; (14n + 3)\mod (7n + 1))$$ $$ = gcd(7n + 1, 1) = gcd(1, 0) = 1$$