1
00:00:00,633 --> 00:00:04,500
Hello everyone. In this video, I'd like 
to talk about the following problem.

2
00:00:04,500 --> 00:00:07,400
Let a, b, c be integers 
such that c divides a b,

3
00:00:07,400 --> 00:00:11,000
and show that c divides 
the product of the gcds

4
00:00:11,000 --> 00:00:11,600


5
00:00:11,600 --> 00:00:14,433
of a and c, and the gcd of b and c.

6
00:00:14,433 --> 00:00:16,166


7
00:00:16,166 --> 00:00:20,300
I really would suggest, recommend,

8
00:00:20,300 --> 00:00:23,066
strongly suggest that you stop the video now

9
00:00:23,066 --> 00:00:27,066
and actually try this problem out. Try a couple 
of things and see what you come up with.

10
00:00:27,066 --> 00:00:28,866


11
00:00:28,866 --> 00:00:31,733
Then hopefully once you've tried a 
couple of things, watching this video

12
00:00:31,733 --> 00:00:34,466
might give you a little bit of insight
to some of the things that I tried,

13
00:00:34,466 --> 00:00:37,100
got wrong, and then had to correct.

14
00:00:37,100 --> 00:00:38,333


15
00:00:38,333 --> 00:00:41,166
So it might be worth it to 
take a minute to do that

16
00:00:41,166 --> 00:00:44,200
and then come back to the video.

17
00:00:44,200 --> 00:00:46,733


18
00:00:46,733 --> 00:00:49,066
Now I wanted to show this example

19
00:00:49,066 --> 00:00:49,800


20
00:00:49,800 --> 00:00:53,933
and I want to do it sort of 
stream of consciousness,

21
00:00:53,933 --> 00:00:55,466


22
00:00:55,466 --> 00:00:58,966
which is going to be hard to do because 
I've already solved this question,

23
00:00:58,966 --> 00:01:03,200
but that being said I want to try to talk about my 
thought process when I first went through this question.

24
00:01:03,200 --> 00:01:04,733


25
00:01:04,733 --> 00:01:07,600
My thought process went a 
little something like this: so

26
00:01:07,600 --> 00:01:12,266
I started off with the assumption 
that okay well c divides a b so

27
00:01:12,266 --> 00:01:13,166


28
00:01:13,166 --> 00:01:16,000
since c divides a b,

29
00:01:16,000 --> 00:01:19,700
there exists an integer

30
00:01:19,700 --> 00:01:23,666
k such that c k equals a b.

31
00:01:23,666 --> 00:01:25,333


32
00:01:25,333 --> 00:01:28,166
So this is how I started, c divides a b so

33
00:01:28,166 --> 00:01:30,133


34
00:01:30,133 --> 00:01:33,233
there exists an integer k 
such that c k equals a b.

35
00:01:33,233 --> 00:01:34,100


36
00:01:34,100 --> 00:01:35,533
I got to here,

37
00:01:35,533 --> 00:01:39,133
I looked and I said, “okay this
is true, but now the problem is

38
00:01:39,133 --> 00:01:40,133


39
00:01:40,133 --> 00:01:41,600
that I don't

40
00:01:41,600 --> 00:01:46,133
really know how to get from here
to some sort of gcd statement.”

41
00:01:46,133 --> 00:01:48,300
So I sat, I looked at this for a little bit,

42
00:01:48,300 --> 00:01:51,066
and I wasn't sure what to do.

43
00:01:51,066 --> 00:01:52,900


44
00:01:52,900 --> 00:01:56,400
So when I was stuck I said, “okay well 
I'm just going to get rid of this idea.”

45
00:01:56,400 --> 00:01:58,033


46
00:01:58,033 --> 00:02:02,466
Didn't work, it seems like a reasonable 
place to start but it's not going to help me.

47
00:02:02,466 --> 00:02:03,933


48
00:02:03,933 --> 00:02:06,700
So instead of doing that, let’s try to 
deal with one of the gcd conditions.

49
00:02:06,700 --> 00:02:09,633
So let's deal with the gcd of a and c, okay?

50
00:02:09,633 --> 00:02:13,400
I start at the gcd of a and c, that doesn't 
really give me much on its own,

51
00:02:13,400 --> 00:02:15,733
so I need to get some other 
variables involved and I thought

52
00:02:15,733 --> 00:02:19,400
well okay let’s try to use Bézout’s Lemma 
or the Extended Euclidean Algorithm.

53
00:02:19,400 --> 00:02:20,300


54
00:02:20,300 --> 00:02:22,600
So by Bézout’s Lemma,

55
00:02:22,600 --> 00:02:23,266


56
00:02:23,266 --> 00:02:25,066
EEA in the notes,

57
00:02:25,066 --> 00:02:25,800


58
00:02:25,800 --> 00:02:31,500
there exists integers x and y such that

59
00:02:31,500 --> 00:02:34,233


60
00:02:34,233 --> 00:02:38,700
a x plus c y is equal to 
the gcd of a and c.

61
00:02:38,700 --> 00:02:42,433


62
00:02:42,433 --> 00:02:46,833
Okay, that’s a reasonable starting point. 
So now I have some of the things I need,

63
00:02:46,833 --> 00:02:47,733


64
00:02:47,733 --> 00:02:52,066
some of the terms are here, this is
looking like there's some potential here.

65
00:02:52,066 --> 00:02:56,666


66
00:02:56,666 --> 00:02:59,366
Now I have that c divides a b,

67
00:02:59,366 --> 00:03:00,033


68
00:03:00,033 --> 00:03:02,600
but there's no b’s here so 
maybe I should include them.

69
00:03:02,600 --> 00:03:05,100
So let's multiply by b.

70
00:03:05,100 --> 00:03:08,000


71
00:03:08,000 --> 00:03:11,266


72
00:03:11,266 --> 00:03:14,666
Okay so what am I going to 
get when I multiply by b?

73
00:03:14,666 --> 00:03:15,533


74
00:03:15,533 --> 00:03:19,266
So I get a b x plus c b y is equal to

75
00:03:19,266 --> 00:03:21,933
b times the gcd of a and c.

76
00:03:21,933 --> 00:03:23,300


77
00:03:23,300 --> 00:03:26,300
This is good, now let's use 
the fact that c divides a b.

78
00:03:26,300 --> 00:03:28,733
So c divides a b x,

79
00:03:28,733 --> 00:03:31,900


80
00:03:31,900 --> 00:03:36,800
so c divides a b, and c divides

81
00:03:36,800 --> 00:03:37,466


82
00:03:37,466 --> 00:03:39,566
c

83
00:03:39,566 --> 00:03:42,166


84
00:03:42,166 --> 00:03:45,933
so by Divisibility

85
00:03:45,933 --> 00:03:48,966


86
00:03:48,966 --> 00:03:51,566
of Integer Combinations,

87
00:03:51,566 --> 00:03:54,633


88
00:03:54,633 --> 00:03:59,466
c divides a b x plus c b y which is equal to

89
00:03:59,466 --> 00:04:01,700


90
00:04:01,700 --> 00:04:05,700
b gcd of a and c.

91
00:04:05,700 --> 00:04:07,133


92
00:04:07,133 --> 00:04:10,466
By the way I don't know where 
this is going, but at least

93
00:04:10,466 --> 00:04:12,600
I'm getting there.

94
00:04:12,600 --> 00:04:13,266


95
00:04:13,266 --> 00:04:16,266
So c divides b times the gcd of a and c.

96
00:04:16,266 --> 00:04:19,100
Let me put this in brackets,

97
00:04:19,100 --> 00:04:20,133


98
00:04:20,133 --> 00:04:22,166
one more little fix. Okay?

99
00:04:22,166 --> 00:04:23,900


100
00:04:23,900 --> 00:04:27,500
How do I know this is going to work? I don’t. I was 
kind of going through this blindly and I got to this,

101
00:04:27,500 --> 00:04:29,200
okay, so c divides

102
00:04:29,200 --> 00:04:31,266
b times the gcd of a and c.

103
00:04:31,266 --> 00:04:33,966


104
00:04:33,966 --> 00:04:36,333
Now I need the gcd of 
b and c to show up.

105
00:04:36,333 --> 00:04:39,400


106
00:04:39,400 --> 00:04:41,233
And I know that

107
00:04:41,233 --> 00:04:43,566
the gcd of b and c divides b,

108
00:04:43,566 --> 00:04:43,933


109
00:04:43,933 --> 00:04:43,966
so what do I know? So then since…

110
00:04:43,966 --> 00:04:44,166


111
00:04:44,166 --> 00:04:46,800
Now I'm going to write b as

112
00:04:46,800 --> 00:04:48,533


113
00:04:48,533 --> 00:04:51,600
k times the gcd of b and 
c for some integer k,

114
00:04:51,600 --> 00:04:54,400
possible since

115
00:04:54,400 --> 00:04:57,733
gcd of b and c divides b.

116
00:04:57,733 --> 00:04:58,266


117
00:04:58,266 --> 00:04:58,333


118
00:04:58,333 --> 00:05:00,500
So far, so good.

119
00:05:00,500 --> 00:05:00,566


120
00:05:00,566 --> 00:05:00,733


121
00:05:00,733 --> 00:05:03,366
Alright now what? Well let's plug that in.

122
00:05:03,366 --> 00:05:04,300


123
00:05:04,300 --> 00:05:04,600


124
00:05:04,600 --> 00:05:07,066
Okay well let's see what we have.

125
00:05:07,066 --> 00:05:10,266


126
00:05:10,266 --> 00:05:12,900
Substitute this above

127
00:05:12,900 --> 00:05:15,233


128
00:05:15,233 --> 00:05:17,366
and we're going to get

129
00:05:17,366 --> 00:05:19,166


130
00:05:19,166 --> 00:05:21,166
this.

131
00:05:21,166 --> 00:05:21,700


132
00:05:21,700 --> 00:05:21,733


133
00:05:21,733 --> 00:05:25,700
So let's see where we are.
c divides a b x plus c b y,

134
00:05:25,700 --> 00:05:26,900


135
00:05:26,900 --> 00:05:30,866
I guess I don't need that anymore. 
Let's just get rid of the first part.

136
00:05:30,866 --> 00:05:34,600
So c divides just k times

137
00:05:34,600 --> 00:05:36,266
gcd of b and c

138
00:05:36,266 --> 00:05:38,733
and the gcd of a and c.

139
00:05:38,733 --> 00:05:40,800


140
00:05:40,800 --> 00:05:42,900
Okay so we reach this point

141
00:05:42,900 --> 00:05:47,666
and then we see that c divides k times 
the gcd of b c times the gcd of a c,

142
00:05:47,666 --> 00:05:48,333


143
00:05:48,333 --> 00:05:52,000
but we really don't have a great 
reason to believe the gcd - 

144
00:05:52,000 --> 00:05:55,933
like really what we would you like 
to show is the gcd of c and k is 1,

145
00:05:55,933 --> 00:05:59,800
but there's no real great way to do this.

146
00:05:59,800 --> 00:06:03,500
So at this point, we're kind of in a tricky spot.

147
00:06:03,500 --> 00:06:06,133


148
00:06:06,133 --> 00:06:08,433
So we went down a wrong path,

149
00:06:08,433 --> 00:06:10,933
now we're going to have to 
backtrack and correct that.

150
00:06:10,933 --> 00:06:12,900
So how do we do that? Well

151
00:06:12,900 --> 00:06:16,600
we introduced the b by going up here, 
multiplying by b yields this, right?

152
00:06:16,600 --> 00:06:19,966
Now we made some progress but 
we got a little bit hosed at the end.

153
00:06:19,966 --> 00:06:21,366


154
00:06:21,366 --> 00:06:26,533
So let's try to remember okay we want the product 
of gcd of a and c and the gcd of b and c to appear.

155
00:06:26,533 --> 00:06:27,166


156
00:06:27,166 --> 00:06:29,033
Right?

157
00:06:29,033 --> 00:06:30,100


158
00:06:30,100 --> 00:06:33,600
And not until near the end do 
we introduce the gcd of b and c,

159
00:06:33,600 --> 00:06:36,066
so let's actually do that at an earlier step.

160
00:06:36,066 --> 00:06:39,733
So instead of multiplying by b, let's use 
Bézout’s Lemma again and see what we get.

161
00:06:39,733 --> 00:06:42,266


162
00:06:42,266 --> 00:06:45,066
So using

163
00:06:45,066 --> 00:06:48,100
Bézout’s Lemma

164
00:06:48,100 --> 00:06:48,633


165
00:06:48,633 --> 00:06:50,533
again,

166
00:06:50,533 --> 00:06:51,200


167
00:06:51,200 --> 00:06:55,666
there exist integers, let’s say u and v,

168
00:06:55,666 --> 00:06:56,566


169
00:06:56,566 --> 00:06:58,700
such that…

170
00:06:58,700 --> 00:06:59,533


171
00:06:59,533 --> 00:06:59,633


172
00:06:59,633 --> 00:07:02,900
let's say b u plus c v

173
00:07:02,900 --> 00:07:05,966
is equal to the gcd of b and c.

174
00:07:05,966 --> 00:07:06,233


175
00:07:06,233 --> 00:07:08,933
Okay so now we have these two gcds,

176
00:07:08,933 --> 00:07:11,333
let's multiply this together.

177
00:07:11,333 --> 00:07:13,033


178
00:07:13,033 --> 00:07:15,933
Multiply the previous two equations together

179
00:07:15,933 --> 00:07:21,466


180
00:07:21,466 --> 00:07:24,800
to see that a b x u

181
00:07:24,800 --> 00:07:27,633
plus a c x v

182
00:07:27,633 --> 00:07:29,533


183
00:07:29,533 --> 00:07:31,466
plus

184
00:07:31,466 --> 00:07:32,666


185
00:07:32,666 --> 00:07:35,966
b c u y

186
00:07:35,966 --> 00:07:40,400
plus c squared y v

187
00:07:40,400 --> 00:07:41,166


188
00:07:41,166 --> 00:07:43,700
is equal to the gcd of a and c

189
00:07:43,700 --> 00:07:44,733


190
00:07:44,733 --> 00:07:47,066
and the gcd of b and c.

191
00:07:47,066 --> 00:07:51,200


192
00:07:51,200 --> 00:07:53,666
So let's see what we got here.

193
00:07:53,666 --> 00:07:57,366
So multiply the previous two equations
together to see the following.

194
00:07:57,366 --> 00:07:58,433


195
00:07:58,433 --> 00:08:00,566
Okay now this looks a little bit more promising,

196
00:08:00,566 --> 00:08:02,466
right, now let's look at the left-hand side, right?

197
00:08:02,466 --> 00:08:05,466
c divides three of these values,

198
00:08:05,466 --> 00:08:07,166


199
00:08:07,166 --> 00:08:10,500
and in fact, c divides the first one 
too because c divides a b, alright.

200
00:08:10,500 --> 00:08:11,200


201
00:08:11,200 --> 00:08:13,933
So we can put it all together. Notice that 
up to this point we hadn't used the fact

202
00:08:13,933 --> 00:08:16,166
that c divides a b, but let's do that now.

203
00:08:16,166 --> 00:08:17,066


204
00:08:17,066 --> 00:08:19,300
So...

205
00:08:19,300 --> 00:08:21,533


206
00:08:21,533 --> 00:08:24,866
write c k equals a b

207
00:08:24,866 --> 00:08:26,733
for some integer k.

208
00:08:26,733 --> 00:08:28,766


209
00:08:28,766 --> 00:08:34,233
Substituting above and factoring

210
00:08:34,233 --> 00:08:36,300


211
00:08:36,300 --> 00:08:38,700
yields…

212
00:08:38,700 --> 00:08:39,233


213
00:08:39,233 --> 00:08:39,433


214
00:08:39,433 --> 00:08:41,733
exactly what we want.

215
00:08:41,733 --> 00:08:43,200


216
00:08:43,200 --> 00:08:45,600
Let's see.

217
00:08:45,600 --> 00:08:48,866
So substitute and factor, 
and now we see that c

218
00:08:48,866 --> 00:08:52,966
times some integer is equal to
the gcd of a c times the gcd b c,

219
00:08:52,966 --> 00:08:55,533
that's exactly what we needed to show. 

220
00:08:55,533 --> 00:09:01,966


221
00:09:01,966 --> 00:09:04,566
So let's just put in our concluding statement.

222
00:09:04,566 --> 00:09:06,000


223
00:09:06,000 --> 00:09:09,300
Okay so hopefully you stuck around this is a

224
00:09:09,300 --> 00:09:11,700
tricky-ish problem, but I mean, 

225
00:09:11,700 --> 00:09:15,766
you kind of just have to go through it and try a 
couple of things. Sometimes you're going to be wrong

226
00:09:15,766 --> 00:09:16,700


227
00:09:16,700 --> 00:09:19,133
and eventually

228
00:09:19,133 --> 00:09:22,466
you just kind of see it. There’s 
really no other way to explain it.

229
00:09:22,466 --> 00:09:24,100


230
00:09:24,100 --> 00:09:26,066
So how did we do this? Well

231
00:09:26,066 --> 00:09:29,133
we used Bézout’s Lemma not once but twice, 

232
00:09:29,133 --> 00:09:30,333


233
00:09:30,333 --> 00:09:32,600
multiplied these equations together,

234
00:09:32,600 --> 00:09:35,066
and we got a whole bunch of terms, 
many of them depending on c,

235
00:09:35,066 --> 00:09:37,366
and then this is extra factor a b. 

236
00:09:37,366 --> 00:09:38,200


237
00:09:38,200 --> 00:09:42,333
Writing c k equals a b for some 
integer [k], we can substitute above

238
00:09:42,333 --> 00:09:43,533


239
00:09:43,533 --> 00:09:47,166
and see that c times an integer is 
equal to the product of the gcds

240
00:09:47,166 --> 00:09:49,866
and thus c must divide the two gcds.

241
00:09:49,866 --> 00:09:50,933


242
00:09:50,933 --> 00:09:54,333
So hopefully you learned something 
about, you know, being wrong it's okay.

243
00:09:54,333 --> 00:09:58,500
Stumbling through a problem, 
all of these things are okay.

244
00:09:58,500 --> 00:10:01,266
The point is that you keep persisting

245
00:10:01,266 --> 00:10:01,966


246
00:10:01,966 --> 00:10:05,800
and hopefully something
clicks and you just kind of

247
00:10:05,800 --> 00:10:10,400
get the right sequence of statements 
to get the result that you want.

248
00:10:10,400 --> 00:10:12,700


249
00:10:12,700 --> 00:10:14,800
So I guess that's all I have to say.