1 00:00:00,000 --> 00:00:00,366 2 00:00:00,366 --> 00:00:02,633 So tips for gcd type problems. 3 00:00:02,633 --> 00:00:06,200 So when tackling a gcd type problem, we can try the following tips. 4 00:00:06,200 --> 00:00:06,966 5 00:00:06,966 --> 00:00:09,466 I have these 3 bullets, and I'll mention 
what the brackets are in a minute. 6 00:00:09,466 --> 00:00:12,666 These are a great analogy 
given to me by JP Pretti, 7 00:00:12,666 --> 00:00:15,966 but first I want to talk about the order. 8 00:00:15,966 --> 00:00:18,766 So thing 1 that you should try when 
you're looking at a gcd problem 9 00:00:18,766 --> 00:00:20,533 is trying to use key theorems from the course, 10 00:00:20,533 --> 00:00:21,266 11 00:00:21,266 --> 00:00:23,666 especially some of the 
following: so we have 12 00:00:23,666 --> 00:00:26,600 Bézout’s Theorem, or the 
Extended Euclidean Algorithm, 13 00:00:26,600 --> 00:00:29,600 and this is good when you're you're doing either a computation, 14 00:00:29,600 --> 00:00:32,900 or when the greatest common divisor condition is in the hypothesis, right? 15 00:00:32,900 --> 00:00:36,200 Once you have that, then you can get these integers x and y that do something, 16 00:00:36,200 --> 00:00:38,400 and then maybe you can manipulate 
them to get the results you want. 17 00:00:38,400 --> 00:00:39,133 18 00:00:39,133 --> 00:00:44,000 GCDWR, this is good when terms in the greatest 
common divisor, they depend on each other. 19 00:00:44,000 --> 00:00:48,000 So if you're, let's say for example, looking for 
the greatest common divisor of n and n plus 1, 20 00:00:48,000 --> 00:00:49,466 for any integer n. 21 00:00:49,466 --> 00:00:53,766 Using GCDWR gives you a good way 
to simplify the problem and tackle it. 22 00:00:53,766 --> 00:00:56,000 23 00:00:56,000 --> 00:00:57,900 Lastly, GCDCT, 24 00:00:57,900 --> 00:01:00,000 this is good when the 
gcd is in the conclusion. 25 00:01:00,000 --> 00:01:03,200 So if you remember, the GCD 
Characterization Theorem tells us hey 26 00:01:03,200 --> 00:01:03,666 27 00:01:03,666 --> 00:01:08,000 if you have a divisor, 
d, greater than 0 28 00:01:08,000 --> 00:01:11,200 of two numbers a and 
b, and you can write 29 00:01:11,200 --> 00:01:14,300 d as an integer linear combination of a and b, 30 00:01:14,300 --> 00:01:17,933 then you can conclude that d 
must be the gcd of a and b. 31 00:01:17,933 --> 00:01:19,700 32 00:01:19,700 --> 00:01:22,966 So that's why it's good when you 
have the gcd in the conclusion 33 00:01:22,966 --> 00:01:25,233 because you get some 
results about the gcd. 34 00:01:25,233 --> 00:01:28,266 And don't forget about your other theorems, right, your DBGCD, 35 00:01:28,266 --> 00:01:31,800 Divide By GCD, your 36 00:01:31,800 --> 00:01:34,100 GCD Of One, your 37 00:01:34,100 --> 00:01:37,066 Coprimeness and Divisibility, all 
these results are very important. 38 00:01:37,066 --> 00:01:40,366 We'll see Coprimeness and 
Divisibility in a moment. 39 00:01:40,366 --> 00:01:42,400 40 00:01:42,400 --> 00:01:46,300 Then okay, so once you've tried 
all your big hammers, your 41 00:01:46,300 --> 00:01:48,066 key theorems in this course, 42 00:01:48,066 --> 00:01:50,766 one thing to try is you can 
use the definition of gcd, 43 00:01:50,766 --> 00:01:52,833 and that... 44 00:01:52,833 --> 00:01:55,000 that'll usually… well that can 
always get you to the answer, 45 00:01:55,000 --> 00:01:57,633 but it might be difficult to write up, 
right? It's going to be very slow, 46 00:01:57,633 --> 00:02:02,200 it's going to be… you're going to need to take your 
time and be very careful about your argument. 47 00:02:02,200 --> 00:02:04,600 And then the last sort of 48 00:02:04,600 --> 00:02:08,533 ditch effort technique is to use prime factorizations, so use GCDPF. 49 00:02:08,533 --> 00:02:09,766 50 00:02:09,766 --> 00:02:12,566 Now why are these
things here in the side? 51 00:02:12,566 --> 00:02:14,833 Highway 401, Highway 7, and flying? 52 00:02:14,833 --> 00:02:19,700 So the analogy here is, pretend you're 
trying to travel from Waterloo to Toronto. 53 00:02:19,700 --> 00:02:20,533 54 00:02:20,533 --> 00:02:22,633 The one way you can do this, 55 00:02:22,633 --> 00:02:26,266 as many of you know, is by 
driving on Highway 401. 56 00:02:26,266 --> 00:02:29,033 Highway 401 is… 57 00:02:29,033 --> 00:02:32,000 when the traffic moves, it’s a very good 
highway. You can drive pretty quickly, 58 00:02:32,000 --> 00:02:34,566 and you make it there 
without too many problems. 59 00:02:34,566 --> 00:02:36,533 Once in a while, you know, 
there's an accident or something, 60 00:02:36,533 --> 00:02:38,533 it might cause a 
bit of a slowdown 61 00:02:38,533 --> 00:02:40,900 but this way is usually the quickest to get to the answer. 62 00:02:40,900 --> 00:02:41,966 63 00:02:41,966 --> 00:02:44,366 Driving by Highway 7, so this 
is like taking the backroads 64 00:02:44,366 --> 00:02:46,033 to go from Waterloo to Toronto. 65 00:02:46,033 --> 00:02:49,133 You're going to make it there, but 
it's going to take you a long time, 66 00:02:49,133 --> 00:02:50,200 67 00:02:50,200 --> 00:02:52,500 you're going to have to be careful. 
There's going to be lots of details that 68 00:02:52,500 --> 00:02:55,766 you're going to have to… that you're going to pick 
up, and you're going to have to be careful with. 69 00:02:55,766 --> 00:02:58,533 So that's the analogy of 
using the definition of the gcd. 70 00:02:58,533 --> 00:03:02,000 It's going to be slow, you're going to have 
to be meticulous, but you'll get there. 71 00:03:02,000 --> 00:03:02,866 72 00:03:02,866 --> 00:03:05,866 Flying is using the prime factorizations of numbers. 73 00:03:05,866 --> 00:03:07,700 74 00:03:07,700 --> 00:03:10,166 This seems like a really quick 
idea, right, you're flying 75 00:03:10,166 --> 00:03:12,466 so you should be going ten 
times as fast as a car, right? 76 00:03:12,466 --> 00:03:15,766 But the problem, of 
course while flying is that 77 00:03:15,766 --> 00:03:16,500 78 00:03:16,500 --> 00:03:19,800 you know you have to go 
through the airport security, 79 00:03:19,800 --> 00:03:23,633 you have to pack your luggage, things 
like this. This can be often a very 80 00:03:23,633 --> 00:03:25,933 arduous and difficult chore. 81 00:03:25,933 --> 00:03:28,000 So here the write-up, what's the analogy here? 82 00:03:28,000 --> 00:03:30,000 So the write-up for using 
a prime factorization 83 00:03:30,000 --> 00:03:32,400 proof is actually 
really, really difficult. 84 00:03:32,400 --> 00:03:35,700 You have to quantify everything, you 
have to state what things are, I'm using 85 00:03:35,700 --> 00:03:39,300 primes, I'm using integers, I'm 
using exponents, that can be 86 00:03:39,300 --> 00:03:41,400 positive or 0, and 87 00:03:41,400 --> 00:03:43,700 and all of these things matter, right? 88 00:03:43,700 --> 00:03:47,500 So this is going to take you…it's going 
to take time, as a summary of this. 89 00:03:47,500 --> 00:03:48,400 90 00:03:48,400 --> 00:03:50,700 So that's the analogy here. So again, 91 00:03:50,700 --> 00:03:53,766 using the key theorems should get 
you there the quickest if you can. 92 00:03:53,766 --> 00:03:56,000 Using the definition of 
gcd gets you there… 93 00:03:56,000 --> 00:03:59,466 if the theorems don't seem to work or 
you don't have any other choices. 94 00:03:59,466 --> 00:04:02,033 Sometimes, you know, you'll 
pick up details along the way, 95 00:04:02,033 --> 00:04:05,000 and of course the last way, 
flying, so using GCPPF 96 00:04:05,000 --> 00:04:07,400 seems like a good idea at first, 
until you try to do it you're like, 97 00:04:07,400 --> 00:04:09,700 “Oh my gosh, there's so many 
details I have to remember 98 00:04:09,700 --> 00:04:12,733 and write up to make 
my proof look correct.” 99 00:04:12,733 --> 00:04:13,833 Okay. 100 00:04:13,833 --> 00:04:15,600 So that's it for the gcd type problems. 101 00:04:15,600 --> 00:04:17,100 This is what we're going 
to end with in gcd’s.