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?

  • $\begingroup$ a+b=78c-55d,c=3,d=4,get min 14 $\endgroup$ – chenbai Dec 11 '14 at 8:45
  • $\begingroup$ Consider following two linear congruences, $$a+11b\equiv 0\mod13$$ $$a+13b\equiv 0\mod11$$ of two variables. $\endgroup$ – 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$.

  • 1
    $\begingroup$ Thanks for the gratuitous downvote... I'd say the answer is $28$. $\endgroup$ – 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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.