# Thread: Linear Diophantine equation

1. ## 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?

2. 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}, 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 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} satisfying that condition.

Now suppose again we only had the restriction $0\leq{y}, 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} 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)}$

3. Sorry I got lost going through your response.

Where does the equation below come from?

ax + by = ax' + by' = n

4. Originally Posted by LL_5
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' ) 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