# Show that the fraction $\frac{15n+4}{10n+3}$ is irreducible for any $n \in \mathbb N$

Problem

Show that the fraction $\frac{15n+4}{10n+3}$ is irreducible for any $n \in \mathbb N$

Source

This problem was given during a national high-school (equivalent) algebra test in Norway.

My attempt

To be honest, the only thing I could think to try was to see whether the numerator minus the denominator was 1, which would have concluded the proof. Since it was not, I don't know where to go from here.

• Here's a hint. Suppose the fraction is reducible. Then surely some $d\in \mathbb{Z}$ divides both $15n+4$ and $10n+3$. Now you know that $d|a,b$ implies $d$ divides any linear combination of a and b. Can you produce a contradiction from here?
– user96343
Commented Dec 30, 2015 at 13:38
• @user96343 - Yep, perfect hint. Thanks!
– Alec
Commented Dec 30, 2015 at 14:02
• you are welcome.
– user96343
Commented Dec 30, 2015 at 15:22

We have $$3(10n+3)-2(15n+4)=1$$ Hence, the $\gcd(10n+3,15n+4)=1$ and hence the fraction is irreducible for all $n \in \mathbb{N}$.
The long way to explain is any common divisor $d$ of $10n+3$ and $15n+4$ should also divide $\alpha(10n+3) + \beta(15n+4)$ for all $\alpha, \beta \in \mathbb{Z}$. For the specific choice of $\alpha = 3$ and $\beta=-2$, we see that any common divisor $d$ has to divide $1$, which in turn means that the $\gcd(10n+3,15n+4)=1$.
$$\gcd(15n+4,10n+3)=\gcd(10n+3,5n+1)=\gcd(5n+2,5n+1)=\color{red}{1}$$ since $5n+1$ and $5n+2$ are consecutive numbers.