Thread: 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?

Let's generalise it. Suppose we have 2 positive integers such that

We'll show that if then has solutions with nonnegative integers.

If are integers ( positive, negative or 0), then the equation: always has solutions. Indeed, by just considering there are solutions. ( multiply by the modular inverse of b)

Now suppose , we'll show that, with that restriction, the solution to is unique. ( It exists and is unique)

Suppose then however and so if is multiple of ( as it is), it must be thus and from there we immediately get so the solution is unique. For the existence just consider , since we can find satisfying that condition.

Now suppose again we only had the restriction , we know that in this case the solution for integers is unique. If then must be greater than Indeed, suppose it wasn't, then we have ABSURD!

So we have found that if there's a solution in the nonnegative integers!

Now note that , so, by the unique of the representation if and x, y are integers, it follows that, if there can be no solution in the positive integers.

So the smallest integer such that for all , has a solution for nonnegative integers is

Sorry I got lost going through your response.

Where does the equation below come from?

ax + by = ax' + by' = n

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 are integers and they satisfy: ( both with the condition ) then 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