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 $\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)}$

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 $\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