Maths Olympiad Prep

Library / /3 of 5

Number theory Difficulty 4.0 AIME Prove it Croatia

Let mm and nn be positive integers of different parity. Prove that
3m2+5mn3n2+mn \frac{3m^2 + 5mn}{3n^2 + mn}
is not a positive integer.
(Ilko Brnetić)

Solution

Let dd be the greatest common divisor of mm and nn, i.e. m=dmm = d m' and n=dnn = d n', where mm' and nn' are relatively prime positive integers of different parity.
Now we need to prove that
3d2m2+5d2mn3d2n2+dmn=m(3m+5n)n(m+3n) \frac{3d^2 m'^2 + 5d^2 m' n'}{3d^2 n'^2 + d m' n'} = \frac{m'(3m' + 5n')}{n'(m' + 3n')}
is not a positive integer.
Note that 3m+5n3m' + 5n' and m+3nm' + 3n' are both odd.
If mm' is odd and nn' is even, the even n(m+3n)n'(m' + 3n') clearly cannot divide the odd m(3m+5n)m'(3m' + 5n').
Otherwise, let the odd kk be the greatest common divisor of 3m+5n3m' + 5n' and m+3nm' + 3n'. Then we have
k3(3m+5n)5(m+3n), i.e. k4m,k1(3m+5n)3(m+3n), i.e. k4n, \begin{aligned} k &\mid 3 \cdot (3m' + 5n') - 5 \cdot (m' + 3n'), & \text{ i.e. } k &\mid 4m', \\ k &\mid 1 \cdot (3m' + 5n') - 3 \cdot (m' + 3n'), & \text{ i.e. } k &\mid -4n', \end{aligned}
from which it follows that kk divides both mm' and nn', so k=1k = 1 and both factors in
mn3m+5nm+3n \frac{m'}{n'} \cdot \frac{3m' + 5n'}{m' + 3n'}
are irreducible fractions.
Since m+3n>mm' + 3n' > m', the proof is finished.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.