So tips for gcd type problems.
So when tackling a gcd type problem, we can try the following tips.
I have these 3 bullets, and I'll mention what the brackets are in a minute.
These are a great analogy given to me by JP Pretti,
but first I want to talk about the order.
So thing 1 that you should try when you're looking at a gcd problem
is trying to use key theorems from the course,
especially some of the following: so we have
Bézout’s Theorem, or the Extended Euclidean Algorithm,
and this is good when you're you're doing either a computation,
or when the greatest common divisor condition is in the hypothesis, right?
Once you have that, then you can get these integers x and y that do something,
and then maybe you can manipulate them to get the results you want.
GCDWR, this is good when terms in the greatest common divisor, they depend on each other.
So if you're, let's say for example, looking for the greatest common divisor of n and n plus 1,
for any integer n.
Using GCDWR gives you a good way to simplify the problem and tackle it.
Lastly, GCDCT,
this is good when the gcd is in the conclusion.
So if you remember, the GCD Characterization Theorem tells us hey
if you have a divisor, d, greater than 0
of two numbers a and b, and you can write
d as an integer linear combination of a and b,
then you can conclude that d must be the gcd of a and b.
So that's why it's good when you have the gcd in the conclusion
because you get some results about the gcd.
And don't forget about your other theorems, right, your DBGCD,
Divide By GCD, your
GCD Of One, your
Coprimeness and Divisibility, all these results are very important.
We'll see Coprimeness and Divisibility in a moment.
Then okay, so once you've tried all your big hammers, your
key theorems in this course,
one thing to try is you can use the definition of gcd,
and that...
that'll usually… well that can always get you to the answer,
but it might be difficult to write up, right? It's going to be very slow,
it's going to be… you're going to need to take your time and be very careful about your argument.
And then the last sort of
ditch effort technique is to use prime factorizations, so use GCDPF.
Now why are these things here in the side?
Highway 401, Highway 7, and flying?
So the analogy here is, pretend you're trying to travel from Waterloo to Toronto.
The one way you can do this,
as many of you know, is by driving on Highway 401.
Highway 401 is…
when the traffic moves, it’s a very good highway. You can drive pretty quickly,
and you make it there without too many problems.
Once in a while, you know, there's an accident or something,
it might cause a bit of a slowdown
but this way is usually the quickest to get to the answer.
Driving by Highway 7, so this is like taking the backroads
to go from Waterloo to Toronto.
You're going to make it there, but it's going to take you a long time,
you're going to have to be careful. There's going to be lots of details that
you're going to have to… that you're going to pick up, and you're going to have to be careful with.
So that's the analogy of using the definition of the gcd.
It's going to be slow, you're going to have to be meticulous, but you'll get there.
Flying is using the prime factorizations of numbers.
This seems like a really quick idea, right, you're flying
so you should be going ten times as fast as a car, right?
But the problem, of course while flying is that
you know you have to go through the airport security,
you have to pack your luggage, things like this. This can be often a very
arduous and difficult chore.
So here the write-up, what's the analogy here?
So the write-up for using a prime factorization
proof is actually really, really difficult.
You have to quantify everything, you have to state what things are, I'm using
primes, I'm using integers, I'm using exponents, that can be
positive or 0, and
and all of these things matter, right?
So this is going to take you…it's going to take time, as a summary of this.
So that's the analogy here. So again,
using the key theorems should get you there the quickest if you can.
Using the definition of gcd gets you there…
if the theorems don't seem to work or you don't have any other choices.
Sometimes, you know, you'll pick up details along the way,
and of course the last way, flying, so using GCPPF
seems like a good idea at first, until you try to do it you're like,
“Oh my gosh, there's so many details I have to remember
and write up to make my proof look correct.”
Okay.
So that's it for the gcd type problems.
This is what we're going to end with in gcd’s.