Now we have a scientific name for our topic.

It's Integer Linear Combinations.

But the problem is quite elementary.

Let's see. So, imagine a country where there are only two types of coins,

the unit is, for example,

florin and there are two coins,

seven and 13 and there are two people, a buyer and a seller,

and each of them has

many coins of each type and one of them wants to pay six florin to the other.

Is it possible or not?

Probably, you will say

that we are kidding because it is obvious that six is 13 minus seven so

you pay 13 and you get back seven and everything is done.

But now, what about paying one florin? Also you

can explicitly compute these,

you pay twice sevens fourteens and you get 13 back.

So it's one. But also you can make a more,

I would say, bottom up approach.

So, we know that we already can pay six and initially we can pay seven.

So you can pay seven and get six back.

And this is one. So you somehow capitalize on what you know already.

What about two florins?

Again, you can make a direct search and find something like this.

So you get to it this way.

Again you can capitalize on what you know already. Do you see how?

You see that it's possible to get one.

And so if you can pay one florin,

you can do it twice and then you pay two florins.

So it's just two times one is two, one is possible.

So this works for every integer amount.

So any integer amount is payable and in

mathematical language one can say that for every integer c this equation,

this x and y are just the number of coins

and the negative number means that the coins are going that direction.

And this equation has integer solution and in other terms,

every integer can be an integer linear combination of seven and 13.

That is probably a more mathematical way to say the same thing.

Now look at another case.

Imagine another country which has only 15 and 21 coins.

Again, how can we pay six? And again it is trivial.

It's 21 minus 15, but now look, can we pay eight or not?

What do you think?

There is an obstacle.

Look at this, all the coins are multiples of three.

So whatever you pay or you get is always

a multiple of three and eight is not a multiple of three,

so no chances for eight and for the same reason,

there is no chances to pay one.

And three, can we three? What do you think?

We know that we can pay six,

this we already know.

Now see that we can pay nine.

And because it's 15 minus six,

15 we know and six we all of us know.

Now, we know nine.

And so we can capitalize on this and say that we can pay nine and six and get three.

So this is called Euclid's algorithm actually,

probably you heard about this and we will come to this in number theory again.

For now we see that three is payable.

And if you want to unfold this you can just

compute for each of the number you can compute how you pay,

so how you pay nine,

how you pay six,

how you pay three and then you get this

and you can also check directly this is 45 and this is 42.

Yeah. So three is payable and for the same reason,

any multiple of three is payable.

And we can say that

this equation has integer solutions if and only if C is a multiple of three.

So if C is a multiple,

then there are solutions.

If C is not a multiple,

there is no solution.

So in other terms,

integer linear combinations of seven and 13 are exactly multiples of three.

The general statement of this form says that there are multiple of them.

If we have coins of two types,

their linear combinations are

multiple of the greatest common divisor

but this will be a topic of the number theory course.

Integer Linear Combinations

What is a Proof?

与讲师见面