Results 1 to 3 of 3

Thread: Least possible value of a+b

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,115
    Thanks
    7

    Least possible value of a+b

    Find the least pssible value of $\displaystyle a + b$, where $\displaystyle a, b$ are positive integers such that $\displaystyle 11$ divides $\displaystyle a + 13b$ and $\displaystyle 13$ divides $\displaystyle a + 11b$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10
    Quote Originally Posted by alexmahone View Post
    Find the least possible value of $\displaystyle a + b$, where $\displaystyle a, b$ are positive integers such that $\displaystyle 11$ divides $\displaystyle a + 13b$ and $\displaystyle 13$ divides $\displaystyle a + 11b$.
    I make the answer 28 (a=23, b=5), but I don't have a neat argument to prove that it's minimal.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Opalg View Post
    I make the answer 28 (a=23, b=5), but I don't have a neat argument to prove that it's minimal.
    here's a proof:

    $\displaystyle a+13b \equiv 0 \mod 11$ and $\displaystyle a+11b \equiv 0 \mod 13$ are equivalent to say that $\displaystyle a+2b=11k$ and $\displaystyle a-2b=13 \ell,$ for some integers $\displaystyle k, \ell.$ clearly we must have: $\displaystyle k > 0.$ we also get:

    $\displaystyle 2a=11k + 13 \ell, \ \ 4b=11k - 13 \ell \equiv -k - \ell \mod 4 .$ so: $\displaystyle k + \ell = 4m.$ hence: $\displaystyle \ell=4m - k,$ which gives us: $\displaystyle a=26m - k, \ b=6k - 13m.$ clearly $\displaystyle a>0, \ k > 0,$ implies $\displaystyle m > 0.$

    if $\displaystyle m \geq 2,$ then since $\displaystyle b > 0,$ we will have: $\displaystyle k > \frac{13m}{6} > 4.$ thus: $\displaystyle a+b=13m + 5k > 13 \times 2 + 5 \times 4=46 > 28.$

    if $\displaystyle m=1,$ then $\displaystyle a+b=5k+13.$ also from $\displaystyle b > 0,$ we get: $\displaystyle k > \frac{13}{6} > 2.$ thus the minimum possible value of $\displaystyle k$ is $\displaystyle 3.$ therefore: $\displaystyle a=26 - k = 23, \ b = 6k - 13 = 5, \ a+b=28. \ \ \ \Box$
    Last edited by NonCommAlg; Oct 18th 2008 at 10:51 PM.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum