So some mixed examples. So
we did a bunch of examples in class…
well okay I should say that hopefully you did a bunch of examples in class.
And here are some, and I decided to
mix them up instead of doing them right after the theorems.
So “prove that the gcd of 3s plus t and s is equal to the gcd of s and t.”
So s and t here are integers. Again
if we don't say, you take them to be as big as possible.
You take s and t to belong to the domain
as big as possible where this makes sense.
That you know of course.
Using GCDWR, so I gave you a little hint here
and said, “Use GCDWR.”
Again if you're solving this at home,
or if you're practicing - by the way at this point in the video,
you should stop it and actually try to do this, okay?
It's a good practice to even redo this even if you have done this before.
So if you look at this and, again,
if you don't know what GCDWR is,
the first thing you should do is look it up.
I've been generous and I'm actually going to copy it here,
but that's a good skill to have, okay? So if a, b, q, r are integers
and a equals b q plus r, then the gcd of a and b is equal to the gcd of b and r.
Well okay,
so I need to somehow
get an a equal to a, b q plus r
and assuming that my b and r are going to somehow be s and t,
that means that a should probably be something from here, well s is my b then
maybe 3s plus t should be my a,
and I'm going to try to make the q work.
How do we do that? Well plug those in, and just figure out what's going to work.
So if 3s plus t is equal to, here I've written it as q b instead of b q I apologize,
but 3s plus t is equal to 3 times s plus t.
That doesn't look like much,
but that's basically gcd with remainders, right? I mean
gcd with remainders states that, “The gcd of 3s plus t comma s is equal to
the gcd of s and t by setting a equals to 3s plus t,
b equals to s, q equals to 3, and r equals to t.
That's exactly a direct use of this theorem.
So I have 4 integers,
3s plus t, s,
t, and the number 3,
and I've related them in some "a equals b q plus r" way.
That was done right here.
Then I get the conclusion for free. That's using a theorem.
Just a reminder of that fact at this point.
Let's do another one, another mixed example.
Oh this time I just show you the answer, I apologize.
You should just try to copy the question down and try not to look at proof,
so hide it! No okay I'm sorry…
”Prove that if a, b, x, y are integers such that
the gcd of a and b is not 0,
and a x plus b y is equal to the gcd of a and b,
then the gcd of x and y must be 1.
This is something that's important, we'll see this actually later in this video as well.
So what's the idea here? So
since the greatest common divisor of a and b divides a and b,
we divide by the non-zero number, the greatest common divisor of a and b, to see that
we get the following expression.
So here I took the hypothesis, a x plus b y is equal to the gcd of a and b,
and simplified it to get 1 on one side, okay?
Why am I doing this? So maybe I should have mentioned this before...
before I went through the proof,
but the gcd of x and y equals 1, that's in the conclusion.
When a greatest common divisor condition is in the conclusion, it's usually good to use
the GCD Characterization Theorem.
Why do we do that?
Well the reason why you do it is because, well, it will usually work,
but perhaps answering the question, “why will it work?”
GCDCT has the gcd condition in the conclusion.
So if you want to conclude something about a greatest common divisor, it's
probably good to use a theorem that allows you to
conclude something about the greatest common divisor.
So that's the idea,
but in order to use GCDCT I need 1
isolated on its own.
And the only equation I'm given is a x plus b y is equal to the greatest common divisor of a and b.
So how do I get the 1 on its own? Well I probably want to divide by the gcd of a and b.
So I'm going a little bit backwards and a little bit forward,
but doing that helps you to formulate the proof
and then you just have to write it up formally.
With all this in place,
Now we just look at what we have and now we say, “well okay 1 divides
x, 1 divides y, and 1 is greater than 0,
so GCDCT implies that the gcd of x and y equals 1.”
Now if you have the GCD Characterization Theorem in front of you, this might be confusing,
because here x is playing the role as a in that theorem and
y is playing the role of b in that theorem,
and a over the gcd of a and b that's going to be like your x
and b over the gcd of a and b is going to be like your y
in the GCD Characterization Theorem.
So it can be confusing, just make sure that you remember that
okay these a, b, x, y are different than the a, b, x, y
possibly in the GCD Characterization Theorem.
Well when you use it. Okay?
Just because things are the same letter, doesn't mean that they have the same use.
That's all I should about that.
Good tip, so just a reminder of this tip,
it's good enough that I've given it its own slide,
“If the greatest common divisor condition appears in the hypothesis,
then Bézout’s Lemma or the Extended Euclidean Algorithm might be useful.
If the gcd, the greatest common divisor, condition appears in the conclusion,
then GCD Characterization Theorem might be useful.”
Just a good tip, okay?
If it's in the hypothesis, then you can use Bézout’s lemma to get somewhere,
and if it's in the conclusion then you might want to use GCDCT to get somewhere.
We're going to see a lot of examples of using
Bézout’s Lemma a little bit later on in this
slideshow.
So again a good tip, keep it in mind.