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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Advertisements

About benvitalis

math grad - Interest: Number theory
This entry was posted in Number Puzzles and tagged . Bookmark the permalink.

2 Responses to Divisibility: 11|(a + 13b) and 13|(a + 11b)

  1. Paul says:

    The lowest value is 28, when a = 23 and b = 5

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s