## Divisibility: 11|(a + 13b) and 13|(a + 11b)

Definition :

If   $a$   and   $b$   are integers (with   $a$   not zero), we say   $a$ divides   $b$

if there is an integer   $c$   such that   $b \; = \; a \, c$.

we write,   $a | b$   means     $a$ divides   $b$.

Puzzle:

$a, \; b$   are positive integers such that

$11 \; | \; a + 13 \, b$
$13 \; | \; a + 11 \, b$

Find the least possible value of   $a + b$

Solution:

Since   $13 \; | \; a + 11 \, b$
we see that   $13 \; | \; a - 2 \, b$
and hence   $13 \; | \; 6 \, a - 12 \, b$
this implies   $13 \; | \; 6 \, a + b$

Similarly,

$11 \; | \; a + 13 \, b$   $\implies$   $11 \; | \; a + 2 \, b$   $\implies$   $11 \; | \; 6 \, a + 12 \, b$   $\implies$   $11 \; | \; 6 \, a + b$

Since   $gcd \, ( \, 11, 13 \, ) \; = \; 1$

we conclude   $143 \; | \; 6 \, a + b$

Thus we may write   $6 \, a \; + \; b \; = \; 143 \, k$   for some integer   $k$

Hence,

$6 \, a \; + \; 6 \, b \; = \; 143 \, k \; + \; 5 \, b \; = \; 144 \, k \; + \; 6 \, b \; - \; (k + b)$

This shows that   $6 \; | \; k + b$   and hence   $k + b \; \geq \; 6$.

We therefore obtain

$6 \,(a + b) \; = \; 143 \,k + 5 \,b \; = \; 138 \,k + 5 \,(k + b) \; \geq \; 138 + (5\times6) \; = \; 168$

It follows   that   $a + b \; \geq \; 28$

Taking   a = 23   and   b = 5
we see that the conditions of the problem satisfied.
Thus the minimum value of   a + b   is   28