1
00:00:00,000 --> 00:00:04,000
Hello everyone. Welcome to week 5 of Carmen's 
Core Concepts. My name is Carmen Bruni,

2
00:00:04,000 --> 00:00:08,000
and this week we're going to 
talk about Math 135 week 5.

3
00:00:08,000 --> 00:00:10,000
This had a lot to do with 
greatest common divisors.

4
00:00:10,000 --> 00:00:12,166
There were a couple of other 
topics scattered about,

5
00:00:12,166 --> 00:00:14,533
but that's the main 
topic of this week.

6
00:00:14,533 --> 00:00:18,666
Again I just want to remind everyone 
that this isn't meant to replace lectures.

7
00:00:18,666 --> 00:00:21,133
And if you use these 
in lieu of lectures, you're

8
00:00:21,133 --> 00:00:23,233
probably not going 
to get as much

9
00:00:23,233 --> 00:00:25,600
out of the course as you 
would have you've done both.

10
00:00:25,600 --> 00:00:27,433
The idea behind these videos 
is to give you some sort of

11
00:00:27,433 --> 00:00:30,100
spaced repetition where you go 
to the lectures during the week, 

12
00:00:30,100 --> 00:00:33,066
and then maybe later on you 
go back and you review them.

13
00:00:33,066 --> 00:00:36,166
And that should help you reinforce 
your learning about these concepts.

14
00:00:36,166 --> 00:00:36,800


15
00:00:36,800 --> 00:00:40,500
Okay so Euclid’s Theorem, this is one of 
my favorite theorems in mathematics.

16
00:00:40,500 --> 00:00:42,333
“There exists infinitely
many primes.”

17
00:00:42,333 --> 00:00:45,566
The reason why I like it, it's very 
simple and it's just very creative.

18
00:00:45,566 --> 00:00:48,466
It's a cool little argument that we're 
going to talk about briefly here.

19
00:00:48,466 --> 00:00:50,166
This isn't a full sketch, but

20
00:00:50,166 --> 00:00:52,266
the idea is that you 
argue by contradiction.

21
00:00:52,266 --> 00:00:55,666
It's tough to say that there 
exists infinitely many primes,

22
00:00:55,666 --> 00:00:58,366
but it's easier to argue that 
if you have finitely many,

23
00:00:58,366 --> 00:01:00,733
you can't have… you 
reach a contradiction.

24
00:01:00,733 --> 00:01:02,433
So...

25
00:01:02,433 --> 00:01:04,466
beginning with that, we

26
00:01:04,466 --> 00:01:07,666
start with finitely many primes, 
let’s call them the p1 to p n…

27
00:01:07,666 --> 00:01:08,566


28
00:01:08,566 --> 00:01:09,933
p little n

29
00:01:09,933 --> 00:01:10,600


30
00:01:10,600 --> 00:01:12,033
And then we're going to 
create the following number.

31
00:01:12,033 --> 00:01:14,100
We're going to create capital 
N is equal to 1 plus the

32
00:01:14,100 --> 00:01:16,633
product of all the finitely 
many primes, okay?

33
00:01:16,633 --> 00:01:17,066


34
00:01:17,066 --> 00:01:19,233
Now why can we do 
this topic now? Well

35
00:01:19,233 --> 00:01:21,866
we talked earlier about the 
Fundamental Theorem of Arithmetic;

36
00:01:21,866 --> 00:01:24,633
Unique Factorization, right? 
So N can be factored

37
00:01:24,633 --> 00:01:26,400
uniquely as a product of primes.

38
00:01:26,400 --> 00:01:28,166
So that means that 
one of these primes

39
00:01:28,166 --> 00:01:30,566
must divide N, at 
least one of them.

40
00:01:30,566 --> 00:01:32,866
One of the primes must 
also divide this product.

41
00:01:32,866 --> 00:01:34,233
That's also by

42
00:01:34,233 --> 00:01:36,666
Euclid’s Lemma, or the
Generalized Euclid’s Lemma.

43
00:01:36,666 --> 00:01:38,400


44
00:01:38,400 --> 00:01:41,166
So we have that a prime divides N 
and a prime divides this product,

45
00:01:41,166 --> 00:01:43,500
so it must divide the difference. 
Well the difference is 1,

46
00:01:43,500 --> 00:01:46,266
by Divisibility of Integer Combinations, 
and that's a contradiction.

47
00:01:46,266 --> 00:01:47,200


48
00:01:47,200 --> 00:01:49,566
Again these are - this is
just shorthand. This is just a

49
00:01:49,566 --> 00:01:51,766
very brief sketch, right? 
You shouldn't write

50
00:01:51,766 --> 00:01:53,433
p divides something 
equals something else.

51
00:01:53,433 --> 00:01:56,166
You should write p divides
this and hence p divides 1,

52
00:01:56,166 --> 00:01:59,133
but for a proof sketch I'm just 
going to write the shorthand.

53
00:01:59,133 --> 00:02:01,100
Okay so that's the idea. I
think this is a cool little proof. It

54
00:02:01,100 --> 00:02:04,166
doesn't require too much 
heavy duty mathematics.

55
00:02:04,166 --> 00:02:06,033
The Fundamental Theorem 
of Arithmetic is used,

56
00:02:06,033 --> 00:02:08,166
some sort of unique
factorization thing, but

57
00:02:08,166 --> 00:02:09,733
again it's not
too too bad.

58
00:02:09,733 --> 00:02:11,600
I like this argument. I 
think it's one of these

59
00:02:11,600 --> 00:02:13,466
arguments that every 
math major should know.

60
00:02:13,466 --> 00:02:15,500


61
00:02:15,500 --> 00:02:17,533
Greatest common divisor.

62
00:02:17,533 --> 00:02:19,000


63
00:02:19,000 --> 00:02:21,666
So this is something that we spent a lot 
of the week talking about. So let's just

64
00:02:21,666 --> 00:02:22,633
go over the definition again:

65
00:02:22,633 --> 00:02:24,900
“The greatest common 
divisor of integers a and b

66
00:02:24,900 --> 00:02:25,766


67
00:02:25,766 --> 00:02:28,700
with a or b not 0…” so one 
of these has to be not 0

68
00:02:28,700 --> 00:02:30,233
in order to use 
this definition,

69
00:02:30,233 --> 00:02:32,166
‘…it's an integer d such that

70
00:02:32,166 --> 00:02:32,766


71
00:02:32,766 --> 00:02:34,633
d is a common 
divisor of a and b,”

72
00:02:34,633 --> 00:02:36,966
that's condition 1: d 
divides a and d divides b,

73
00:02:36,966 --> 00:02:40,766
and condition 2 is “if I have another
common divisor of a and b [call it c],

74
00:02:40,766 --> 00:02:43,133
then I know that c must be 
less than or equal to d.”

75
00:02:43,133 --> 00:02:45,633
That's the greatest condition 
of a greatest common divisor.

76
00:02:45,633 --> 00:02:46,366


77
00:02:46,366 --> 00:02:48,566
So the greatest common 
divisor is a common divisor,

78
00:02:48,566 --> 00:02:51,566
and it is the largest 
such common divisor.

79
00:02:51,566 --> 00:02:52,966
The maximal such.

80
00:02:52,966 --> 00:02:53,666


81
00:02:53,666 --> 00:02:57,233
We write d equals the gcd of a 
and b, so that's how we denote it.

82
00:02:57,233 --> 00:03:00,166
Some examples: so the gcd 
of 120 and 84, that was one

83
00:03:00,166 --> 00:03:02,533
we saw in class, 
this is equal to 12.

84
00:03:02,533 --> 00:03:05,466
Again 12 divides 
120 and 12 divides

85
00:03:05,466 --> 00:03:08,833
84, happens to be the largest such 
number that has that property.

86
00:03:08,833 --> 00:03:11,700
gcd of 0 and 0, we 
define that to be 0.

87
00:03:11,700 --> 00:03:14,200
It just works out a lot 
easier in many proofs.

88
00:03:14,200 --> 00:03:15,166


89
00:03:15,166 --> 00:03:16,866
Works out a lot easier 
in many ways, so

90
00:03:16,866 --> 00:03:19,100
we just define the 
gcd of 0 and 0 to be 0.

91
00:03:19,100 --> 00:03:21,300
gcd of a and b is equal 
to the gcd of b and a.

92
00:03:21,300 --> 00:03:23,833
That holds in all cases. I'll 
leave that as an exercise.

93
00:03:23,833 --> 00:03:27,066
gcd of a and a is equal to the
absolute value of a. Don't forget that

94
00:03:27,066 --> 00:03:28,533
a can be negative,

95
00:03:28,533 --> 00:03:32,700
so it's important to use the absolute values 
here and same as the gcd of a and 0.

96
00:03:32,700 --> 00:03:35,000
The last thing, the gcd, the 
greatest common divisor,

97
00:03:35,000 --> 00:03:36,800
of a and b exists 
and is unique.

98
00:03:36,800 --> 00:03:40,166
Perhaps not surprising. There's only 
one greatest common divisor,

99
00:03:40,166 --> 00:03:41,366


100
00:03:41,366 --> 00:03:42,633
and it does exist.

101
00:03:42,633 --> 00:03:44,833
I mean, we know that 
it's bounded between 1…

102
00:03:44,833 --> 00:03:48,000
so 1 is a common divisor of 
a and b, and the biggest

103
00:03:48,000 --> 00:03:51,666
the common divisor could be is the 
minimum of the absolute value of a and b.

104
00:03:51,666 --> 00:03:53,033


105
00:03:53,033 --> 00:03:55,966
So that proves that it 
exists and it’s unique.

106
00:03:55,966 --> 00:03:58,066
That's all I want to say about the
greatest common divisor definition.

107
00:03:58,066 --> 00:03:59,266


108
00:03:59,266 --> 00:04:00,433
Well maybe I'll say 
one last thing

109
00:04:00,433 --> 00:04:02,533
there are other definitions of 
the greatest common divisor. 

110
00:04:02,533 --> 00:04:06,200
This is the one that we used in in our notes 
and that's the one that we used in class.

111
00:04:06,200 --> 00:04:08,000


112
00:04:08,000 --> 00:04:10,733
So let's start 
our theorem...

113
00:04:10,733 --> 00:04:12,333
montage? I guess.

114
00:04:12,333 --> 00:04:14,766
So gcd with remainder 
is our first one.

115
00:04:14,766 --> 00:04:16,533
“If a, b, q, r are
elements of the integers

116
00:04:16,533 --> 00:04:20,833
and a equals b q plus r, then the gcd of 
a and b is equal that the gcd of b and r.”

117
00:04:20,833 --> 00:04:23,033
So something 
to be careful of

118
00:04:23,033 --> 00:04:24,300
when you're going 
through these proofs;

119
00:04:24,300 --> 00:04:28,166
you always want to make sure you 
watch the “a equals b equals 0”  case.

120
00:04:28,166 --> 00:04:31,300
Sometimes it'll fall
through with your proof

121
00:04:31,300 --> 00:04:34,300
and sometimes it won’t. You
 have to isolate that case

122
00:04:34,300 --> 00:04:36,166
I believe this one just 
falls through. You can

123
00:04:36,166 --> 00:04:38,566
double check this as 
you're reading this

124
00:04:38,566 --> 00:04:40,666
or as you're listening to this.

125
00:04:40,666 --> 00:04:44,500
For the proof, whenever you're
trying to prove something about a gcd

126
00:04:44,500 --> 00:04:45,866
equalling some other object,

127
00:04:45,866 --> 00:04:48,166
it's usually easier, 
I find it easier,

128
00:04:48,166 --> 00:04:50,266
to write, “let d equal 
the gcd of a and b

129
00:04:50,266 --> 00:04:52,366
and let e equal
the gcd of b and r”

130
00:04:52,366 --> 00:04:54,766
and then I'm arguing
about d and e.

131
00:04:54,766 --> 00:04:57,100
I just find it easier to argue
like this. I don't have to write

132
00:04:57,100 --> 00:05:00,166
the letters gcd a b everywhere.

133
00:05:00,166 --> 00:05:01,633
It just makes it easier.

134
00:05:01,633 --> 00:05:02,900


135
00:05:02,900 --> 00:05:05,466
The general proof technique when 
you're using the definition of the

136
00:05:05,466 --> 00:05:08,900
greatest common divisor, it's usually good 
to show something - well in this case - 

137
00:05:08,900 --> 00:05:12,033
that d is less than or equal to e, 
and e is less than or equal to d.

138
00:05:12,033 --> 00:05:13,766
Just turns out to be
easier that way,

139
00:05:13,766 --> 00:05:16,166
and then because of that, we 
know they must be equal.

140
00:05:16,166 --> 00:05:17,500


141
00:05:17,500 --> 00:05:19,533
So how do we go?

142
00:05:19,533 --> 00:05:20,533


143
00:05:20,533 --> 00:05:22,400
So with this, we're going 
to start by showing

144
00:05:22,400 --> 00:05:25,266
that d is less than or equal to e,
and e is less than or equal to d.

145
00:05:25,266 --> 00:05:27,833
So what connects 
a, b, and r? Well

146
00:05:27,833 --> 00:05:30,833
a equals b q plus r. So that's the thing 
that we're going to have to use a lot.

147
00:05:30,833 --> 00:05:32,866
That's the only thing 
we're really given.

148
00:05:32,866 --> 00:05:35,000
So since a equals b q plus r,

149
00:05:35,000 --> 00:05:38,300
and we know that d is the greatest 
common divisor of a and b,

150
00:05:38,300 --> 00:05:40,766
so it is a common
divisor of a and b.

151
00:05:40,766 --> 00:05:43,200
Thus by DIC, Divisibility 
of Integer Combinations,

152
00:05:43,200 --> 00:05:45,300
we have that d divides

153
00:05:45,300 --> 00:05:48,166
a plus b minus q.

154
00:05:48,166 --> 00:05:52,166
But a minus b q that's 
just r. So hence, d divides r.

155
00:05:52,166 --> 00:05:54,600
So d divides b 
and d divides r,

156
00:05:54,600 --> 00:05:56,333
so by the maximality of e, 

157
00:05:56,333 --> 00:05:58,933
so e is the greatest 
common divisor

158
00:05:58,933 --> 00:05:59,933


159
00:05:59,933 --> 00:06:03,300
of b and r, we see that d must 
be less than or equal to e.

160
00:06:03,300 --> 00:06:04,500


161
00:06:04,500 --> 00:06:06,500
Alright, now in reverse, 
it's the same sort of idea.

162
00:06:06,500 --> 00:06:08,166
e divides b and e divides r, so

163
00:06:08,166 --> 00:06:11,733
once again, by DIC, 
e divides b q plus r,

164
00:06:11,733 --> 00:06:14,633
so b times q plus r, 
and that's just a,

165
00:06:14,633 --> 00:06:16,466
so therefore e divides a.

166
00:06:16,466 --> 00:06:19,900
Since d is the largest common divisor of a 
and b, we see that e is less than or equal to d

167
00:06:19,900 --> 00:06:22,033
and hence d equals e.

168
00:06:22,033 --> 00:06:24,900
So again, this is a
very typical argument

169
00:06:24,900 --> 00:06:28,166
of what you would do if you're trying 
to argue by the definition of gcd.

170
00:06:28,166 --> 00:06:31,000
Arguing by this
definition usually works...

171
00:06:31,000 --> 00:06:35,433
probably I can almost say 
“always” here and be very safe.

172
00:06:35,433 --> 00:06:39,366
You can always go back to the definition,
but it usually helps to use the tools

173
00:06:39,366 --> 00:06:43,700
that we've given you in this course to
help prove different or new theorems.

174
00:06:43,700 --> 00:06:46,266
Just know that it is possible to go
straight back to the definition.

175
00:06:46,266 --> 00:06:48,000


176
00:06:48,000 --> 00:06:50,533
Oh…I guess I kind of spoiled it,

177
00:06:50,533 --> 00:06:52,266
but what can we 
use GCDWR for?

178
00:06:52,266 --> 00:06:55,966
Remember I said it was kind of 
like…actually let me go back…

179
00:06:55,966 --> 00:06:58,066
I said it was kind of 
like a division algorithm

180
00:06:58,066 --> 00:06:59,566


181
00:06:59,566 --> 00:07:00,400
statement.

182
00:07:00,400 --> 00:07:03,233
a equals b q plus r. This looks 
like the division algorithm,

183
00:07:03,233 --> 00:07:05,500
right, except we don't 
have any restriction on r.

184
00:07:05,500 --> 00:07:07,366
Usually we bound r.

185
00:07:07,366 --> 00:07:08,066


186
00:07:08,066 --> 00:07:10,633
But here we don't have that 
restriction. r can be positive, negative,

187
00:07:10,633 --> 00:07:12,800
it can be very big, it 
can be very small.

188
00:07:12,800 --> 00:07:14,466
Again it turns out that

189
00:07:14,466 --> 00:07:18,433
if we use this in sort of the context of 
the division algorithm, we actually can

190
00:07:18,433 --> 00:07:20,166
get this algorithm called
the Euclidean Algorithm,

191
00:07:20,166 --> 00:07:24,666
which helps us to compute the greatest
common divisor of very large numbers

192
00:07:24,666 --> 00:07:26,200
very, very quickly.

193
00:07:26,200 --> 00:07:28,166
So that's what we're 
going to talk about next.

194
00:07:28,166 --> 00:07:32,166
Again, this is the heart of 
the Euclidean Algorithm.

195
00:07:32,166 --> 00:07:34,666
So let's see an example of 
the Euclidean Algorithm here.

196
00:07:34,666 --> 00:07:39,766
So compute the greatest common
divisor of 1239 and 735, okay?

197
00:07:39,766 --> 00:07:40,700


198
00:07:40,700 --> 00:07:45,300
So the idea here is repeated 
use of gcd with remainders.

199
00:07:45,300 --> 00:07:48,733
So 1239 is equal to 735

200
00:07:48,733 --> 00:07:50,433
times 1 plus 504.

201
00:07:50,433 --> 00:07:52,500
That's basically the division algorithm,

202
00:07:52,500 --> 00:07:56,633
but on the right hand side, 
this is gcd with remainders,

203
00:07:56,633 --> 00:08:00,900
so the greatest common
divisor of 1239 and 735,

204
00:08:00,900 --> 00:08:04,400
think of this as my a and 
think of this as my b,

205
00:08:04,400 --> 00:08:08,466
is the same as 
the gcd of b, 735,

206
00:08:08,466 --> 00:08:10,300
and r, 504.

207
00:08:10,300 --> 00:08:12,133


208
00:08:12,133 --> 00:08:15,633
So with that, you can kind of see 
oh okay well we've gotten from

209
00:08:15,633 --> 00:08:17,566
a 4 digit number and 
a 3 digit number…

210
00:08:17,566 --> 00:08:19,966
the greatest common divisor of a 4 
digit number and a 3 digit number

211
00:08:19,966 --> 00:08:24,000
to the greatest common divisor of a 
3 digit number and a 3 digit number.

212
00:08:24,000 --> 00:08:26,400
So we're slowly getting smaller 
and each of these numbers

213
00:08:26,400 --> 00:08:29,000
is strictly less than the
previous examples,

214
00:08:29,000 --> 00:08:31,266
and we can keep going
through this, okay? 

215
00:08:31,266 --> 00:08:36,700
So now…there's a little typo here. This 
should be 735, this shouldn't be 725.

216
00:08:36,700 --> 00:08:40,800
So 735 is equal to 504
times 1, plus 231.

217
00:08:40,800 --> 00:08:42,466


218
00:08:42,466 --> 00:08:48,166
So again what do we get? We get the gcd of 735 
and 504 is equal to the gcd of 504 and 231,

219
00:08:48,166 --> 00:08:52,166
and then again we do it again. So the 
idea is that this number goes here,

220
00:08:52,166 --> 00:08:53,133


221
00:08:53,133 --> 00:08:56,166
and this number goes 
here, and then we repeat.

222
00:08:56,166 --> 00:09:00,166
This number goes here, 
and this 231 goes here,

223
00:09:00,166 --> 00:09:02,666
and we keep going through this 
with the division algorithm,

224
00:09:02,666 --> 00:09:04,833
and we see by doing this, our numbers 
are getting smaller and smaller

225
00:09:04,833 --> 00:09:08,833
and smaller and eventually we're 
going hit the gcd of 21 and 0.

226
00:09:08,833 --> 00:09:11,866
So eventually 0 will appear. I'll
leave that as something to think about.

227
00:09:11,866 --> 00:09:15,733
Why does 0 have to always appear? That
comes from the division algorithm though.

228
00:09:15,733 --> 00:09:19,466
When we get to there, we know what
the gcd is, right? It's just the non-zero
number,

229
00:09:19,466 --> 00:09:21,800
which is 21. That was 
on the previous slide.

230
00:09:21,800 --> 00:09:23,100


231
00:09:23,100 --> 00:09:25,533
And that's basically the
Euclidean Algorithm.

232
00:09:25,533 --> 00:09:27,433
Now the second part of 
the Euclidean Algorithm

233
00:09:27,433 --> 00:09:29,466
that we talked about 
was back substitution.

234
00:09:29,466 --> 00:09:31,800
Now back substitution 
answers this other question.

235
00:09:31,800 --> 00:09:33,966
So this slide’s very, 
very hectic but

236
00:09:33,966 --> 00:09:35,700
it's okay.

237
00:09:35,700 --> 00:09:39,300
So one question that we might want to know 
the answer to, and we'll see why in a little bit,

238
00:09:39,300 --> 00:09:41,133
this actually helps us to 
prove Euclid's Lemma,

239
00:09:41,133 --> 00:09:46,300
we might want to find x and 
y such that 1239, 735…

240
00:09:46,300 --> 00:09:48,166
or so 100… oh sorry,

241
00:09:48,166 --> 00:09:52,600
we might want to find x and y integers
such that 1239x plus 735y is

242
00:09:52,600 --> 00:09:56,166
equal to the greatest common 
divisor of 1239 and 735.

243
00:09:56,166 --> 00:09:57,233


244
00:09:57,233 --> 00:10:00,700
So from before, this is 
just the previous slide.

245
00:10:00,700 --> 00:10:02,366
The content on the left.

246
00:10:02,366 --> 00:10:04,233


247
00:10:04,233 --> 00:10:07,400
And on the right, what we're going to 
do is we're going to start with the 21,

248
00:10:07,400 --> 00:10:10,400
so that's the greatest common 
divisor that we figured out,

249
00:10:10,400 --> 00:10:12,233
and what we're going to do is 
we're going to back substitute. So

250
00:10:12,233 --> 00:10:14,733
we're going to keep isolating
for the remainders,

251
00:10:14,733 --> 00:10:18,766
and substituting those in to 
the previous steps, okay?

252
00:10:18,766 --> 00:10:22,266
So step one is just isolate 
the remainder, that's easy,

253
00:10:22,266 --> 00:10:26,866
and step two now is okay well we have this 
42 here, and 42 was the previous remainder,

254
00:10:26,866 --> 00:10:29,333
so we're going to isolate for the 
previous remainder: so we get

255
00:10:29,333 --> 00:10:31,700
42 is equal to 504 times 1,

256
00:10:31,700 --> 00:10:34,866
plus 231 times negative 2,

257
00:10:34,866 --> 00:10:36,866
and we're going to 
substitute that in.

258
00:10:36,866 --> 00:10:38,033


259
00:10:38,033 --> 00:10:40,166
And then we're going 
to keep going, okay?

260
00:10:40,166 --> 00:10:41,200


261
00:10:41,200 --> 00:10:42,800


262
00:10:42,800 --> 00:10:47,433
Let's take a look at this step. So 42 is 
equal to that, that we said from before,

263
00:10:47,433 --> 00:10:50,033
now I'm going to take the 
minus 5 and distribute it in,

264
00:10:50,033 --> 00:10:53,900
so I'll do that once very slowly, 
so 231 times 1 that comes down

265
00:10:53,900 --> 00:10:58,333
plus 504 times 1, times negative 
5, that's 504 times negative 5.

266
00:10:58,333 --> 00:11:02,966
231 times negative 2, times negative 
5, that's going to be 10, right?

267
00:11:02,966 --> 00:11:07,500
This is going to distribute, so the negative 5
distributes to that term in the bracket,

268
00:11:07,500 --> 00:11:12,033
and the negative 5 distributes to that term 
in the bracket. That's what's happening there.

269
00:11:12,033 --> 00:11:16,000
Adding, so 1 plus 10 is 11, 
so I have 11 versions of 231,

270
00:11:16,000 --> 00:11:18,300
and I have negative 
5 versions of 504.

271
00:11:18,300 --> 00:11:20,766
Now again I do the same 
argument with 231. So

272
00:11:20,766 --> 00:11:24,166
isolate for 231, substitute that in.

273
00:11:24,166 --> 00:11:27,100
Then I take the 11 and 
bring it into each term,

274
00:11:27,100 --> 00:11:30,600
and then I'm going to add it to the 504 
times negative 5, so I'm going to get 

275
00:11:30,600 --> 00:11:32,733
11 copies of 735, and

276
00:11:32,733 --> 00:11:36,466
negative 11 minus 5 
negative 16 copies of 504.

277
00:11:36,466 --> 00:11:38,900
Then with the 504, I'm going 
to do it again. I’m going

278
00:11:38,900 --> 00:11:41,533
to isolate my 
remainder in step one,

279
00:11:41,533 --> 00:11:44,166
plug it in, simplify, and I get
the following equation.

280
00:11:44,166 --> 00:11:45,300


281
00:11:45,300 --> 00:11:47,366
Something to mention here 
is that your textbook also

282
00:11:47,366 --> 00:11:49,766
refers to this as a 
Certificate of Correctness.

283
00:11:49,766 --> 00:11:52,166
So on every step, you can 
actually make sure that

284
00:11:52,166 --> 00:11:55,966
you're doing the computations correctly, right? 
There's no reason to get this computation wrong.

285
00:11:55,966 --> 00:11:58,966
At any step you can check your 
answer by just multiplying it out,

286
00:11:58,966 --> 00:12:01,566
making sure that 
I always get 21.

287
00:12:01,566 --> 00:12:03,433
And if you don't then
you made a mistake.

288
00:12:03,433 --> 00:12:05,166
So this is a good way to 
double check your answer

289
00:12:05,166 --> 00:12:07,399
when you're doing 
your homework.