How is the Euclidean Algorithm used to solve IMO 1959 Problem 1?

Question

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

I understand that it can be solved using the Euclidean Algorithm, but how would the solution look like? I know the Euclidean Algorithm, but don't understand how it is applied here.

Answer 1

The euclidean algorithm works just as usual. We have $$ \gcd(21n+4,14n+3)\\ =\gcd(21n+4-(14n+3),14n+3)\\ =\gcd(7n+1,14n+3)\\ =\gcd(7n+1,14n+3-2(7n+1))\\ =\gcd(7n+1,1)=1 $$

Answer 2

HINT:

If integer $d$ divides $21n+4,14n+3$

$d$ must divide $3(14n+3)-2(21n+4)=1$

The basic idea was to eliminate $n$ and find a constant that must be divisible by $d$

Answer 3

By the Euclidean algorithm,$$21n+4 = 1(14n + 3) + (7n + 1)$$ Now the $GCD$ of $(21n+4)$ & $(14n + 3)$ is the same as that of $(14n + 3)$ & $(7n + 1)$.
So applying the algorithm to $(14n + 3)$ & $(7n + 1)$, $$(14n + 3) = 2(7n+1) + 1$$ By the same logic, the $GCD$ of $(14n + 3)$ & $(7n + 1)$ is equal to that of $(7n + 1)$ & $1$. Hence we finally have the $GCD$ of $(21n+4)$ & $(14n + 3)$ $=1$.
Since the $GCD$ of the numerator and denominator is 1, therefore, the fraction is irreducible.

Answer 4

$${21n+4\over 14n+3}={14n +3 +7n+1\over 14n+3}=1 +{7n+1\over 14n+3}= 1 +{14n+2\over 2(14n+3)}$$

$$\gcd(14n+2,14n+3) = 1$$ thus irreducible.