1
00:00:00,000 --> 00:00:03,833
Hello everyone. In this video, 
we're going to talk about

2
00:00:03,833 --> 00:00:04,566


3
00:00:04,566 --> 00:00:09,033
CISR, so Congruent If and 
Only If Same Remainder.

4
00:00:09,033 --> 00:00:12,433
I'd like to start this video by just going 
over the statement that we have,

5
00:00:12,433 --> 00:00:13,400


6
00:00:13,400 --> 00:00:17,266
and the statement here is written: a 
is congruent to b mod m if and only if

7
00:00:17,266 --> 00:00:21,100
a and b have the same
remainder when divided by m.

8
00:00:21,100 --> 00:00:24,000
So remember this says two things, right, 
that's what the notes here are saying.

9
00:00:24,000 --> 00:00:28,266
So this comes straight from 
your…the notes for Math 135

10
00:00:28,266 --> 00:00:31,433
in the fall 2015 term.

11
00:00:31,433 --> 00:00:32,600


12
00:00:32,600 --> 00:00:35,433
So what does this statement say? So 
it says, if a is congruent to b mod m,

13
00:00:35,433 --> 00:00:37,700
then a and b have the same
remainder when divided by m.

14
00:00:37,700 --> 00:00:42,033
That's half of it, and the other half is a and b 
have the same remainder when divided by m,

15
00:00:42,033 --> 00:00:44,733
then a is congruent to b mod m.

16
00:00:44,733 --> 00:00:46,166


17
00:00:46,166 --> 00:00:50,500
So if we ever want to calculate a
congruence, it's the same as computing

18
00:00:50,500 --> 00:00:53,233
the remainder, in some sense,

19
00:00:53,233 --> 00:00:57,600
and that sense is given by this. So 
let's take a look at an actual example

20
00:00:57,600 --> 00:01:00,100
of this problem.

21
00:01:00,100 --> 00:01:02,400
So the example that I have in mind

22
00:01:02,400 --> 00:01:06,500
is does 13 divided 2 to 
the 70 plus 3 to the 70?

23
00:01:06,500 --> 00:01:07,500


24
00:01:07,500 --> 00:01:10,400
So take a couple of minutes now,

25
00:01:10,400 --> 00:01:13,833
pause the video, and actually try this problem.

26
00:01:13,833 --> 00:01:17,833
It's worth thinking about and at least 
trying to come up with a solution to this.

27
00:01:17,833 --> 00:01:19,633


28
00:01:19,633 --> 00:01:22,300
Now that you're back, hopefully you paused it,

29
00:01:22,300 --> 00:01:24,000


30
00:01:24,000 --> 00:01:26,133
let's take a look. How do we do
this? So does 13 divided this?

31
00:01:26,133 --> 00:01:29,166
So if 13 divides this number,

32
00:01:29,166 --> 00:01:32,000
then the remainder when I 
divide by 13 should be 0.

33
00:01:32,000 --> 00:01:33,266


34
00:01:33,266 --> 00:01:36,933
So what does it suffice? Well by Congruent 
If and Only If Same Remainder,

35
00:01:36,933 --> 00:01:40,000
it suffices to look at this mod 13,

36
00:01:40,000 --> 00:01:44,233
and if I get 0, then 13 divides it and 
otherwise 13 doesn't divide this number.

37
00:01:44,233 --> 00:01:45,066


38
00:01:45,066 --> 00:01:47,600
So by CISR,

39
00:01:47,600 --> 00:01:48,533


40
00:01:48,533 --> 00:01:51,033
13 divides this number

41
00:01:51,033 --> 00:01:52,533


42
00:01:52,533 --> 00:01:54,566
if and only if…

43
00:01:54,566 --> 00:01:56,700


44
00:01:56,700 --> 00:01:58,933
if and only if this number…

45
00:01:58,933 --> 00:02:03,566


46
00:02:03,566 --> 00:02:06,000
is equivalent to 0

47
00:02:06,000 --> 00:02:07,500


48
00:02:07,500 --> 00:02:09,366
mod 13.

49
00:02:09,366 --> 00:02:09,633


50
00:02:09,633 --> 00:02:10,433


51
00:02:10,433 --> 00:02:13,066
Right, so now it suffices 
to divide this number,

52
00:02:13,066 --> 00:02:16,133
or to look at this number mod 13.

53
00:02:16,133 --> 00:02:18,400


54
00:02:18,400 --> 00:02:23,700


55
00:02:23,700 --> 00:02:27,700
So hopefully you got to this point 
and you at least knew how to do this.

56
00:02:27,700 --> 00:02:28,533


57
00:02:28,533 --> 00:02:31,300
Again, I would recommend
pausing the video at this point

58
00:02:31,300 --> 00:02:34,000
and if you didn't get to this 
point, then trying it again.

59
00:02:34,000 --> 00:02:35,066


60
00:02:35,066 --> 00:02:36,400


61
00:02:36,400 --> 00:02:39,066
So now let's look at this number

62
00:02:39,066 --> 00:02:40,400


63
00:02:40,400 --> 00:02:42,666
mod 13. Now

64
00:02:42,666 --> 00:02:44,433


65
00:02:44,433 --> 00:02:49,233
it might not be obvious what to do 
and with these types of problems, 

66
00:02:49,233 --> 00:02:51,266
it might not be,

67
00:02:51,266 --> 00:02:52,266


68
00:02:52,266 --> 00:02:55,833
but what I'm going to do is I'm going 
to just start to evaluate this, okay?

69
00:02:55,833 --> 00:02:57,166


70
00:02:57,166 --> 00:03:01,766
I'm going to take this first 2 to the 70 
and at least start to evaluate it and

71
00:03:01,766 --> 00:03:04,800
the best way to do this - well 
maybe not the best way…

72
00:03:04,800 --> 00:03:07,633
a way to do this is to 
actually take the 70,

73
00:03:07,633 --> 00:03:10,766
and use the fact that 70 is 2 times 35, 

74
00:03:10,766 --> 00:03:13,466
and then look at 2 squared to the power of 35,

75
00:03:13,466 --> 00:03:16,133
and then see where that gets us.

76
00:03:16,133 --> 00:03:19,266
So I'm going to take this 
and do exactly what I said.

77
00:03:19,266 --> 00:03:21,666
2 squared to the power of 35.

78
00:03:21,666 --> 00:03:23,466


79
00:03:23,466 --> 00:03:26,433
So let's make that change here.

80
00:03:26,433 --> 00:03:27,900


81
00:03:27,900 --> 00:03:30,600
Those are the same thing, 
right, by exponent laws.

82
00:03:30,600 --> 00:03:31,666


83
00:03:31,666 --> 00:03:35,500
Now what am I doing? Well 
now I need to take a look at

84
00:03:35,500 --> 00:03:37,233


85
00:03:37,233 --> 00:03:40,266
2 squared, well that's 4, so let's do that.

86
00:03:40,266 --> 00:03:42,000


87
00:03:42,000 --> 00:03:44,433
Okay so it's 4, 

88
00:03:44,433 --> 00:03:45,433


89
00:03:45,433 --> 00:03:48,066
now what am I going to do?
Okay so now it's not clear.

90
00:03:48,066 --> 00:03:51,733
Again, you might want to pause and 
try to think about what to do now.

91
00:03:51,733 --> 00:03:56,200


92
00:03:56,200 --> 00:04:00,100
If you look at this, so 
now 4 mod 13, well

93
00:04:00,100 --> 00:04:01,400


94
00:04:01,400 --> 00:04:04,333
again it's not…

95
00:04:04,333 --> 00:04:08,066
it's not obvious but 4 isn't really
the right number to use. So

96
00:04:08,066 --> 00:04:10,566
4 mod 13, we can actually 
go to the negative side

97
00:04:10,566 --> 00:04:13,600
of 4 and what do we get if we go 
to the negative side of 4? So

98
00:04:13,600 --> 00:04:18,433
4 is actually the same 
as negative 9 mod 13.

99
00:04:18,433 --> 00:04:20,566
So how do we see that? Well…

100
00:04:20,566 --> 00:04:22,400


101
00:04:22,400 --> 00:04:27,533
well 4 is the same as negative 9 mod 13, you
can do that just directly by definition, right?

102
00:04:27,533 --> 00:04:30,600
So I'll write that underneath this. So

103
00:04:30,600 --> 00:04:33,500
4 is equivalent to negative 9 mod 13.

104
00:04:33,500 --> 00:04:37,066


105
00:04:37,066 --> 00:04:39,500
So I’m going to write this underneath 
it should appear here right?

106
00:04:39,500 --> 00:04:42,166
So how did we see that? Well okay, 
if we bring the negative 9 over, that

107
00:04:42,166 --> 00:04:45,266
becomes 4 plus 9, and 13 divides 4 plus 9.

108
00:04:45,266 --> 00:04:46,966
So that's the simplest way to see it.

109
00:04:46,966 --> 00:04:51,533
I like to think of mod 13 every once in a 
while as adding or subtracting 0’s, right?

110
00:04:51,533 --> 00:04:52,900


111
00:04:52,900 --> 00:04:55,333
So with mod 13, I can actually just

112
00:04:55,333 --> 00:04:59,066
subtract 13 because 13 is 
the same as 0 mod 13.

113
00:04:59,066 --> 00:04:59,766


114
00:04:59,766 --> 00:05:01,233
Right?

115
00:05:01,233 --> 00:05:03,300
So I can

116
00:05:03,300 --> 00:05:05,433
add and subtract 0 as 
much as I want, right?

117
00:05:05,433 --> 00:05:08,566
It works for equality, it works for congruences.

118
00:05:08,566 --> 00:05:11,133
Now if I do this, what do I get?
Doesn't look like I get much,

119
00:05:11,133 --> 00:05:13,333
but let's take a look.

120
00:05:13,333 --> 00:05:14,866


121
00:05:14,866 --> 00:05:17,333
Well 4 minus 13, that's negative 9.

122
00:05:17,333 --> 00:05:20,766


123
00:05:20,766 --> 00:05:23,633
And now with negative 
9, what do I do now?

124
00:05:23,633 --> 00:05:24,900


125
00:05:24,900 --> 00:05:26,733
Well negative 9, that's the same as - 

126
00:05:26,733 --> 00:05:31,766
so negative 1 to the power of 35, well 35 is 
an odd number so I can pull the negative out. 

127
00:05:31,766 --> 00:05:33,500
It’ll look like this,

128
00:05:33,500 --> 00:05:36,066


129
00:05:36,066 --> 00:05:41,066
and now I have 9 to the 35, well let's go
backwards now. 9 is the same as 3 squared.

130
00:05:41,066 --> 00:05:45,066


131
00:05:45,066 --> 00:05:46,733


132
00:05:46,733 --> 00:05:48,566
3 squared well okay,

133
00:05:48,566 --> 00:05:51,533
3 squared to the 35 well, 
just like I did up here,

134
00:05:51,533 --> 00:05:55,400
2 squared to the 35 I'm going to bring those
two together what am I going to get?

135
00:05:55,400 --> 00:05:57,133


136
00:05:57,133 --> 00:06:00,733
I'm going to actually get 3 to the 70.

137
00:06:00,733 --> 00:06:04,566


138
00:06:04,566 --> 00:06:06,900
And lo and behold,

139
00:06:06,900 --> 00:06:10,866


140
00:06:10,866 --> 00:06:13,133
we actually get

141
00:06:13,133 --> 00:06:14,200


142
00:06:14,200 --> 00:06:16,000
cancellation.

143
00:06:16,000 --> 00:06:21,600
It's a little bit magical, so you didn't have to evaluate 
2 to the 70 and 3 to the 70 completely by hand,

144
00:06:21,600 --> 00:06:26,366
right, you actually get a little bit lucky. 
Again, how do you know to do this?

145
00:06:26,366 --> 00:06:30,266
It's a matter of feeling and a 
matter of trying things, right?

146
00:06:30,266 --> 00:06:34,433
My first attempt wasn't this. My
first attempt was actually trying…

147
00:06:34,433 --> 00:06:36,766
I got to 2 to the 4 and I said

148
00:06:36,766 --> 00:06:39,466
oh that's 16 well mod 13, that's 3,

149
00:06:39,466 --> 00:06:41,833
and then I tried to use that to help me out.

150
00:06:41,833 --> 00:06:43,866
I didn't really get very far.

151
00:06:43,866 --> 00:06:44,866


152
00:06:44,866 --> 00:06:48,566
It just became more complicated and I 
thought it was harder than it needed to be.

153
00:06:48,566 --> 00:06:52,400
So then I started saying okay what 
if I did this splitting up the 2 trick,

154
00:06:52,400 --> 00:06:56,166
then I got to 4 and I was still not confident

155
00:06:56,166 --> 00:06:58,366
and then I decided well okay well

156
00:06:58,366 --> 00:07:02,566
instead of 4 let's go to negative 9, and then 
I realized oh that's almost the same as 3,

157
00:07:02,566 --> 00:07:04,400
and then I could do it. 

158
00:07:04,400 --> 00:07:08,800
You can also play this trick with 3 
to the 70 instead of with 2 to the 70.

159
00:07:08,800 --> 00:07:13,100
3 squared is 9, 9 becomes negative 4, 
and then the same sort of trick works. So

160
00:07:13,100 --> 00:07:16,166
I encourage you to try
that if you don't see this.

161
00:07:16,166 --> 00:07:18,200
I guess we should also 
finish this off, right? So let's

162
00:07:18,200 --> 00:07:21,400
put a nice little concluding
sentence. So therefore

163
00:07:21,400 --> 00:07:22,766


164
00:07:22,766 --> 00:07:26,466
13 divides the number.

165
00:07:26,466 --> 00:07:26,733


166
00:07:26,733 --> 00:07:27,700


167
00:07:27,700 --> 00:07:29,600
And that's actually it.

168
00:07:29,600 --> 00:07:33,300
So hopefully, this gives you a little 
bit of a feeling as to what CISR says

169
00:07:33,300 --> 00:07:36,633
and how to use it in an example,

170
00:07:36,633 --> 00:07:37,366


171
00:07:37,366 --> 00:07:40,166
and this gives you a little bit of 
feeling about the computation.

172
00:07:40,166 --> 00:07:43,700
Gives you a little bit of a 
feeling of how I treat mods.

173
00:07:43,700 --> 00:07:48,700
I kind of look at the 13 as being a 0 so I can 
add and subtract 13 as much as I want.

174
00:07:48,700 --> 00:07:50,500


175
00:07:50,500 --> 00:07:53,200
Hopefully this gives you some insight 
to solving these types of problems.

176
00:07:53,200 --> 00:07:55,633
So thank you very much and good luck.