1 00:00:00,000 --> 00:00:04,000 This algorithm…actually… 
so this algorithm 2 00:00:04,000 --> 00:00:08,300 we’ll learn… so in my section I'm going to teach this on… 3 00:00:08,300 --> 00:00:09,366 next week's lecture, 4 00:00:09,366 --> 00:00:10,366 5 00:00:10,366 --> 00:00:10,866 6 00:00:10,866 --> 00:00:12,266 on Monday’s lecture. 7 00:00:12,266 --> 00:00:15,266 I'm going to teach the Extended Euclidean Algorithm, 8 00:00:15,266 --> 00:00:17,800 but this process is also 
known as Bezout’s Lemma 9 00:00:17,800 --> 00:00:18,666 10 00:00:18,666 --> 00:00:20,833 the theorem states the following: 
“Let a and b be integers. 11 00:00:20,833 --> 00:00:22,566 then there exists integers 
x and y such that 12 00:00:22,566 --> 00:00:24,733 a x plus b y is equal to 
the gcd of a and b.' 13 00:00:24,733 --> 00:00:25,633 14 00:00:25,633 --> 00:00:27,500 What's the proof of this? 
Well the proof of this is 15 00:00:27,500 --> 00:00:29,833 do the Euclidean Algorithm, and then do back substitution. 16 00:00:29,833 --> 00:00:30,866 17 00:00:30,866 --> 00:00:33,033 That's the like three line proof. 18 00:00:33,033 --> 00:00:35,533 Now you could go through and 
algebraically break this down. 19 00:00:35,533 --> 00:00:38,066 It is a little bit painful 
though, so I'm not going to. 20 00:00:38,066 --> 00:00:39,266 21 00:00:39,266 --> 00:00:41,766 You can check it out as extra 
reading. It’s definitely on Wikipedia, 22 00:00:41,766 --> 00:00:43,866 I believe it's also in 
your course notes. 23 00:00:43,866 --> 00:00:45,533 If not, again, it's on 
Wikipedia. It’s a very… 24 00:00:45,533 --> 00:00:47,600 it's easily accessible, it's 
a very common proof. 25 00:00:47,600 --> 00:00:48,333 26 00:00:48,333 --> 00:00:50,166 but it is... 27 00:00:50,166 --> 00:00:52,000 it is tedious there's no real reason - 28 00:00:52,000 --> 00:00:54,966 if you understood the previous two slides, 
there's no reason to really formally prove this. 29 00:00:54,966 --> 00:00:56,066 30 00:00:56,066 --> 00:00:58,733 But if you're curious you 
can go check it out. 31 00:00:58,733 --> 00:00:59,600 32 00:00:59,600 --> 00:01:00,900 So that's Bezout’s Lemma. 33 00:01:00,900 --> 00:01:03,533 Now when you have something 
like this, one question 34 00:01:03,533 --> 00:01:06,933 you might want to ask is, “What about a converse type theorem?” 35 00:01:06,933 --> 00:01:09,466 And a converse type theorem 
would look something like this: 36 00:01:09,466 --> 00:01:11,566 the GCD Characterization Theorem. 37 00:01:11,566 --> 00:01:12,266 38 00:01:12,266 --> 00:01:15,666 So if I have some 
positive integer d, 39 00:01:15,666 --> 00:01:18,233 and d divides a and d divides 
b where a and b are integers 40 00:01:18,233 --> 00:01:21,800 and there exist integers x and y such that a x plus b y equals d, 41 00:01:21,800 --> 00:01:24,766 so we have four conditions here 
that need to be satisfied. We need 42 00:01:24,766 --> 00:01:27,066 d to be a positive integer, 43 00:01:27,066 --> 00:01:29,333 we need d to be a common 
divisor of a and b, 44 00:01:29,333 --> 00:01:33,300 and we need d to be an integer 
linear combination of a and b. 45 00:01:33,300 --> 00:01:34,166 46 00:01:34,166 --> 00:01:37,366 If all those things are true, then d is the 
greatest common divisor of a and b. 47 00:01:37,366 --> 00:01:40,800 48 00:01:40,800 --> 00:01:42,700 So if you want to think - 49 00:01:42,700 --> 00:01:46,400 so let's think about maybe how would a 
proof go before I just show you the proof. 50 00:01:46,400 --> 00:01:47,066 51 00:01:47,066 --> 00:01:48,466 What would a proof 
look like? Well 52 00:01:48,466 --> 00:01:50,933 I want to show d is 
equal to some gcd value, 53 00:01:50,933 --> 00:01:54,866 so let's make some new letter 
e equal to gcd of a and b, 54 00:01:54,866 --> 00:01:57,033 okay, so some non-given letter, 55 00:01:57,033 --> 00:01:58,033 say e. 56 00:01:58,033 --> 00:02:01,800 Now I'm trying to show that d is less than 
or equal to e and e is less than or equal to d. 57 00:02:01,800 --> 00:02:03,866 Well e is a common 
divisor of a and b 58 00:02:03,866 --> 00:02:05,733 so e divides a, 
e divides b, 59 00:02:05,733 --> 00:02:09,533 therefore by Divisibility of Integer Combinations, once again, e must divide d 60 00:02:09,533 --> 00:02:11,066 61 00:02:11,066 --> 00:02:13,566 And now let's go in 
the opposite direction 62 00:02:13,566 --> 00:02:16,600 What do we have? Well d divides a and d divides b, so therefore 63 00:02:16,600 --> 00:02:18,766 d must be less than 
or equal to e because 64 00:02:18,766 --> 00:02:20,933 e is the greatest common 
divisor of a and b. 65 00:02:20,933 --> 00:02:24,000 So that's basically the idea here, 
so let's just take a look at it. 66 00:02:24,000 --> 00:02:25,433 67 00:02:25,433 --> 00:02:28,733 That's basically what I said, but 
I actually think I reversed it. 68 00:02:28,733 --> 00:02:30,833 So let e be the 
gcd of a and b, 69 00:02:30,833 --> 00:02:34,100 then since d divides a and 
d divides b, by definition 70 00:02:34,100 --> 00:02:37,433 and the maximality of e, we have that d must be less than or equal to e, right? 71 00:02:37,433 --> 00:02:40,900 e is the greatest common divisor of a and 
b and d is a common divisor of a and b. 72 00:02:40,900 --> 00:02:42,166 73 00:02:42,166 --> 00:02:44,866 Again, by definition, we see 
that e divides a and e divides b 74 00:02:44,866 --> 00:02:47,833 so by Divisibility of Integer 
Combinations, we have that e divides 75 00:02:47,833 --> 00:02:49,900 a linear combination of a and b, 76 00:02:49,900 --> 00:02:52,166 specifically the given one. 77 00:02:52,166 --> 00:02:54,066 This implies that e divides d. 78 00:02:54,066 --> 00:02:56,000 So thus by Bounds By 
Divisibility, we know that 79 00:02:56,000 --> 00:02:59,033 the absolute of e is less than or 
equal to the absolute value of d, 80 00:02:59,033 --> 00:03:01,133 and here's where we needed 
the fact that d was positive, 81 00:03:01,133 --> 00:03:02,666 it's right here, we only know that 82 00:03:02,666 --> 00:03:04,866 the absolute value of e is less than 
or equal to the absolute value of d 83 00:03:04,866 --> 00:03:06,733 and we really want that e 
is less than or equal to d, 84 00:03:06,733 --> 00:03:09,366 and we get that because both 
of these things are positive. 85 00:03:09,366 --> 00:03:11,133 So hence d equals e. 86 00:03:11,133 --> 00:03:12,366 87 00:03:12,366 --> 00:03:14,833 So something to note 
here, so my proofs and… 88 00:03:14,833 --> 00:03:17,966 well my proofs and I think everyone's 
proofs who teaches this course, 89 00:03:17,966 --> 00:03:20,733 are going to get a little bit…
I’m going to say sloppier but 90 00:03:20,733 --> 00:03:22,700 I don't want to… that's not really true. 91 00:03:22,700 --> 00:03:23,433 92 00:03:23,433 --> 00:03:25,800 If you're going to prove something 
directly, a lot of the times 93 00:03:25,800 --> 00:03:28,000 mathematicians won't write, “Assume that 94 00:03:28,000 --> 00:03:30,266 d is greater than 
0 and d divides a 95 00:03:30,266 --> 00:03:33,100 and d divides b and there 
exist integers x and y…” 96 00:03:33,100 --> 00:03:35,900 it's kind of implied that okay well 
if I'm proving this and I don't 97 00:03:35,900 --> 00:03:39,266 give you any indication that I'm doing 
something else, it's going to be a direct proof. 98 00:03:39,266 --> 00:03:40,633 99 00:03:40,633 --> 00:03:42,500 You know, if I want to prove 
something by contradiction, 100 00:03:42,500 --> 00:03:44,900 maybe I'll mention, “Assume towards a contradiction…” something like that 101 00:03:44,900 --> 00:03:48,633 but in a direct proof, I'm not going to 
rewrite the hypothesis every single time. 102 00:03:48,633 --> 00:03:50,300 103 00:03:50,300 --> 00:03:52,000 It's pretty clear that 
this is going to be - 104 00:03:52,000 --> 00:03:56,000 well that this is a direct proof, 
so I don't need to rewrite it. 105 00:03:56,000 --> 00:03:59,366 If you find that it helps you to rewrite 
the hypothesis, then I suggest 106 00:03:59,366 --> 00:04:01,933 you go ahead and do 
that. That's perfectly fine. 107 00:04:01,933 --> 00:04:02,533 108 00:04:02,533 --> 00:04:06,533 But I'm going to try to steer away 
from doing that and try to write 109 00:04:06,533 --> 00:04:10,366 mathematics now a little bit more how 
you would see it in a textbook and such.