1
00:00:00,000 --> 00:00:00,366


2
00:00:00,366 --> 00:00:03,500
Congruences and Division. So a 
couple more theorems from this week.

3
00:00:03,500 --> 00:00:07,133
Congruences and Division, 
you should put this…

4
00:00:07,133 --> 00:00:09,566
you should draw the parallels 
to Congruences and Division, and

5
00:00:09,566 --> 00:00:12,933
Coprimeness and Divisibility, which 
we denoted by the acronym CAD,

6
00:00:12,933 --> 00:00:15,733
and there actually is a 
similarity between them,

7
00:00:15,733 --> 00:00:17,333
which we'll get to in a minute.

8
00:00:17,333 --> 00:00:20,200
The other thing I want to bring to your 
attention is the word “division”, right?

9
00:00:20,200 --> 00:00:24,800
So up to this point with congruences, we talked 
about adding, subtracting, and multiplying,

10
00:00:24,800 --> 00:00:27,100
and even exponentiation 
to some extent,

11
00:00:27,100 --> 00:00:29,633
but haven't spoken at all 
about division, and you might

12
00:00:29,633 --> 00:00:32,366
ask yourself, “Well why have 
we not spoken about division?”

13
00:00:32,366 --> 00:00:35,600
And the answer is well division 
is actually a little bit complicated.

14
00:00:35,600 --> 00:00:38,633
So let a, b, c be integers and 
let n be a natural number.

15
00:00:38,633 --> 00:00:41,066
If a c is congruent 
to b c mod n,

16
00:00:41,066 --> 00:00:44,700
and c and n are co-prime,
the gcd of c and n is 1,

17
00:00:44,700 --> 00:00:47,100
then a is congruent to b mod n.

18
00:00:47,100 --> 00:00:50,666
So in this setting…so when you 
have a c is congruent to b c mod n

19
00:00:50,666 --> 00:00:52,000
and c is co-prime to n, 

20
00:00:52,000 --> 00:00:54,533
you can divide by c, 
is what this is saying.

21
00:00:54,533 --> 00:00:56,566


22
00:00:56,566 --> 00:01:00,533
We'll learn later that this means 
that c is invertible mod n,

23
00:01:00,533 --> 00:01:02,833
which again means
the same sort of thing, 

24
00:01:02,833 --> 00:01:05,266
but we'll talk about that 
probably next week.

25
00:01:05,266 --> 00:01:07,033


26
00:01:07,033 --> 00:01:10,300
Again the proof of this is actually not bad, 
it's a “follow your nose” kind of proof.

27
00:01:10,300 --> 00:01:11,300


28
00:01:11,300 --> 00:01:15,533
You're going to unwind the 
definition, n divides a c minus b c,

29
00:01:15,533 --> 00:01:18,466
and then because c 
and n are co-prime and

30
00:01:18,466 --> 00:01:21,466
n divides c times a minus b,

31
00:01:21,466 --> 00:01:25,966
we can use Coprimeness and Divisibility 
to get the result that we want.

32
00:01:25,966 --> 00:01:27,700
So let's actually see this. 

33
00:01:27,700 --> 00:01:28,733


34
00:01:28,733 --> 00:01:31,600
So as I said, n divides 
c times a minus b.

35
00:01:31,600 --> 00:01:33,966
Since the gcd of c and n is 1,

36
00:01:33,966 --> 00:01:36,833
by Coprimeness and
Divisibility, n must divide…

37
00:01:36,833 --> 00:01:39,266
well n and c don't share 
any prime factors, so n

38
00:01:39,266 --> 00:01:42,033
must divide a minus b, is
what's happening there.

39
00:01:42,033 --> 00:01:44,000
That's Coprimeness and Divisibility.

40
00:01:44,000 --> 00:01:47,500
And hence what do we have? Well we have 
that a is congruent to b mod n, and that's it.

41
00:01:47,500 --> 00:01:49,733


42
00:01:49,733 --> 00:01:51,366
So, great.

43
00:01:51,366 --> 00:01:52,966
And that ends this proof. So

44
00:01:52,966 --> 00:01:57,066
a fun little result. This tells us how 
we can actually divide mod n.

45
00:01:57,066 --> 00:01:59,533


46
00:01:59,533 --> 00:02:02,100
On to the next one. Congruent if 
and only if Same Remainder.

47
00:02:02,100 --> 00:02:05,600
So this is one of the ways
that I like to think about

48
00:02:05,600 --> 00:02:08,000
mod n computations as 
well. So we talked about

49
00:02:08,000 --> 00:02:11,633
like how I think of n as 
being 0 mod n, it's one way

50
00:02:11,633 --> 00:02:14,766
that I think about it, and
this is the other way.

51
00:02:14,766 --> 00:02:15,566


52
00:02:15,566 --> 00:02:18,266
So let a and b be integers, 
and n a natural number,

53
00:02:18,266 --> 00:02:21,166
then a is congruent to b mod 
n if and only if a and b have

54
00:02:21,166 --> 00:02:24,066
the same remainder 
after division by n.

55
00:02:24,066 --> 00:02:24,966


56
00:02:24,966 --> 00:02:28,000
So when you read the
statement, the proof

57
00:02:28,000 --> 00:02:31,266
doesn't quite write itself. It's 
not immediately obvious, but

58
00:02:31,266 --> 00:02:35,000
not too, too far-fetched, right, you 
want to talk about division by n,

59
00:02:35,000 --> 00:02:38,333
so you probably want to use the Division
Algorithm somewhere on a and b,

60
00:02:38,333 --> 00:02:40,733
and then it's just a matter of 
making the symbols work out.

61
00:02:40,733 --> 00:02:44,400
This turns out to be exactly the 
proof. The Division Algorithm

62
00:02:44,400 --> 00:02:47,233
and a little bit of manipulating. 
So there is a lot of text here,

63
00:02:47,233 --> 00:02:49,233
but it's actually not too bad. 
It's what you think, right?

64
00:02:49,233 --> 00:02:54,200
By the Division Algorithm, we’ll write a as 
n times it's quotient plus the remainder.

65
00:02:54,200 --> 00:02:58,466
We’ll denote the quotient of a as q 
sub a, and r sub a and similarly for b,

66
00:02:58,466 --> 00:03:00,300


67
00:03:00,300 --> 00:03:03,466
and these values these r a 
and r b are less than n.

68
00:03:03,466 --> 00:03:04,200


69
00:03:04,200 --> 00:03:06,000
So if we subtract these two 
things, what do we get?

70
00:03:06,000 --> 00:03:08,600
We get a minus b is equal to

71
00:03:08,600 --> 00:03:11,966
n times q a minus q b,

72
00:03:11,966 --> 00:03:13,966
plus the difference 
of their remainders.

73
00:03:13,966 --> 00:03:14,966


74
00:03:14,966 --> 00:03:18,300
So this is true for both cases. 
Now what we're going to do is

75
00:03:18,300 --> 00:03:21,366
we're actually going to break it up into
the “if and only if” part. So sometimes

76
00:03:21,366 --> 00:03:24,266
when you're writing an “if and only if” proof, 
you can write general things that are true,

77
00:03:24,266 --> 00:03:27,400
and then try to prove each
direction, which is what I did here.

78
00:03:27,400 --> 00:03:29,600
So first, we're going to assume 
that a is congruent to b mod n,

79
00:03:29,600 --> 00:03:31,166
that is that n divides a minus b.

80
00:03:31,166 --> 00:03:35,066
So n divides a minus b, and
clearly divides this term that

81
00:03:35,066 --> 00:03:37,200
is a product of n 
and something else,

82
00:03:37,200 --> 00:03:40,333
so therefore by Divisibility of Integer
Combinations, n must divide

83
00:03:40,333 --> 00:03:44,166
r sub a minus r sub b, so the 
difference of the remainders.

84
00:03:44,166 --> 00:03:45,733
That's what it says there

85
00:03:45,733 --> 00:03:48,600
So by a restriction on the 
remainders, we know that - well...

86
00:03:48,600 --> 00:03:52,000
how big and how small can
r a minus r b be. We saw this

87
00:03:52,000 --> 00:03:56,033
a while ago back with 
uniqueness, this type of argument.

88
00:03:56,033 --> 00:03:58,466
So n divides r a 
minus r b, but

89
00:03:58,466 --> 00:04:02,800
the two remainders are 
between 0 and n, not including n.

90
00:04:02,800 --> 00:04:05,833
So if I take their difference, the 
smallest it can be is minus n plus 1,

91
00:04:05,833 --> 00:04:08,000
and the largest it 
can be is n minus 1.

92
00:04:08,000 --> 00:04:08,766


93
00:04:08,766 --> 00:04:12,466
What does that mean? Well again, 
when is this smallest and largest? It's

94
00:04:12,466 --> 00:04:16,600
largest when the remainder with 
respect to a is biggest, so n minus 1,

95
00:04:16,600 --> 00:04:19,166
and when the remainder 
with respect to b

96
00:04:19,166 --> 00:04:20,366


97
00:04:20,366 --> 00:04:24,000
is smallest, which is 0.

98
00:04:24,000 --> 00:04:25,200


99
00:04:25,200 --> 00:04:26,800
However - so if you 
look at this range,

100
00:04:26,800 --> 00:04:28,900
there's only one number 
that's divisible by n, right?

101
00:04:28,900 --> 00:04:31,633
There's only one multiple of 
n in this range, and that's 0.

102
00:04:31,633 --> 00:04:32,800


103
00:04:32,800 --> 00:04:35,200
And since n divides the difference 
of the remainders, we must have that

104
00:04:35,200 --> 00:04:38,366
the difference the remainders 
must be 0, and hence r a equals r b.

105
00:04:38,366 --> 00:04:40,066
So their remainders are the same.

106
00:04:40,066 --> 00:04:44,000
So if a is congruent to b mod n, then 
the two remainders must be the same.

107
00:04:44,000 --> 00:04:44,966


108
00:04:44,966 --> 00:04:48,866
If the two remainders are the same, then 
if we go back to this statement here

109
00:04:48,866 --> 00:04:51,266
what do we have? Well the two remainders 
are the same, so that goes away,

110
00:04:51,266 --> 00:04:54,366
so then we have a minus b is 
equal to some multiple of n.

111
00:04:54,366 --> 00:04:56,866
Well that just means 
that n divides a minus b

112
00:04:56,866 --> 00:04:59,700
and so by definition, a is
congruent to b mod n,

113
00:04:59,700 --> 00:05:02,866
and that's it. So again a little bit 
of a “follow your nose” kind of proof.

114
00:05:02,866 --> 00:05:04,366


115
00:05:04,366 --> 00:05:08,600
Maybe not so obvious the first time you 
see it, but what once you've seen it once,

116
00:05:08,600 --> 00:05:11,333
hopefully the arguments 
are not too, too bad. It just

117
00:05:11,333 --> 00:05:14,200
uses sort of the major
theorems from this course,

118
00:05:14,200 --> 00:05:16,833
Division Algorithm, Divisibility 
of Integer Combinations.

119
00:05:16,833 --> 00:05:19,633
These are things that you're 
probably quite familiar with by now.

120
00:05:19,633 --> 00:05:20,600


121
00:05:20,600 --> 00:05:24,433
And if not, I recommend getting 
familiar with these two theorems.

122
00:05:24,433 --> 00:05:26,533
They're very, very 
powerful and they're very - 

123
00:05:26,533 --> 00:05:28,666
they're used a lot in mathematics.

124
00:05:28,666 --> 00:05:30,133


125
00:05:30,133 --> 00:05:32,266
Okay, where to now? Let's 
actually look at a problem.

126
00:05:32,266 --> 00:05:32,900


127
00:05:32,900 --> 00:05:36,000
So again, example 2, let’s…so,

128
00:05:36,000 --> 00:05:40,266
what is the remainder when 
77 to the 100 times 999

129
00:05:40,266 --> 00:05:43,300
minus 6 to the 83 
is divided by 4?

130
00:05:43,300 --> 00:05:45,533
Pause the video, try this out.

131
00:05:45,533 --> 00:05:47,400
It's not too hard…

132
00:05:47,400 --> 00:05:49,266
well okay maybe I 
shouldn't say that. 

133
00:05:49,266 --> 00:05:50,466
[laughs]

134
00:05:50,466 --> 00:05:52,233
It's not too hard once you 
know what you're doing.

135
00:05:52,233 --> 00:05:55,433
If you don't know what you're doing, 
this question looks really difficult.

136
00:05:55,433 --> 00:05:59,200
But once you really think 
about what congruent means

137
00:05:59,200 --> 00:06:01,800
and things like that, 
this question actually

138
00:06:01,800 --> 00:06:02,300


139
00:06:02,300 --> 00:06:04,566
is relatively straightforward.

140
00:06:04,566 --> 00:06:07,500
Maybe not obvious, but
relatively straightforward.

141
00:06:07,500 --> 00:06:09,533
So hopefully you've attempted it.

142
00:06:09,533 --> 00:06:11,200


143
00:06:11,200 --> 00:06:13,933
Given that this came after Congruent 
if and only if Same Remainder,

144
00:06:13,933 --> 00:06:16,300
we probably have to 
use that theorem, CISR.

145
00:06:16,300 --> 00:06:17,700


146
00:06:17,700 --> 00:06:21,500
So given that we have this
77, the 999, and the 6,

147
00:06:21,500 --> 00:06:23,733
which we can all
reduce mod 4, right?

148
00:06:23,733 --> 00:06:25,866
So what are these numbers? So

149
00:06:25,866 --> 00:06:28,733
77, so let's think.

150
00:06:28,733 --> 00:06:31,800
80 is a multiple of 4,

151
00:06:31,800 --> 00:06:36,466
76 is a multiple of 4, so 77 
should give you remainder 1,

152
00:06:36,466 --> 00:06:40,000
when I divide by 4. 
999 is close to 1000,

153
00:06:40,000 --> 00:06:43,566
so it's close to 996, and 
so if I divide this by

154
00:06:43,566 --> 00:06:45,466
4, my remainder 
is going to be 3,

155
00:06:45,466 --> 00:06:48,433
and 6 is the same as 2 
mod 4, so let's actually

156
00:06:48,433 --> 00:06:50,366
plug in those values.

157
00:06:50,366 --> 00:06:52,866
So that's what the first line is 
saying, just that same computation.

158
00:06:52,866 --> 00:06:54,966
I actually explicitly wrote it 
out with a Division Algorithm.

159
00:06:54,966 --> 00:06:57,433
You don't have to do this 
when you're using it.

160
00:06:57,433 --> 00:06:59,633
You can just write down 6 
is congruent to 2 mod 4,

161
00:06:59,633 --> 00:07:04,200
77 is congruent to 1 mod 4, and 
999 is congruent to 3 mod 4.

162
00:07:04,200 --> 00:07:05,433


163
00:07:05,433 --> 00:07:08,533
Again, do you have to 
show this? No you don’t.

164
00:07:08,533 --> 00:07:12,366
I just thought I would do it to 
explicitly show you by CISR.

165
00:07:12,366 --> 00:07:14,966
But again, you can just write 
this down. If you just see that

166
00:07:14,966 --> 00:07:18,533
77 is the same as 1 
mod 4, just do it.  Don't

167
00:07:18,533 --> 00:07:20,600
waste too much time explaining it.

168
00:07:20,600 --> 00:07:21,833


169
00:07:21,833 --> 00:07:25,066
So now combining this with Properties 
of Congruences, what we have?

170
00:07:25,066 --> 00:07:28,000
Well 77 is the same as 
1, 999 is the same as 3,

171
00:07:28,000 --> 00:07:30,266
and minus 6 [to the 83] 
is same as 2 to the 83.

172
00:07:30,266 --> 00:07:31,133


173
00:07:31,133 --> 00:07:35,066
1 to the 100, that's 
easy, times 3, that's 3.

174
00:07:35,066 --> 00:07:35,933


175
00:07:35,933 --> 00:07:38,666
2 to the 83, now if 
you don't see this… 

176
00:07:38,666 --> 00:07:40,633
I've actually broken it down 
in a couple of steps, but

177
00:07:40,633 --> 00:07:43,533
2 to the 83 is divisible 
by 4, right? Why? Well

178
00:07:43,533 --> 00:07:46,533
2 to the 83 is 2 squared, 
times 2 to the 81.

179
00:07:46,533 --> 00:07:49,566
2 squared is 4, 
and 4 is 0 mod 4.

180
00:07:49,566 --> 00:07:52,933
Again I missed a mod 
4 here. But that's it.

181
00:07:52,933 --> 00:07:57,300
So again, 4 divides 
6 to the 83, that's

182
00:07:57,300 --> 00:07:59,100
not too, too hard to see,

183
00:07:59,100 --> 00:08:00,633
and you're left with just 3.

184
00:08:00,633 --> 00:08:01,733


185
00:08:01,733 --> 00:08:07,000
So once again, by CISR, 3 is the remainder 
when this big number is divided by 4.

186
00:08:07,000 --> 00:08:10,800
How do we know that? Well we saw that 
this number is equivalent to 3 mod 4,

187
00:08:10,800 --> 00:08:13,866
and so they must have the same
remainder when divided by 4,

188
00:08:13,866 --> 00:08:16,300
and the remainder of 3
when I divide by 4 is 3.

189
00:08:16,300 --> 00:08:17,666


190
00:08:17,666 --> 00:08:18,766
So there we go.