1
00:00:00,000 --> 00:00:04,833
Hello everyone. In this video, we're going
to talk about a problem that we did

2
00:00:04,833 --> 00:00:06,766
as a clicker question,

3
00:00:06,766 --> 00:00:09,700
and it's the following CRT problem.

4
00:00:09,700 --> 00:00:12,600
I've slightly modified the numbers, 
but the idea will be the same.

5
00:00:12,600 --> 00:00:16,000
Find the number of integer solutions
to x is congruent to 5 mod 17

6
00:00:16,000 --> 00:00:18,600
and 2x is congruent to 3 mod 11. 

7
00:00:18,600 --> 00:00:19,866


8
00:00:19,866 --> 00:00:21,633
Okay.

9
00:00:21,633 --> 00:00:24,933
Again, I advise trying the problem out
first and then watching the video

10
00:00:24,933 --> 00:00:26,200


11
00:00:26,200 --> 00:00:27,900
if you get stuck.

12
00:00:27,900 --> 00:00:31,300
So in this case, what are we doing?

13
00:00:31,300 --> 00:00:34,600
How are we going to do it? We have 
two options, right? Option 1 is we can -

14
00:00:34,600 --> 00:00:37,900
well we have lots of options, let me
throw out a couple of options though.

15
00:00:37,900 --> 00:00:42,633
Option 1 is to take x is congruent to 5, 
and write this as x equals 5 plus 17k,

16
00:00:42,633 --> 00:00:43,533


17
00:00:43,533 --> 00:00:46,600
plug that into the second equation, solve,

18
00:00:46,600 --> 00:00:49,233
in the end we're going to get 
some solution that's unique

19
00:00:49,233 --> 00:00:51,733
mod 17 times 11,

20
00:00:51,733 --> 00:00:53,533
and we can run through that.

21
00:00:53,533 --> 00:00:54,500


22
00:00:54,500 --> 00:00:56,433
Option 2,

23
00:00:56,433 --> 00:01:00,000
we can take the second equation 
and we can modify it so that it

24
00:01:00,000 --> 00:01:03,033
looks like it's of the form for the 
Chinese Remainder Theorem,

25
00:01:03,033 --> 00:01:06,933
and then we have two 
options. 1, solve it explicitly 

26
00:01:06,933 --> 00:01:11,700
or 2, note that a solution must 
exist since 17 and 11 are co-prime.

27
00:01:11,700 --> 00:01:14,466
If 17 and 11 weren't co-prime,

28
00:01:14,466 --> 00:01:18,366
then you would have to go down that first route 
where you just make x equal to 5 plus 17k,

29
00:01:18,366 --> 00:01:21,566
plug it into the second one,
rearrange, and hope for the best,

30
00:01:21,566 --> 00:01:22,233


31
00:01:22,233 --> 00:01:24,833
but here we have a couple options. 
So let's do the second option.

32
00:01:24,833 --> 00:01:27,700
Let's change this into something with the 
form of Chinese Remainder Theorem.

33
00:01:27,700 --> 00:01:30,766
So textbf, solution.

34
00:01:30,766 --> 00:01:33,466


35
00:01:33,466 --> 00:01:35,500
So here,

36
00:01:35,500 --> 00:01:36,966


37
00:01:36,966 --> 00:01:39,500
with the second equation, 
what do we want to do?

38
00:01:39,500 --> 00:01:40,866


39
00:01:40,866 --> 00:01:44,200
Well we want to write this as x is 
congruent to something mod 11, right?

40
00:01:44,200 --> 00:01:48,100
And so the way to do that is to invert 2. 
So we're going to try to find the number

41
00:01:48,100 --> 00:01:50,066
that when I multiply

42
00:01:50,066 --> 00:01:52,833
2 by something, I'm going to get 1.

43
00:01:52,833 --> 00:01:54,266


44
00:01:54,266 --> 00:01:56,800
If you think about it, 2 times 2 is -

45
00:01:56,800 --> 00:02:00,866
2 times 1 is 2, it's not 1. 
2 times 2 is 4, it's not 1,

46
00:02:00,866 --> 00:02:02,700
6, 8,

47
00:02:02,700 --> 00:02:05,100
now 10. 2 times 2 is -

48
00:02:05,100 --> 00:02:07,066
or 2 times 5 is 10,

49
00:02:07,066 --> 00:02:09,866
and 10 is the same as negative 1 mod 11.

50
00:02:09,866 --> 00:02:14,200
So if I use negative 5, which is 6,

51
00:02:14,200 --> 00:02:16,466
so 2 times [6] which is 12,

52
00:02:16,466 --> 00:02:19,100
and reduce that mod 11 I should get 1.

53
00:02:19,100 --> 00:02:22,766
So solution, notice that…

54
00:02:22,766 --> 00:02:28,233


55
00:02:28,233 --> 00:02:33,933
and so multiplying both sides of equation 2…

56
00:02:33,933 --> 00:02:34,833


57
00:02:34,833 --> 00:02:37,000
as follows.

58
00:02:37,000 --> 00:02:39,733
Oh, sorry. Opened a new tab.

59
00:02:39,733 --> 00:02:41,866


60
00:02:41,866 --> 00:02:44,333
Command s, not command t. Okay.

61
00:02:44,333 --> 00:02:45,433


62
00:02:45,433 --> 00:02:48,033
So since 2 times 6 is 1 mod 11 and

63
00:02:48,033 --> 00:02:52,833
multiply both sides of equation 2 
by 6 gives the equivalent system…

64
00:02:52,833 --> 00:02:53,533


65
00:02:53,533 --> 00:02:55,500
probably not 17,

66
00:02:55,500 --> 00:02:58,866
but so 6 times 2 is 12, 12 is 1,

67
00:02:58,866 --> 00:03:01,366
so that's the same as that, 
and then 6 times 3 is 18,

68
00:03:01,366 --> 00:03:05,766
and 18 mod 11 is 7 not 
17 so let's change 17.

69
00:03:05,766 --> 00:03:07,500


70
00:03:07,500 --> 00:03:09,500
So great, okay.

71
00:03:09,500 --> 00:03:11,500


72
00:03:11,500 --> 00:03:14,433
The Chinese Remainder Theorem

73
00:03:14,433 --> 00:03:16,466
now says that

74
00:03:16,466 --> 00:03:18,933
there is a unique

75
00:03:18,933 --> 00:03:21,833


76
00:03:21,833 --> 00:03:24,366
solution modulo 

77
00:03:24,366 --> 00:03:27,600


78
00:03:27,600 --> 00:03:33,000
17 times 11, which is…187?

79
00:03:33,000 --> 00:03:35,500
Does that sound right? That sounds good.

80
00:03:35,500 --> 00:03:37,866


81
00:03:37,866 --> 00:03:42,600
So the Chinese Remainder Theorem now says 
that there's a unique solution modulo [187].

82
00:03:42,600 --> 00:03:46,033
So I should maybe mention why I can 
use the Chinese Remainder - valid since

83
00:03:46,033 --> 00:03:49,533
the gcd of 11 and 17 is equal to 1.

84
00:03:49,533 --> 00:03:54,466


85
00:03:54,466 --> 00:03:56,966
Okay, great.

86
00:03:56,966 --> 00:03:59,166
So now we know there's a unique solution

87
00:03:59,166 --> 00:04:00,233


88
00:04:00,233 --> 00:04:03,233
modulo 187, okay?

89
00:04:03,233 --> 00:04:07,766
So now we'd like to know all the total
solutions between negative 1500 and 1500.

90
00:04:07,766 --> 00:04:09,766
This is a range of…

91
00:04:09,766 --> 00:04:11,633


92
00:04:11,633 --> 00:04:15,300
okay, so let's be exact here, okay? So...

93
00:04:15,300 --> 00:04:17,900
so we want to know…

94
00:04:17,900 --> 00:04:20,400
let's give the solution a name.

95
00:04:20,400 --> 00:04:22,733


96
00:04:22,733 --> 00:04:24,766
Call this solution a.

97
00:04:24,766 --> 00:04:27,233


98
00:04:27,233 --> 00:04:31,400
Hence, all solutions are given by

99
00:04:31,400 --> 00:04:34,366


100
00:04:34,366 --> 00:04:38,000
x is equal to a plus 187k,

101
00:04:38,000 --> 00:04:40,800


102
00:04:40,800 --> 00:04:44,133
where k is an integer.

103
00:04:44,133 --> 00:04:47,100


104
00:04:47,100 --> 00:04:49,866
So all solutions to this

105
00:04:49,866 --> 00:04:53,600
are given by x is equal to a plus 187k.

106
00:04:53,600 --> 00:04:56,700


107
00:04:56,700 --> 00:05:00,200
Where k is an integer, I guess we 
should maybe be precise. Okay,

108
00:05:00,200 --> 00:05:02,666
do you want to solve this? Yeah 
maybe we should solve this.

109
00:05:02,666 --> 00:05:03,733


110
00:05:03,733 --> 00:05:07,000
Can we eyeball the solution? Nah, you 
know what? Let's not eyeball the solution,

111
00:05:07,000 --> 00:05:10,400
let's just actually do it. Well 
okay I guess actually…

112
00:05:10,400 --> 00:05:11,533


113
00:05:11,533 --> 00:05:15,366
yeah that's actually it. So in class, the 
5 and the 7 ended up being equal

114
00:05:15,366 --> 00:05:17,033
and here they're not.

115
00:05:17,033 --> 00:05:17,900


116
00:05:17,900 --> 00:05:21,266
what are we going to do? Let’s…

117
00:05:21,266 --> 00:05:21,900


118
00:05:21,900 --> 00:05:23,766


119
00:05:23,766 --> 00:05:27,500
what do I want to do? Do I really want to go through 
it? Yeah let's go through it, what the heck, okay.

120
00:05:27,500 --> 00:05:32,800


121
00:05:32,800 --> 00:05:34,933
To find a,

122
00:05:34,933 --> 00:05:37,866
we use the fact that

123
00:05:37,866 --> 00:05:42,933
x is equal to 5 plus 17l,

124
00:05:42,933 --> 00:05:43,666


125
00:05:43,666 --> 00:05:45,933
for some integer l,

126
00:05:45,933 --> 00:05:49,266


127
00:05:49,266 --> 00:05:54,200
and plug into the second equation to yield

128
00:05:54,200 --> 00:05:59,866


129
00:05:59,866 --> 00:06:04,200
5 plus 17l is equivalent to 7

130
00:06:04,200 --> 00:06:05,233


131
00:06:05,233 --> 00:06:07,166
mod 11.

132
00:06:07,166 --> 00:06:08,733


133
00:06:08,733 --> 00:06:10,833
So we're going to use the fact

134
00:06:10,833 --> 00:06:11,433


135
00:06:11,433 --> 00:06:15,833
that well if x is congruent to 5 mod 17,
that means that x is equal to 5 plus 17l

136
00:06:15,833 --> 00:06:19,066
for some integer l. I'm going to plug that into 
the second equation, what are we going to get?

137
00:06:19,066 --> 00:06:22,933
We're going to get 5 plus
17l is congruent to 7 mod 11.

138
00:06:22,933 --> 00:06:24,000


139
00:06:24,000 --> 00:06:26,600
Simplifying gives… 

140
00:06:26,600 --> 00:06:28,700


141
00:06:28,700 --> 00:06:31,800
so 17 is the same as 6,

142
00:06:31,800 --> 00:06:32,866


143
00:06:32,866 --> 00:06:35,900
and this is equivalent to 2 mod 11.

144
00:06:35,900 --> 00:06:38,933


145
00:06:38,933 --> 00:06:41,066


146
00:06:41,066 --> 00:06:43,266
We can use

147
00:06:43,266 --> 00:06:45,500
Congruences

148
00:06:45,500 --> 00:06:47,100


149
00:06:47,100 --> 00:06:50,533
and Divisibility from our course.

150
00:06:50,533 --> 00:06:52,566


151
00:06:52,566 --> 00:06:56,333


152
00:06:56,333 --> 00:06:58,466
We can divide by 2,

153
00:06:58,466 --> 00:06:59,666


154
00:06:59,666 --> 00:07:02,133
since the gcd of 2 and 11 is 1.

155
00:07:02,133 --> 00:07:05,800


156
00:07:05,800 --> 00:07:07,500
To get that…

157
00:07:07,500 --> 00:07:10,266
actually I don't even want to 
do that, yeah maybe I do.

158
00:07:10,266 --> 00:07:14,933


159
00:07:14,933 --> 00:07:18,433
So we're going to get that 3l 
is equivalent to 1 mod 11.

160
00:07:18,433 --> 00:07:21,800


161
00:07:21,800 --> 00:07:24,366
Multiplying by 4

162
00:07:24,366 --> 00:07:26,933


163
00:07:26,933 --> 00:07:30,566


164
00:07:30,566 --> 00:07:33,900
gives us that well 12l - so…

165
00:07:33,900 --> 00:07:38,400


166
00:07:38,400 --> 00:07:40,866
gives us that l is congruent to 

167
00:07:40,866 --> 00:07:41,700


168
00:07:41,700 --> 00:07:43,800
4 mod 11.

169
00:07:43,800 --> 00:07:46,933
So 11 is equal to 4 plus 11m.

170
00:07:46,933 --> 00:07:50,933


171
00:07:50,933 --> 00:07:53,400


172
00:07:53,400 --> 00:07:55,566
For some integer m.

173
00:07:55,566 --> 00:07:58,933


174
00:07:58,933 --> 00:08:01,000


175
00:08:01,000 --> 00:08:04,166
Plugging back in yields x is equal to 5

176
00:08:04,166 --> 00:08:07,466
plus 17 [times] 4 plus 11m,

177
00:08:07,466 --> 00:08:09,833


178
00:08:09,833 --> 00:08:15,000
giving x is equal to 17 times 4,

179
00:08:15,000 --> 00:08:19,200
68, 73, 73 plus 187m.

180
00:08:19,200 --> 00:08:22,933


181
00:08:22,933 --> 00:08:25,033


182
00:08:25,033 --> 00:08:28,800
Alright, excellent. So we 
know what the answer is.

183
00:08:28,800 --> 00:08:33,133
Well we know that x is 
equal to 73 plus 187m. So

184
00:08:33,133 --> 00:08:36,066


185
00:08:36,066 --> 00:08:40,666
now let's plug it into the condition, 
right? So we have bounds on x, 

186
00:08:40,666 --> 00:08:43,433
right, which are given by

187
00:08:43,433 --> 00:08:44,133


188
00:08:44,133 --> 00:08:46,100
negative 1500 to 1500.

189
00:08:46,100 --> 00:08:47,833


190
00:08:47,833 --> 00:08:51,166
So x is [between] negative 
1500 and 1500, and -

191
00:08:51,166 --> 00:08:54,400
oh by the way, I guess before we go on, we 
should always double check our answer, right?

192
00:08:54,400 --> 00:08:57,433
So x is equal to 73 plus 187m.

193
00:08:57,433 --> 00:09:01,400
So let's just plug that into here, so 73

194
00:09:01,400 --> 00:09:05,733
minus 7 is 66,

195
00:09:05,733 --> 00:09:10,566
which is divisible by 11, so 
that’s good. 73 minus 5 is 68,

196
00:09:10,566 --> 00:09:15,200
and I'm hoping that 4 times 
17 is 68, I believe it is.

197
00:09:15,200 --> 00:09:16,700
So, fantastic, okay.

198
00:09:16,700 --> 00:09:19,366
So this actually is the solution, and the
Chinese Remainder Theorem says that

199
00:09:19,366 --> 00:09:22,133
of this form gives us all solutions.

200
00:09:22,133 --> 00:09:26,566
So since this is the case, 
I can plug in this x value.

201
00:09:26,566 --> 00:09:27,633


202
00:09:27,633 --> 00:09:28,666


203
00:09:28,666 --> 00:09:32,166
So x is 73 plus 187m.

204
00:09:32,166 --> 00:09:35,500


205
00:09:35,500 --> 00:09:37,233


206
00:09:37,233 --> 00:09:40,633
Simplifying yields - so if I 
subtract 73 from either side,

207
00:09:40,633 --> 00:09:43,133
I get negative 1573 is less than

208
00:09:43,133 --> 00:09:46,433
187m, which is less than

209
00:09:46,433 --> 00:09:48,366


210
00:09:48,366 --> 00:09:51,766
1427, let’s see if that looks good.

211
00:09:51,766 --> 00:09:54,200


212
00:09:54,200 --> 00:09:56,000
Let’s see what we have here.

213
00:09:56,000 --> 00:09:59,833
So since x is bounded in 
this range, we have that

214
00:09:59,833 --> 00:10:04,366
negative 1573 is less 
than 187[m] is less than

215
00:10:04,366 --> 00:10:06,166
1427.

216
00:10:06,166 --> 00:10:08,733
I'm subtracting 73 from either number.

217
00:10:08,733 --> 00:10:10,400
That looks good.

218
00:10:10,400 --> 00:10:13,600
Now the question is how
many times is 187…

219
00:10:13,600 --> 00:10:14,933


220
00:10:14,933 --> 00:10:17,833
or how many multiples
187 lie in this range?

221
00:10:17,833 --> 00:10:20,666


222
00:10:20,666 --> 00:10:24,933
So if we think about it, do I 
want to do this by hand or not?

223
00:10:24,933 --> 00:10:28,933
I mean, 187 times 10 is [1870],

224
00:10:28,933 --> 00:10:29,566


225
00:10:29,566 --> 00:10:32,833
and then I'd have to subtract 
a couple multiples of 187.

226
00:10:32,833 --> 00:10:34,366


227
00:10:34,366 --> 00:10:38,166
Am I in the mood to do this or do I 
just want to pull up the old calculator?

228
00:10:38,166 --> 00:10:40,633


229
00:10:40,633 --> 00:10:45,333
187 times 7, 9, 4, 0…

230
00:10:45,333 --> 00:10:48,266
you know what, let's just do it 
just so that it's easier to see.

231
00:10:48,266 --> 00:10:49,533


232
00:10:49,533 --> 00:10:52,400
The odds of me doing it correctly on a
video are probably pretty small anyways.

233
00:10:52,400 --> 00:10:55,133
Okay, so 187,

234
00:10:55,133 --> 00:10:59,733
how many times does it go into
these numbers? So 1427

235
00:10:59,733 --> 00:11:02,033
divided by 187,

236
00:11:02,033 --> 00:11:03,966


237
00:11:03,966 --> 00:11:05,733
7 times.

238
00:11:05,733 --> 00:11:07,000


239
00:11:07,000 --> 00:11:09,800
So let's simplify once more.

240
00:11:09,800 --> 00:11:11,233


241
00:11:11,233 --> 00:11:11,600


242
00:11:11,600 --> 00:11:12,633


243
00:11:12,633 --> 00:11:17,500
So 7.63, so m is definitely less than 7.6,

244
00:11:17,500 --> 00:11:18,300


245
00:11:18,300 --> 00:11:21,166
and let's go the other way, 1573

246
00:11:21,166 --> 00:11:23,200


247
00:11:23,200 --> 00:11:26,333
divided by 187,

248
00:11:26,333 --> 00:11:27,233


249
00:11:27,233 --> 00:11:29,333
8.4.

250
00:11:29,333 --> 00:11:30,700


251
00:11:30,700 --> 00:11:33,933
So this is going to be - so 
m is going to be at least…

252
00:11:33,933 --> 00:11:35,700


253
00:11:35,700 --> 00:11:38,433
whatever, at least negative 8.3.

254
00:11:38,433 --> 00:11:39,166


255
00:11:39,166 --> 00:11:42,166
Fantastic. So how many integers is this?

256
00:11:42,166 --> 00:11:45,166


257
00:11:45,166 --> 00:11:46,466


258
00:11:46,466 --> 00:11:49,133
What is that? There’s…so what is this?

259
00:11:49,133 --> 00:11:51,133
It’s between 7 and 
negative 8 as an integer,

260
00:11:51,133 --> 00:11:53,800
so 7 minus negative 8 is 15

261
00:11:53,800 --> 00:11:56,100
plus 1 is 16. So hence,

262
00:11:56,100 --> 00:11:57,666


263
00:11:57,666 --> 00:11:59,633
there are 16 integers.

264
00:11:59,633 --> 00:12:01,966


265
00:12:01,966 --> 00:12:04,866
So on an exam, you should expect 
that the numbers work out a lot nicer.

266
00:12:04,866 --> 00:12:09,466
So for example, in the clicker
question that we did for this week,

267
00:12:09,466 --> 00:12:10,200


268
00:12:10,200 --> 00:12:13,166
the numbers turned out a 
lot nicer than they did here.

269
00:12:13,166 --> 00:12:16,466
Here I did use a calculator just 
to keep my life a little easier.

270
00:12:16,466 --> 00:12:17,200


271
00:12:17,200 --> 00:12:21,166
Okay so let's take a step back and 
let's go through what we did, okay?

272
00:12:21,166 --> 00:12:22,266


273
00:12:22,266 --> 00:12:25,233
So we started with the system 
x is congruent to 5 mod 17

274
00:12:25,233 --> 00:12:28,200
and 2x is congruent to 3 mod 11.

275
00:12:28,200 --> 00:12:32,566


276
00:12:32,566 --> 00:12:35,800
By simplifying the second equation,
or finding the inverse of 2,

277
00:12:35,800 --> 00:12:40,466
we saw this is equivalent to x is congruent to
5 mod 17, and x is congruent to 7 mod 11.

278
00:12:40,466 --> 00:12:43,333
We use the Chinese Remainder
Theorem to find our solution

279
00:12:43,333 --> 00:12:44,566


280
00:12:44,566 --> 00:12:48,066
that was given by 73 plus 187m 

281
00:12:48,066 --> 00:12:50,533
where m ranges over the 
integers, any of these will work

282
00:12:50,533 --> 00:12:55,266
because 187 is 11 times 17, 
and that’s congruent to 0

283
00:12:55,266 --> 00:12:57,200
mod 17 and mod 11.

284
00:12:57,200 --> 00:12:59,100


285
00:12:59,100 --> 00:13:01,833
Plug it in, simplify,

286
00:13:01,833 --> 00:13:03,066


287
00:13:03,066 --> 00:13:05,533
and when you get to this point, you either

288
00:13:05,533 --> 00:13:08,466
guess and check, or use 
a calculator like I did,

289
00:13:08,466 --> 00:13:10,666
find out there are only 16 integers.

290
00:13:10,666 --> 00:13:11,466


291
00:13:11,466 --> 00:13:14,000
So this gives you a little
bit of practice with

292
00:13:14,000 --> 00:13:17,166
the Chinese Remainder Theorem 
with these types of arguments.

293
00:13:17,166 --> 00:13:18,000


294
00:13:18,000 --> 00:13:19,933
That I think is all I have to say.

295
00:13:19,933 --> 00:13:24,633
Thank you very much for your time,
and hopefully this helps you out.