Results 1 to 4 of 4

Thread: Linear Diophantine equation

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    19

    Linear Diophantine equation

    I require help with the below problem

    Suppose I have an unlimited supply of 2p and 5p coins. By considering the linear Diophantine equation 2x + 5y = n show that all amounts n>N=4 are obtainable.

    How do reconile the fact that 3p is unobtainable even though the equation 2x + 5y = 3 has infinitely many solutions?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let's generalise it. Suppose we have 2 positive integers $\displaystyle a,b$ such that $\displaystyle (a,b)=1$

    We'll show that if $\displaystyle n\geq{(a-1)\cdot{(b-1)}}$ then $\displaystyle a\cdot{x}+b\cdot{y}=n$ has solutions with $\displaystyle x,y$ nonnegative integers.

    If $\displaystyle x,y$ are integers ( positive, negative or 0), then the equation: $\displaystyle ax+by=n$ always has solutions. Indeed, by just considering $\displaystyle n\equiv{b\cdot{y}}(\bmod.a)$ there are solutions. ( multiply by the modular inverse of b)

    Now suppose $\displaystyle 0\leq{y}<a$, we'll show that, with that restriction, the solution to $\displaystyle ax+by=n$ is unique. ( It exists and is unique)

    Suppose $\displaystyle ax+by=a\cdot{x'}+b\cdot{y'}=n$ then $\displaystyle a\cdot{(x-x')}=b\cdot{(y'-y)}$ however $\displaystyle -a<y'-y<a$ and $\displaystyle (a,b)=1$ so if $\displaystyle b\cdot{(y'-y)}$ is multiple of $\displaystyle a$ ( as it is), it must be $\displaystyle y'-y=0$ thus $\displaystyle y'=y$ and from there we immediately get $\displaystyle x=x'$ so the solution is unique. For the existence just consider $\displaystyle n\equiv{-by}(\bmod.a)$, since we can find $\displaystyle 0\leq{y}<a$ satisfying that condition.

    Now suppose again we only had the restriction $\displaystyle 0\leq{y}<a$, we know that in this case the solution for integers $\displaystyle x,y$ is unique. If $\displaystyle n\geq{(a-1)\cdot{(b-1)}}$ then $\displaystyle x$ must be greater than $\displaystyle -1$ Indeed, suppose it wasn't, then we have $\displaystyle n\leq{-a+b\cdot{y}}\leq (-a+b\cdot{(a-1)})=(b-1)\cdot{(a-1)}-1$ ABSURD!

    So we have found that if $\displaystyle n\geq{(a-1)\cdot{(b-1)}}$ there's a solution in the nonnegative integers!

    Now note that $\displaystyle (a-1)\cdot{(b-1)}-1=a\cdot{(-1)}+b\cdot{(a-1)}$, so, by the unique of the representation if $\displaystyle 0\leq{y}<a$ and x, y are integers, it follows that, if $\displaystyle n=(a-1)\cdot{(b-1)}-1$ there can be no solution in the positive integers.

    So the smallest integer $\displaystyle m$ such that for all $\displaystyle n\geq{m}$, $\displaystyle n=a\cdot{x}+b\cdot{y}$ has a solution for nonnegative integers $\displaystyle x,y$ is $\displaystyle m=(a-1)\cdot{(b-1)}$
    Last edited by PaulRS; Jan 1st 2009 at 04:11 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    19
    Sorry I got lost going through your response.

    Where does the equation below come from?

    ax + by = ax' + by' = n
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by LL_5 View Post
    Sorry I got lost going through your response.

    Where does the equation below come from?

    ax + by = ax' + by' = n
    I am showing that if $\displaystyle x,y,x',y'$ are integers and they satisfy: $\displaystyle a\cdot{x}+b\cdot{y}=a\cdot{x'}+b\cdot{y'}=n$ ( both with the condition $\displaystyle 0\leq y,y'<a$ ) then $\displaystyle (x',y')=(x,y)$ so they are the same solution, that is there's only one solution (if it exists, which I explained in the response) satisfying the given restrictions
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Positive Solutions to Linear Diophantine Equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Aug 3rd 2010, 11:22 PM
  2. Replies: 1
    Last Post: Mar 17th 2010, 01:43 PM
  3. Question with linear Diophantine equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 18th 2010, 06:40 PM
  4. Linear Diophantine Equation question
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 18th 2010, 05:45 PM
  5. linear diophantine equ.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 27th 2009, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum