RMO 2006 Problem

Given that 11 divides $a + 13b$ and 13 divides $a + 11b$ , we know that

$a + 13b \equiv 0 \pmod{11}$

and

$a + 11b \equiv 0 \pmod{13}$ .

These are equivalent to

$a + 2b \equiv 0 \pmod{11}$

and

$a - 2b \equiv 0 \pmod{13}$ .

Now, let $a + 2b = 11j$ and $a - 2b = 13k$ , where $j, k$ are non-negative integers. Because $b$ is positive, $11j$ must be bigger than $13k$ as there is a difference of $4b$ between the two equations. This means that $j > k$ .

If we add the two equations, we get

$2a = 11j + 13k$ .

Ideally we want $a$ as small as possible, which means we are looking for the smallest values of $j$ and $k$ that work. As $j$ and $k$ are integers, $11j$ and $13k$ must add to give an even number ( $2a$ ).

The smallest values of $j$ and $k$ that fit these criteria are 2 and 0 (respectively). This leads to $a$ being 11. Looking back to our equation $a -2b = 13k$ , the only non-negative value of $13k$ that is smaller than 11 is 0. This leads to $b$ being 5.5, however we know that $b$ is an integer, so this cannot be the case.

The next smallest values of $j$ and $k$ are 3 and 1. This leads to $a$ being 23.

Using these values we can try to find $b$ by subtracting the two equations instead, giving

$4b = 11j - 13k$ .

If we substitute our values in, we get

$4b = 11 \cdot 3 - 13 \cdot 1 = 20$

$b = 5$

$b$ is an integer! It works!

Therefore

$a + b = 23 + 5 = 28$

This is my first time using latex (and writing a solution!), so sorry if my write-up is a bit wonky.

(a+13b) = 0 (mod 11) and (a+11b) = 0(mod 13)

now 13 times a multiple of 11 and

11 times a multiple of 13 is divisible by 11*13 = 143.

therefore 13*(a+13b) = 0 (mod143)

and 11*(a+11b) = 0 (mod 143)

hence

13 a + 169b = 0 (mod 143)

and 11a + 121b = 0 (mod 143)

adding both gives: 24a + 290b = 0 (mod 143)

2(12a + 145b) = 0 (mod 143)

that implies

12a + 145b = 0(mod 143)

(12a + 2b) + 143b = 0 (mod 143)

that implies

12a + 2b = 0 (mod 143)

2(6a+b) = 0 (mod 143)

hence a = 143/6 = 23

and b = 143 - 23*6 = 5.

a+b = 28.

$a+13b≡a+2b≡0$ $(mod 11)$ .

Multiplying by $6$ , $6a+12b≡0$ $(mod 11)$ which further implies $6a+b≡0$ $(mod 11)$ .

Again, $a+11b≡a-2b≡0$ $(mod 13)$

Multiplying by $6$ , $6a-12b≡0$ $(mod 13)$ which implies $6a+b≡0$ $(mod 13)$ .

Since $gcd(11,13)=1$ ,therefore $143$ divides $6a+b$ .

So we can write, $6a+b=143k$ , or $6a+6b=143k+5b=114k+6b-(k+b)$

Hence, $6$ divides $k+b$ and so, $k+b≥6$

Now, $6(a+b)=143k+5b=138+5(k+b)≥138+30=168$

Hence, $a+b≥28$

Taking, $a=23$ and $b=5$ , one can see the conditions of the pronlem are satisfied.

So,the minimum value of $a+b$ is $28$

$11 \mid a+13b \implies 11 \mid (a+13b)+11b \implies \color{#D61F06}{11 \mid a+24b}$

$13 \mid a+11b \implies 13 \mid (a+11b)+13b \implies \color{#D61F06}{13 \mid a+24b}$

Since $a+24b$ is a multiple of $11$ and $13$ and these numbers are coprime, it follows that $a+24b$ is a multiple of $11 \times 13 = 143$

Since we want the least possible value of $a+b$ , we need to set $a+24b = 143$ and maximize $b$

Under these conditions, $a = 23$ and $b = 5$ , so $a+b = \boxed{28}$

$a+13b \equiv 0 \pmod{11} \Rightarrow a+2b \equiv 0 \pmod{11}$

$a+11b \equiv 0 \pmod{13} \Rightarrow a-2b \equiv 0 \pmod{13}$

$a-2b=13x$

Let $x=1$ (For the smallest value of a+b)

$17-4=13 \Rightarrow 17+4=21 \equiv -1 \pmod{11}$

$19-6=13 \Rightarrow 19+6=25 \equiv 3 \pmod{11}$

$21-8=13 \Rightarrow 21+8=29 \equiv 7 \pmod{11}$

$23-10=13 \Rightarrow 23+10=33 \equiv 0 \pmod{11}$

$so, b=10/2=5$

$Hence (a,b)=(23,5) \Rightarrow a+b= \boxed{28}$