Olympic problem on irreducible fraction

Question

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

Answer 1

Let $g = {\rm gcd}(21n + 4, 14n + 3)$. Then $g|h$ where $h = {\rm gcd}(42n + 8, 14n + 3) = {\rm gcd}(1, 14n + 3) = 1$. Hence, $g = h = 1$.

Note: this is the well-known first problem assigned at the 1st International Mathematical Olympiad (1959). You can easily find many other solutions on the internet (for instance, here).

Answer 2

Hint $\ $ If $\,d\,$ is a common factor then $\,{\rm mod}\ d\!:\ 14n+3\equiv 0\equiv 21n+4\,$ Now eliminate $\,n\,$ by noting that $\ 14/21 = \color{#c00}2/\color{#0a0}3\,$ thus $\ 0\equiv \color{#0a0}3(14n+3)-\color{#c00}2(21n+4) \equiv \color{#0a0}9-\color{#c00}8\equiv1\,\Rightarrow\, d\mid 1$.

Remark $\ $ More conceptually, put the fractions for $\,-n\,$ over the common denominator $\,42$

$$\displaystyle {\rm mod}\ d\!:\,\ \frac{3}{14}\, \equiv\, -n\,\equiv\, \frac{4}{21}\ \Rightarrow\ \frac{\color{#0a0}9}{42}\,\equiv\, \frac{\color{#c00}8}{42}$$

The fractions uniquely exist mod $\,d\,$ by $\,(14,d)=1=(21,d),\,$ so $\,14,21\,$ are invertible, viz.

$${\rm mod}\ c=(14,d)\!:\,\ 14\equiv 0\equiv\!\!\! \underbrace{14n+3}_{\large c\,\mid \,d\,\mid\,14n+3}\!\!\!\equiv 3\,\Rightarrow\,0\equiv (3,14)=1\,\Rightarrow\,c\mid 1$$