Results 1 to 4 of 4

Math Help - 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 a,b such that (a,b)=1

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

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

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

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

    Now suppose again we only had the restriction 0\leq{y}<a, we know that in this case the solution for integers x,y is unique. If n\geq{(a-1)\cdot{(b-1)}} then x must be greater than -1 Indeed, suppose it wasn't, then we have 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 n\geq{(a-1)\cdot{(b-1)}} there's a solution in the nonnegative integers!

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

    So the smallest integer m such that for all n\geq{m}, n=a\cdot{x}+b\cdot{y} has a solution for nonnegative integers x,y is m=(a-1)\cdot{(b-1)}
    Last edited by PaulRS; January 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 x,y,x',y' are integers and they satisfy: a\cdot{x}+b\cdot{y}=a\cdot{x'}+b\cdot{y'}=n ( both with the condition 0\leq y,y'<a ) then (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: August 3rd 2010, 11:22 PM
  2. Replies: 1
    Last Post: March 17th 2010, 01:43 PM
  3. Question with linear Diophantine equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 18th 2010, 06:40 PM
  4. Linear Diophantine Equation question
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 18th 2010, 05:45 PM
  5. linear diophantine equ.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 27th 2009, 06:49 PM

Search Tags


/mathhelpforum @mathhelpforum