1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – user96343
    Dec 30, 2015 at 13:38
  • $\begingroup$ @user96343 - Yep, perfect hint. Thanks! $\endgroup$
    – Alec
    Dec 30, 2015 at 14:02
  • $\begingroup$ you are welcome. $\endgroup$
    – user96343
    Dec 30, 2015 at 15:22

2 Answers 2

Reset to default
7
$\begingroup$

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$.

By the way, this is the very,very first IMO problem. (Gone are those days when problems can be solved in a giffy)

$\endgroup$
1
  • 4
    $\begingroup$ Canceling anonymous downvote. Don't see any reason for it. $\endgroup$
    – Shailesh
    Dec 30, 2015 at 13:40
5
$\begingroup$

$$\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.

$\endgroup$
1
  • $\begingroup$ Perhaps worth mentioning that you used the Euclidean algorithm. $\endgroup$
    – user236182
    Dec 30, 2015 at 18:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .