# Find minimum of $a+b$ if $13|a+11b$ and $11|a+13b$

Find minimum of $a+b$ if $13|a+11b$ and $11|a+13b$ where $a,b>0$.

My attempt :

$13|a+11b \implies 13|a+24b$ . Similarly we get $11|a+24b$. Now $\gcd(11,13)=1$, so, $143|a+24b$.

Therefore $a+24b \geq 143$.

How to proceed after this?

• a+b=78c-55d,c=3,d=4,get min 14 – chenbai Dec 11 '14 at 8:45
• Consider following two linear congruences, $$a+11b\equiv 0\mod13$$ $$a+13b\equiv 0\mod11$$ of two variables. – Bumblebee Dec 11 '14 at 12:20

Here's a brute force approach: start with $a+11b=13k$ and $a+13b=11m$, with $k,m\in \mathbb N$. Solve it in $a,b$ and you get:

• $a=84.5k-60.5m$
• $b=-6.5k+5.5m$
• $a+b=78k-55m$

So $a$ and $b$ are integers iff $k$ and $m$ are both odd or both even; in this subspace for $(k,m)$, just minimize $78k-55m$.

• Thanks for the gratuitous downvote... I'd say the answer is $28$. – Alexandre Halm Dec 11 '14 at 7:53

It's 28. a+24b=n for all n has solutions since gcd(1,24)=1.Thus,a+24b=143z for all z has solutions in integers. For non- positive z obviously the equation cannot have solution in postive integers.Thus z is positive. For z=1,selecting the largest b such that 24b<143 we have b=5 and thus 23 + 24(5)= 143.For z>=5 we have 1+24(27)< 143(5)=715. Thus all equations where z>=5 have solutions such that a+b>28.

When 1

• why are we only considering the case when z=1 ? – Soham Dec 11 '14 at 9:56
• For 1<z<5 one can easily see a+b>28. As for z>=5 I have shown that a+b>28 – Murtaza Wani Dec 11 '14 at 9:58