1 00:00:00,000 --> 00:00:00,466 2 00:00:00,466 --> 00:00:02,633 So to finish off… 3 00:00:02,633 --> 00:00:05,333 so this is something that I 
like to do at this point. 4 00:00:05,333 --> 00:00:09,900 Again, because I proved the Fundamental 
Theorem of Arithmetic last week, 5 00:00:09,900 --> 00:00:12,400 up to this lemma. 
I now want to get 6 00:00:12,400 --> 00:00:14,933 to this lemma as quickly as 
possible and I have done this. 7 00:00:14,933 --> 00:00:17,633 Notice that this isn't cyclic 
in any way, shape, or form. 8 00:00:17,633 --> 00:00:19,433 So, I mean, I could, you know, 9 00:00:19,433 --> 00:00:23,166 I didn't use Euclid's Lemma anywhere else in the last couple of days before, 10 00:00:23,166 --> 00:00:25,566 you know, going through the 
proof of the Fundamental - 11 00:00:25,566 --> 00:00:28,000 or after going through the proof of the Fundamental Theorem of Arithmetic. 12 00:00:28,000 --> 00:00:30,933 So there's no logical continuity 
errors, anything like that. 13 00:00:30,933 --> 00:00:35,133 But I do like to use the Fundamental 
Theorem of Arithmetic to motivate this result 14 00:00:35,133 --> 00:00:36,633 of Euclid's Lemma 15 00:00:36,633 --> 00:00:38,633 because it is quite a… 16 00:00:38,633 --> 00:00:42,500 it's surprisingly difficult to prove this, 
even though it looks very simple. 17 00:00:42,500 --> 00:00:43,066 18 00:00:43,066 --> 00:00:45,466 So what's Euclid's 
Lemma say again? 19 00:00:45,466 --> 00:00:48,800 “If p is a prime number and p divides a b for integers a, b, 20 00:00:48,800 --> 00:00:51,366 then p divides a, 
or p divides b. 21 00:00:51,366 --> 00:00:52,033 22 00:00:52,033 --> 00:00:55,400 Again, a good exercise: ask yourself, 
“What proof technique do I use here?” 23 00:00:55,400 --> 00:00:57,300 I have an “or” in the conclusion. 24 00:00:57,300 --> 00:01:00,800 A lot of the times it makes sense to 
use an argument by elimination. 25 00:01:00,800 --> 00:01:03,300 So take one of these 
two things to be false, 26 00:01:03,300 --> 00:01:05,766 so I'm just going to pick p divides a is false, 27 00:01:05,766 --> 00:01:06,300 28 00:01:06,300 --> 00:01:08,333 and I'm going to also 
assume the hypothesis, 29 00:01:08,333 --> 00:01:11,300 so I'm going to suppose that 
p is prime, p divides a b, 30 00:01:11,300 --> 00:01:14,666 and that p does not divide a, and 
I'm going to show that p divides b. 31 00:01:14,666 --> 00:01:17,966 Again remember, why is this true? 
Well if p divides a, I'm done, right? 32 00:01:17,966 --> 00:01:20,166 The conclusion’s true, the 
implication is therefore true. 33 00:01:20,166 --> 00:01:24,000 I don't need to do anything. So I might as 
well start by assuming that p doesn't divide a. 34 00:01:24,000 --> 00:01:26,066 35 00:01:26,066 --> 00:01:28,000 So how do I link all this 
together? Why did I 36 00:01:28,000 --> 00:01:29,966 need greatest common 
divisors to do this? 37 00:01:29,966 --> 00:01:33,266 Okay so in some sense you never need something to do something else, 38 00:01:33,266 --> 00:01:36,666 but it does help formulate 
the argument a lot nicer. 39 00:01:36,666 --> 00:01:40,800 So since p doesn't divide a the 
gcd of p and a, that's equal to 1. 40 00:01:40,800 --> 00:01:41,833 41 00:01:41,833 --> 00:01:44,166 Well because it's equal to 
1, well by Bézout’s Lemma, 42 00:01:44,166 --> 00:01:47,400 again, I have a gcd condition, so I 
might as well use Bézout’s Lemma, 43 00:01:47,400 --> 00:01:51,000 there exist integers x and y 
such that p x plus a y equals 1. 44 00:01:51,000 --> 00:01:52,100 45 00:01:52,100 --> 00:01:54,033 Now you look at this line, 
and maybe in a vacuum 46 00:01:54,033 --> 00:01:56,000 you might wonder oh well why is this useful? 47 00:01:56,000 --> 00:01:59,733 I mean, I don't really… I mean I want to 
show that p divides b and there's no b here. 48 00:01:59,733 --> 00:02:00,333 49 00:02:00,333 --> 00:02:04,333 So when you're doing something like this, 
I mean sometimes it might not be clear 50 00:02:04,333 --> 00:02:07,200 why this is useful, right? I mean it 
doesn't look like I'm making any progress 51 00:02:07,200 --> 00:02:08,766 towards getting p divides b, 52 00:02:08,766 --> 00:02:11,800 but sometimes it helps to just write 
things down and play around with it. 53 00:02:11,800 --> 00:02:13,466 In this case, it actually helps a lot because 54 00:02:13,466 --> 00:02:16,300 now what we're going to do is multiply 
by b, we’re going to introduce b. 55 00:02:16,300 --> 00:02:17,400 56 00:02:17,400 --> 00:02:19,666 And so how do we do that? We're going to multiply everything by b, we get 57 00:02:19,666 --> 00:02:22,333 p b x plus a b y 
is equal to p. 58 00:02:22,333 --> 00:02:23,533 59 00:02:23,533 --> 00:02:26,066 Now what do we have? Well 
p divides p, that's clear, 60 00:02:26,066 --> 00:02:29,033 p divides a b, that 
was the hypothesis, 61 00:02:29,033 --> 00:02:31,133 so thus by Divisibility of 
Integer Combinations, 62 00:02:31,133 --> 00:02:34,400 we have that p divides 
p b x plus a b y, 63 00:02:34,400 --> 00:02:36,833 and this value right here, 64 00:02:36,833 --> 00:02:40,466 that's the same as this value right here. 
So that's equal to b, so hence p divides b, 65 00:02:40,466 --> 00:02:41,900 And that's the end of the proof. 66 00:02:41,900 --> 00:02:42,700 67 00:02:42,700 --> 00:02:45,566 So this theorem is very easy 
to prove…well this lemma 68 00:02:45,566 --> 00:02:48,500 is very easy to prove once 
you have the right tools. 69 00:02:48,500 --> 00:02:51,900 Before having the right tools, this 
could be very tricky to prove. 70 00:02:51,900 --> 00:02:53,000 71 00:02:53,000 --> 00:02:55,300 I've actually tried it and 
not had much success. 72 00:02:55,300 --> 00:02:58,900 You could probably do it if you're 
careful, but I haven't had success. 73 00:02:58,900 --> 00:03:00,500 74 00:03:00,500 --> 00:03:04,000 This being said, now we've reached the point 
where we're going to have a couple more theorems 75 00:03:04,000 --> 00:03:05,733 that we've done through the week. 76 00:03:05,733 --> 00:03:07,233 77 00:03:07,233 --> 00:03:11,033 Again they're good practice, they just 
practice our tools, these theorems. 78 00:03:11,033 --> 00:03:14,066 And again it's going get - there's 
a lot of names here, so don't 79 00:03:14,066 --> 00:03:15,333 get overwhelmed, okay? 80 00:03:15,333 --> 00:03:17,433 Just try to take it 
one at a time and 81 00:03:17,433 --> 00:03:18,566 82 00:03:18,566 --> 00:03:19,900 practice the mix, okay, 83 00:03:19,900 --> 00:03:22,600 don't just practice one at a time. 
Practice one then practice another, 84 00:03:22,600 --> 00:03:26,266 then go back to the first one, maybe 
go to another one, mix it up, okay? 85 00:03:26,266 --> 00:03:27,000 86 00:03:27,000 --> 00:03:31,133 Why do I say mix it up? Well because 
on an exam or on a test or in life, 87 00:03:31,133 --> 00:03:33,366 things are going to be mixed up. It's not going to be hey just solve 88 00:03:33,366 --> 00:03:36,000 this question using 
this technique. It's 89 00:03:36,000 --> 00:03:37,866 going to take a 
little bit of thinking 90 00:03:37,866 --> 00:03:40,000 to figure out which 
technique is good. 91 00:03:40,000 --> 00:03:43,933 So first theorem that we have 
is GCD Of One, GCDOO. 92 00:03:43,933 --> 00:03:47,766 “Let a and b be integers, then the greatest 
common divisor of a b is 1 if and only if 93 00:03:47,766 --> 00:03:50,900 there exist integers x and y 
such that a x plus b y equals 1.” 94 00:03:50,900 --> 00:03:53,966 This looks very similar to something that we did earlier. 95 00:03:53,966 --> 00:03:56,133 That was one of the 
sample exercises. 96 00:03:56,133 --> 00:03:56,866 97 00:03:56,866 --> 00:04:00,266 But here's an “if and only if” 
statement so that extra “only if” part, 98 00:04:00,266 --> 00:04:02,566 it's going to add us a little 
bit more work, but that's okay. 99 00:04:02,566 --> 00:04:03,200 100 00:04:03,200 --> 00:04:07,266 So to go in the implication direction: suppose that the gcd of a and b equals 1. 101 00:04:07,266 --> 00:04:11,066 Again, we started with the gcd condition so we should probably use Bézout’s Lemma. 102 00:04:11,066 --> 00:04:11,733 103 00:04:11,733 --> 00:04:14,000 And it turns out that that's 
exactly going to work, right? 104 00:04:14,000 --> 00:04:16,300 If we use Bézout’s Lemma, that's exactly the conclusion. 105 00:04:16,300 --> 00:04:18,033 So that direction’s easy. 106 00:04:18,033 --> 00:04:20,200 The other direction’s not too hard either though, right? 107 00:04:20,200 --> 00:04:24,200 Suppose that there exist integers x 
and y such that a x plus b y equals 1. 108 00:04:24,200 --> 00:04:26,800 So what can we do now? 
Now we want to conclude 109 00:04:26,800 --> 00:04:28,733 something about the 
greatest common divisor, 110 00:04:28,733 --> 00:04:31,133 so we should use the GCD Characterization Theorem, 111 00:04:31,133 --> 00:04:33,366 and that's exactly 
what happens here. 112 00:04:33,366 --> 00:04:35,366 So again, notice 
the difference here. 113 00:04:35,366 --> 00:04:38,666 When we were proving the implication, 
we used Bézout’s Lemma 114 00:04:38,666 --> 00:04:42,400 because the implication was in the - 
because the gcd was in the hypothesis, 115 00:04:42,400 --> 00:04:45,633 and when we're proving the converse, we're using GCDCT 116 00:04:45,633 --> 00:04:48,400 because now the greatest common 
divisor condition is in the conclusion. 117 00:04:48,400 --> 00:04:49,700 118 00:04:49,700 --> 00:04:52,266 So going through that thought, 
a x plus b y equals 1, 119 00:04:52,266 --> 00:04:56,966 1 divides a, 1 divides B, 1 is 
equal to 1, 1 is greater than 0, 120 00:04:56,966 --> 00:05:00,000 therefore by GCDCT. the gcd of a and b is 1. 121 00:05:00,000 --> 00:05:01,233 122 00:05:01,233 --> 00:05:03,366 And that's that. So it gives 
us a characterization of 123 00:05:03,366 --> 00:05:05,933 when the gcd of a and b is 1. 124 00:05:05,933 --> 00:05:07,133 125 00:05:07,133 --> 00:05:09,800 Next one: Division 
By the GCD. 126 00:05:09,800 --> 00:05:12,766 So let a and b be integers. If the 
gcd of a and b is equal to d 127 00:05:12,766 --> 00:05:14,433 and d is not 0, 128 00:05:14,433 --> 00:05:18,966 then the gcd of a over d comma 
b over d that's equal to 1. 129 00:05:18,966 --> 00:05:20,100 130 00:05:20,100 --> 00:05:22,033 Notice that we 
need the gcd… 131 00:05:22,033 --> 00:05:25,833 that we need d to not be 0 
because we want to divide by d, 132 00:05:25,833 --> 00:05:28,000 so that's clearly an important condition here. 133 00:05:28,000 --> 00:05:29,466 134 00:05:29,466 --> 00:05:31,433 Now if we think 
about this, okay… 135 00:05:31,433 --> 00:05:34,533 so what are we given? We're given 
a condition with the gcd, so 136 00:05:34,533 --> 00:05:36,800 we're probably going to want 
to use Bézout’s Theorem, 137 00:05:36,800 --> 00:05:40,733 and we need to conclude something 
about the gcd of something equaling 1, 138 00:05:40,733 --> 00:05:43,200 so we're probably going 
to also want to use 139 00:05:43,200 --> 00:05:45,766 the GCD Characterization Theorem, okay? 140 00:05:45,766 --> 00:05:46,866 141 00:05:46,866 --> 00:05:48,033 So... 142 00:05:48,033 --> 00:05:48,833 143 00:05:48,833 --> 00:05:53,233 So how do we go about this? So just try to do that exact thing, okay? 144 00:05:53,233 --> 00:05:55,733 So now, again, maybe 
a good exercise, 145 00:05:55,733 --> 00:05:58,066 pause the video and actually try to prove 
this. You should be able to prove this. 146 00:05:58,066 --> 00:06:00,500 It actually is sort of a “follow 
your nose” kind of proof, 147 00:06:00,500 --> 00:06:02,333 given that huge hint, okay? 148 00:06:02,333 --> 00:06:04,133 So take a minute and try it. 149 00:06:04,133 --> 00:06:05,900 Hopefully you've come back now. 150 00:06:05,900 --> 00:06:06,766 151 00:06:06,766 --> 00:06:08,833 Alright let's check 
out the proof. 152 00:06:08,833 --> 00:06:12,233 Suppose that the gcd of a and 
b is equal to d which is not 0, 153 00:06:12,233 --> 00:06:15,500 then by Bézout’s Lemma, there 
exist integers x and y such that 154 00:06:15,500 --> 00:06:17,333 a x plus b y equals d. 155 00:06:17,333 --> 00:06:19,833 So there's our use 
of Bézout’s Lemma. 156 00:06:19,833 --> 00:06:23,533 Dividing by the non-zero 
d gives us that 157 00:06:23,533 --> 00:06:27,433 a over d times x, plus b over 
d times y, is equal to 1. 158 00:06:27,433 --> 00:06:30,833 Well now that we have this condition, this 
looks a lot like the last thing we just proved, 159 00:06:30,833 --> 00:06:34,033 so now we can use that. By the GCD 
Of One condition, we know that 160 00:06:34,033 --> 00:06:36,366 the gcd of a over d and b over d is equal to 1. 161 00:06:36,366 --> 00:06:40,333 So you don't need to reprove things that 
we've proven, that's the emphasis off here. 162 00:06:40,333 --> 00:06:42,533 163 00:06:42,533 --> 00:06:45,766 But again remember so I did say, “Well we should use GCDCT.” 164 00:06:45,766 --> 00:06:47,933 Okay, I didn't use GCDCT, 
well that's because 165 00:06:47,933 --> 00:06:50,966 GCD Of One uses 
GCDCT, okay? 166 00:06:50,966 --> 00:06:53,333 So there are lots of 
ways to prove this. 167 00:06:53,333 --> 00:06:56,933 But again if you forget this theorem, it's 
fine to reprove it, that's perfectly fine. 168 00:06:56,933 --> 00:06:59,166 If you wanted to use 
GCDCT it will work, 169 00:06:59,166 --> 00:07:02,400 but you can make your life easier 
by also using GCD Of One. 170 00:07:02,400 --> 00:07:03,100 171 00:07:03,100 --> 00:07:05,700 I've made my life harder. 
Sometimes I like to do that. 172 00:07:05,700 --> 00:07:08,233 Okay. One more, 173 00:07:08,233 --> 00:07:10,733 Coprimeness and Divisibility. So, 174 00:07:10,733 --> 00:07:13,300 if a, b, c are integers 
and c divides a b 175 00:07:13,300 --> 00:07:15,566 and the gcd of a and c is 1, 176 00:07:15,566 --> 00:07:17,133 then c divides b. 177 00:07:17,133 --> 00:07:20,733 Again take a minute to try this out. This time 
I'm not going to give you hints, okay? 178 00:07:20,733 --> 00:07:22,833 Pause the video, try this out. 179 00:07:22,833 --> 00:07:26,733 It's a good exercise to do, 
it'll help you long-term. 180 00:07:26,733 --> 00:07:28,233 181 00:07:28,233 --> 00:07:30,200 So hopefully you've come back. 182 00:07:30,200 --> 00:07:32,233 If you're stuck 
maybe as a hint: 183 00:07:32,233 --> 00:07:33,133 184 00:07:33,133 --> 00:07:36,233 notice that we have a gcd 
condition in the hypothesis, 185 00:07:36,233 --> 00:07:37,933 so we should use… 186 00:07:37,933 --> 00:07:39,266 187 00:07:39,266 --> 00:07:40,700 what? 188 00:07:40,700 --> 00:07:42,166 Alright let's check 
out the proof. 189 00:07:42,166 --> 00:07:43,266 190 00:07:43,266 --> 00:07:44,600 Okay, 191 00:07:44,600 --> 00:07:47,900 so again assume the hypothesis, 
“Since the gcd of a and c is 1, 192 00:07:47,900 --> 00:07:52,000 by Bézout’s Lemma, there exist integers 
x and y such that a x plus c y equals 1.” 193 00:07:52,000 --> 00:07:54,300 It really is that sort of obvious. 194 00:07:54,300 --> 00:07:57,700 If a gcd condition is in the hypothesis, 
then use Bézout’s Lemma. 195 00:07:57,700 --> 00:07:59,933 Multiplying by b gives 196 00:07:59,933 --> 00:08:02,766 a b x plus c b y is equal to b. 197 00:08:02,766 --> 00:08:06,966 Since c divides a b and 
c divides c we can use… 198 00:08:06,966 --> 00:08:08,733 oh wait what do we know? 199 00:08:08,733 --> 00:08:10,100 Well what are we 
trying to show? 200 00:08:10,100 --> 00:08:13,033 Oh, c divides a b and 
c divides c, then 201 00:08:13,033 --> 00:08:16,000 I guess c must divide 
b, well that was easy. 202 00:08:16,000 --> 00:08:17,200 203 00:08:17,200 --> 00:08:20,800 What did I do? I actually 
reproved DIC here. 204 00:08:20,800 --> 00:08:22,200 Oh well that's okay. 205 00:08:22,200 --> 00:08:26,200 So since either c divides a b there exists 
an integer k such that a b is equal to c k. 206 00:08:26,200 --> 00:08:29,933 Substituting gives c k x plus c b y is equal to b. 207 00:08:29,933 --> 00:08:33,700 Thus c times k x plus b y 
equals b and so c divides b. 208 00:08:33,700 --> 00:08:36,600 Again you can use DIC here or you 
can go directly by the definition. 209 00:08:36,600 --> 00:08:39,266 I guess it's good to practice 
doing different things. 210 00:08:39,266 --> 00:08:42,466 Remind ourselves what the definition of divisibility is etc. 211 00:08:42,466 --> 00:08:43,466 212 00:08:43,466 --> 00:08:45,433 But yeah DIC would 
just crush it from here. 213 00:08:45,433 --> 00:08:48,000 C divides a b, 
c divides c so 214 00:08:48,000 --> 00:08:51,566 therefore c divides a b x 
plus c b y which is b by DIC.