Maths Olympiad Prep

Library / /32 of 44

Number theory Difficulty 6.0 National Olympiad Prove it Slovenia

Find all pairs of positive integers (m,n)(m, n), such that
m+3n5=2v11d. m + 3n - 5 = 2v - 11d.
Here vv is the least common multiple of the numbers mm and nn, and dd is the greatest common divisor of mm and nn.

Solution

Let us write m=dam = d a and n=dbn = d b. Here aa and bb are relatively prime integers and v=dabv = d a b. Plugging this into the given equation we get da+3db5=2dab11dd a + 3 d b - 5 = 2 d a b - 11 d, so

da+3db5=2dab11d d a + 3 d b - 5 = 2 d a b - 11 d

which rearranges to

da+3db2dab+11d=5 d a + 3 d b - 2 d a b + 11 d = 5

or

d(a+3b2ab+11)=5 d(a + 3b - 2ab + 11) = 5

Since dd is a positive integer, dd must divide 55. Thus, d=1d = 1 or d=5d = 5.

First, let us assume that d=1d = 1. Then the equation can be rearranged into

a+3b5=2ab11 a + 3b - 5 = 2ab - 11

or

a+3b+6=2ab11+6+5=2ab a + 3b + 6 = 2ab - 11 + 6 + 5 = 2ab

so

a+3b+6=2ab a + 3b + 6 = 2ab

or

2aba3b6=0 2ab - a - 3b - 6 = 0

or

a(2b1)=3b+6 a(2b - 1) = 3b + 6

From here we conclude that 2b12b - 1 divides 3b+63b + 6, so it must also divide 2(3b+6)3(2b1)=6b+126b+3=152(3b + 6) - 3(2b - 1) = 6b + 12 - 6b + 3 = 15.

Since 2b12b - 1 is a positive integer there are four possibilities:

- If 2b1=12b - 1 = 1, then b=1b = 1 and a=9a = 9.
- If 2b1=32b - 1 = 3, then b=2b = 2 and a=4a = 4, which leads to a contradiction, since aa and bb should be relatively prime.
- If 2b1=52b - 1 = 5, then b=3b = 3 and a=3a = 3, which is again a contradiction.
- If 2b1=152b - 1 = 15, then b=8b = 8 and a=2a = 2, and once more this is not possible.

Hence, in this case we only have one solution, (9,1)(9, 1).

Now, assume that d=5d = 5. Then we can divide the equation by 55 and rearrange it to get

a+3b1=2ab11 a + 3b - 1 = 2ab - 11

or

a+3b+10=2ab a + 3b + 10 = 2ab

so

a(2b1)=3b+10 a(2b - 1) = 3b + 10

This implies that 2b12b - 1 divides 3b+103b + 10, so it must also divide 2(3b+10)3(2b1)=6b+206b+3=232(3b + 10) - 3(2b - 1) = 6b + 20 - 6b + 3 = 23.

There are two possibilities:

- If 2b1=12b - 1 = 1, then b=1b = 1 and a=13a = 13.
- If 2b1=232b - 1 = 23, then b=12b = 12 and a=2a = 2, a contradiction once more.

In this case we get the solution (65,5)(65, 5).

Therefore, the solutions are (m,n)=(9,1)(m, n) = (9, 1) and (65,5)(65, 5).

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 reproduced verbatim; metadata (topic, difficulty) added by this project.