1
00:00:00,000 --> 00:00:03,333
So we've left the Linear Congruence 
Theorem stuff a little bit.

2
00:00:03,333 --> 00:00:05,733
We'd like to go to sort 
of what I would consider

3
00:00:05,733 --> 00:00:07,566
two foundational 
theorems in the course:

4
00:00:07,566 --> 00:00:09,900
Fermat's Little Theorem and the 
Chinese Remainder Theorem.

5
00:00:09,900 --> 00:00:11,300


6
00:00:11,300 --> 00:00:13,366
So Fermat's Little 
Theorem, the proof of this,

7
00:00:13,366 --> 00:00:17,000
that we did in our class, is
actually a little bit tricky.

8
00:00:17,000 --> 00:00:20,500
It's difficult to understand. I think it's 
a really nice proof, it's very clever,

9
00:00:20,500 --> 00:00:23,933
at least the one that we 
present. There are slightly…

10
00:00:23,933 --> 00:00:24,900


11
00:00:24,900 --> 00:00:28,866
maybe I should say not less clever, but 
I would say differently clever proofs.

12
00:00:28,866 --> 00:00:29,333


13
00:00:29,333 --> 00:00:32,633
This one's very easy to understand 
though, which is why I like it.

14
00:00:32,633 --> 00:00:34,100


15
00:00:34,100 --> 00:00:37,133
It's not the easiest to do, I would say
the easiest to do is using induction

16
00:00:37,133 --> 00:00:40,600
and the Binomial Theorem if you want to check 
that out, that'll be I think on Wikipedia actually.

17
00:00:40,600 --> 00:00:41,800


18
00:00:41,800 --> 00:00:44,466
But anyways, Fermat's Little Theorem, 
let's talk about the theorem.

19
00:00:44,466 --> 00:00:46,900
If p is a prime and 
p doesn't divide a,

20
00:00:46,900 --> 00:00:49,933
then a to the p minus 1 
is congruent to 1 mod p,

21
00:00:49,933 --> 00:00:52,100
or you could reword
this again in Z mod p,

22
00:00:52,100 --> 00:00:53,800
a to the p minus 1 is equal to

23
00:00:53,800 --> 00:00:57,200
the equivalence class of a to the 
p minus 1, is equal to 1 in Z mod p.

24
00:00:57,200 --> 00:00:58,400


25
00:00:58,400 --> 00:01:00,400
Now the proof’s not going to fit on 
the slide and I don't think there's

26
00:01:00,400 --> 00:01:02,933
much value in doing 
it on 3 slides again,

27
00:01:02,933 --> 00:01:07,800
but maybe…let me just give you
a recap of what the proof entailed.

28
00:01:07,800 --> 00:01:09,600
As long as you have

29
00:01:09,600 --> 00:01:12,966
the major elements, you can 
actually reconstruct this proof

30
00:01:12,966 --> 00:01:14,300
fairly easily.

31
00:01:14,300 --> 00:01:15,966


32
00:01:15,966 --> 00:01:18,833
There's two key sort of elements 
here, and the one key is this lemma

33
00:01:18,833 --> 00:01:21,433
and this is really
important for this proof. 

34
00:01:21,433 --> 00:01:24,200
So I'm going to define 
the sets S and T.

35
00:01:24,200 --> 00:01:26,333
So T is going to be the 
numbers from 1 to p minus 1,

36
00:01:26,333 --> 00:01:30,166
and S is going to be the a multiples of 
the numbers from 1 to p minus 1. So

37
00:01:30,166 --> 00:01:32,466
a, 2a, all the way up 
to p minus 1 times a.

38
00:01:32,466 --> 00:01:33,433


39
00:01:33,433 --> 00:01:35,966
And here of course we're assuming 
that a and p are co-prime.

40
00:01:35,966 --> 00:01:36,566


41
00:01:36,566 --> 00:01:39,900
Then the elements of S are 
unique modulo p, and for all

42
00:01:39,900 --> 00:01:43,200
elements of S, there 
exists a unique element

43
00:01:43,200 --> 00:01:46,166
t inside T such that S
is congruent to t mod p.

44
00:01:46,166 --> 00:01:47,000


45
00:01:47,000 --> 00:01:50,766
What's really happening here? 
What's really happening here is that

46
00:01:50,766 --> 00:01:53,933
the element a is invertible. 
So one way to look at this

47
00:01:53,933 --> 00:01:56,500
is you can set up 
a map from S to T

48
00:01:56,500 --> 00:01:57,766


49
00:01:57,766 --> 00:02:00,966
and you look at S and T 
as subsets of Z mod p,

50
00:02:00,966 --> 00:02:03,833
and you can set up a map 
from S to T defined by

51
00:02:03,833 --> 00:02:07,066
sending an element s to the element

52
00:02:07,066 --> 00:02:09,666
s times a inverse, for example,

53
00:02:09,666 --> 00:02:11,866
and that sets up a 
bijection between S and T.

54
00:02:11,866 --> 00:02:13,933
That’s one way to look at this.

55
00:02:13,933 --> 00:02:17,766
Another way is just to go through it. All 
the elements of S are non-zero mod p,

56
00:02:17,766 --> 00:02:21,633
and all of them are distinct mod p, so 
therefore they must be equal to t mod p,

57
00:02:21,633 --> 00:02:23,966
in some rearrangement. 

58
00:02:23,966 --> 00:02:26,700
Why is this important? Why is this 
S and T important? Well if I take a

59
00:02:26,700 --> 00:02:30,133
product of the elements of S and 
a product of the elements of T,

60
00:02:30,133 --> 00:02:32,466
I know that they must 
be congruent mod p.

61
00:02:32,466 --> 00:02:34,333
And why is that? Let's 
think about that.

62
00:02:34,333 --> 00:02:35,400


63
00:02:35,400 --> 00:02:38,200
If you take the product of the elements 
of S and the product of the elements of T,

64
00:02:38,200 --> 00:02:42,333
well we said before that these two sets 
are equal mod p, up to a rearrangement.

65
00:02:42,333 --> 00:02:46,200
So if I multiply them together, because 
of commutativity, it doesn't matter.

66
00:02:46,200 --> 00:02:46,900


67
00:02:46,900 --> 00:02:48,900
What do I mean by, “it doesn't matter”? 
Well I mean that the product

68
00:02:48,900 --> 00:02:52,600
of these elements must be the same 
as the product of the elements of T.

69
00:02:52,600 --> 00:02:56,266
Right? Because, again, S and T are the 
same mod p up to a rearrangement.

70
00:02:56,266 --> 00:02:57,866


71
00:02:57,866 --> 00:03:00,166
So what does this mean? What do the 
elements of S look like? Well they look like

72
00:03:00,166 --> 00:03:03,433
multiples of a, so let's 
write down multiples of a.

73
00:03:03,433 --> 00:03:05,566
And what do the elements of T look 
like? Well they look like the integers

74
00:03:05,566 --> 00:03:08,000
from 1 to p minus 1, so 
let's write that down.

75
00:03:08,000 --> 00:03:08,833


76
00:03:08,833 --> 00:03:12,100
Now if I'm doing this product here,
the product of k times a, well

77
00:03:12,100 --> 00:03:14,100
a is getting multiplied 
p minus 1 times,

78
00:03:14,100 --> 00:03:16,466
so it's the same as multiplying 
by a to the p minus 1

79
00:03:16,466 --> 00:03:19,366
times the product from 
1 to p minus 1 of k.

80
00:03:19,366 --> 00:03:20,566


81
00:03:20,566 --> 00:03:23,033
And the same thing with a product 
of j, I didn't touch this side.

82
00:03:23,033 --> 00:03:25,333
Note though that these products, 
these are actually just

83
00:03:25,333 --> 00:03:28,000
a clever notation for 
p minus 1 factorial,

84
00:03:28,000 --> 00:03:28,566


85
00:03:28,566 --> 00:03:32,000
and p minus 1 factorial, well 
we know that p is prime,

86
00:03:32,000 --> 00:03:36,000
and so p minus 1 factorial and p 
don't share any common factor.

87
00:03:36,000 --> 00:03:37,066


88
00:03:37,066 --> 00:03:39,533
So because p is prime, its 
only divisors are 1 and p,

89
00:03:39,533 --> 00:03:43,400
so no number less than 
p, other than 1, divides

90
00:03:43,400 --> 00:03:47,300
p and p minus 1 factorial is the 
product of all numbers less than p,

91
00:03:47,300 --> 00:03:50,933
so therefore the gcd of p 
and p minus 1 factorial is 1.

92
00:03:50,933 --> 00:03:51,500


93
00:03:51,500 --> 00:03:54,433
Because of that, I can cancel, they're 
invertible, that was a previous theorem,

94
00:03:54,433 --> 00:03:57,233
and so we have a to the p minus
1 is congruent to 1 mod p.

95
00:03:57,233 --> 00:03:58,200


96
00:03:58,200 --> 00:03:59,666
And that's it.

97
00:03:59,666 --> 00:04:00,833


98
00:04:00,833 --> 00:04:04,400
A clever, clever statement, so now 
the proof is one thing. The proof…

99
00:04:04,400 --> 00:04:05,666


100
00:04:05,666 --> 00:04:08,633
is clever but it’s…clever.

101
00:04:08,633 --> 00:04:12,000
So you have to - I mean, do we really 
expect you to know all these things.

102
00:04:12,000 --> 00:04:13,000


103
00:04:13,000 --> 00:04:15,266
I'll let you decide 
based on that reaction.

104
00:04:15,266 --> 00:04:18,933
But what's really important about Fermat’s 
Little Theorem is the ability to apply it,

105
00:04:18,933 --> 00:04:21,733
and we're going to see 
an application right now.

106
00:04:21,733 --> 00:04:25,733
So find the remainder when 
7 to 92 is [divided] by 11.

107
00:04:25,733 --> 00:04:28,933
So again, a good point, at this point,
to pause the video and actually

108
00:04:28,933 --> 00:04:30,466
try this problem.

109
00:04:30,466 --> 00:04:32,633
It's not - you should try it.

110
00:04:32,633 --> 00:04:33,600


111
00:04:33,600 --> 00:04:36,300
Now hopefully you're back,

112
00:04:36,300 --> 00:04:38,633
and when you're
looking at 7 to the 92,

113
00:04:38,633 --> 00:04:40,533
well okay 11 is a prime,

114
00:04:40,533 --> 00:04:42,700
and we know that 
11 doesn't divide 7.

115
00:04:42,700 --> 00:04:43,700


116
00:04:43,700 --> 00:04:46,400
Why is that important? If 11 divided 
7, the answer would be really easy.

117
00:04:46,400 --> 00:04:50,000
If 11 divides 7 then 11 
clearly divides 7 to the 92

118
00:04:50,000 --> 00:04:53,533
and so we get that this is
congruent to 0 mod 11.

119
00:04:53,533 --> 00:04:55,066


120
00:04:55,066 --> 00:04:56,933
So when finding the remainder,

121
00:04:56,933 --> 00:05:00,466
again remember by CISR, Congruent 
If and Only If Same Remainder,

122
00:05:00,466 --> 00:05:04,300
we can look at this mod 11, reduce 
it to the least non-negative

123
00:05:04,300 --> 00:05:05,433
residue

124
00:05:05,433 --> 00:05:08,466
and then argue by CISR that since those 
two numbers have the same remainder

125
00:05:08,466 --> 00:05:11,066
when divided by 11, the original…

126
00:05:11,066 --> 00:05:13,766
since those two numbers 
are congruent mod 11,

127
00:05:13,766 --> 00:05:15,300
then the original number 
and the last number must

128
00:05:15,300 --> 00:05:17,366
have the same remainder 
when divided by 11,

129
00:05:17,366 --> 00:05:22,000
and the least non-negative residue
mod 11 is actually just the remainder.

130
00:05:22,000 --> 00:05:23,600


131
00:05:23,600 --> 00:05:25,566
When this number is 
divided by 11. Okay.

132
00:05:25,566 --> 00:05:27,166


133
00:05:27,166 --> 00:05:29,200
So again what do I know by 
Fermat’s Little Theorem?

134
00:05:29,200 --> 00:05:31,800
I know that because 
11 is co-prime to 7,

135
00:05:31,800 --> 00:05:34,833
7 to the 11 minus 
1, which is 10,

136
00:05:34,833 --> 00:05:38,433
so 7 to the 10 is
congruent to 1 mod 11.

137
00:05:38,433 --> 00:05:39,833


138
00:05:39,833 --> 00:05:43,100
So what am I going to try to do with 
7 to the 92? I'm going to try to get

139
00:05:43,100 --> 00:05:45,366
7 to the 10 to appear.

140
00:05:45,366 --> 00:05:46,066


141
00:05:46,066 --> 00:05:47,933
And the way I like to do 
this - so there's lots of ways.

142
00:05:47,933 --> 00:05:50,900
You actually start with 7 to the 10, 
and then take it to the power of 9,

143
00:05:50,900 --> 00:05:54,200
and then multiply by 7 squared,
that's one way to do it.

144
00:05:54,200 --> 00:05:57,200
The way I like to start though is because 
usually when you're solving these problems,

145
00:05:57,200 --> 00:05:59,566
there's multiple - like you
have a sum of these numbers

146
00:05:59,566 --> 00:06:02,666
and you're dealing with multiple things, 
so I like using this method a little bit more.

147
00:06:02,666 --> 00:06:04,433
Personal preference of course.

148
00:06:04,433 --> 00:06:05,500


149
00:06:05,500 --> 00:06:08,533
So here though I'm going to write

150
00:06:08,533 --> 00:06:11,900
7 to the 92 as 7 to the 
power of 9 times 10 plus 2.

151
00:06:11,900 --> 00:06:14,500
This is actually an equality, but 
I'll leave it as a congruence.

152
00:06:14,500 --> 00:06:15,333


153
00:06:15,333 --> 00:06:19,033
Flip the symbols around, 7 to the 
10 to the power of 9 times 7 squared.

154
00:06:19,033 --> 00:06:21,766
That's 1 to the 9
times 7 squared.

155
00:06:21,766 --> 00:06:25,400
7 squared is 49, 
49 mod 11 that's 5

156
00:06:25,400 --> 00:06:26,833
mod 11.

157
00:06:26,833 --> 00:06:27,633


158
00:06:27,633 --> 00:06:30,600
By CISR, the remainder 
when I divide 5 by 11 is 5,

159
00:06:30,600 --> 00:06:33,733
so therefore the remainder 
when I divide 7 to 92 by 11 is 5,

160
00:06:33,733 --> 00:06:36,100
since 7 to the 92 is 
congruent to 5 mod 11.

161
00:06:36,100 --> 00:06:36,966


162
00:06:36,966 --> 00:06:38,666
And that's it.

163
00:06:38,666 --> 00:06:41,966
So a fun little example. These questions 
are actually fun once you get use of them,

164
00:06:41,966 --> 00:06:43,766
but they do take a little bit of time.

165
00:06:43,766 --> 00:06:48,000
So don't be discouraged if at first you 
don't see all these patterns and stuff, but

166
00:06:48,000 --> 00:06:50,266
do practice, do take a 
couple of examples.

167
00:06:50,266 --> 00:06:53,333
Create your own examples, there are lots
of computer programs that can compute

168
00:06:53,333 --> 00:06:54,966
this very quickly.

169
00:06:54,966 --> 00:06:58,733
so the chances of you writing a small 
example and not being able to

170
00:06:58,733 --> 00:07:00,866
verify it on a computer are very small.

171
00:07:00,866 --> 00:07:03,400
This is worth doing 
for your first attempt.

172
00:07:03,400 --> 00:07:05,533


173
00:07:05,533 --> 00:07:09,233
Corollaries to FLT, so some
of these I like to use a lot.

174
00:07:09,233 --> 00:07:12,000
So that's why I've put them 
all on the board. There actually - 

175
00:07:12,000 --> 00:07:14,833
I've put them all on one slide. 
They're not too hard to prove,

176
00:07:14,833 --> 00:07:18,233
I didn't prove any in this talk, but
you can check them out in the notes

177
00:07:18,233 --> 00:07:19,633
online.

178
00:07:19,633 --> 00:07:24,000
So some corollaries: if p is a prime and a is an 
integer, then a to the p is congruent to a mod p.

179
00:07:24,000 --> 00:07:25,666


180
00:07:25,666 --> 00:07:28,600
So how does this 
one work? So when

181
00:07:28,600 --> 00:07:32,133
p doesn't divide a, this is just 
FLT and then multiplied by a,

182
00:07:32,133 --> 00:07:34,766
and when p does divide a, well 
a is the same as 0 mod p.

183
00:07:34,766 --> 00:07:38,100
So a to the p is congruent to 0 mod p, and 
so these two numbers must be equal.

184
00:07:38,100 --> 00:07:38,966


185
00:07:38,966 --> 00:07:41,800
If p is a prime number 
and a is not 0

186
00:07:41,800 --> 00:07:45,800
in Z mod p, so the equivalence class of a 
is not equal to the equivalence class of 0,

187
00:07:45,800 --> 00:07:49,500
then there exists an 
element b inside Z mod p

188
00:07:49,500 --> 00:07:52,100
such that a times b is equal to 1.

189
00:07:52,100 --> 00:07:56,000
What element can we take? Well we can
actually take b to be a to the p minus 2.

190
00:07:56,000 --> 00:07:57,600


191
00:07:57,600 --> 00:08:00,766
Again so what things does this 
use? So p minus 2 is at least 0,

192
00:08:00,766 --> 00:08:04,000
because p is a prime number, 
so this actually makes sense.

193
00:08:04,000 --> 00:08:07,366
And what do we know here? So if 
I take a times a to the p minus 2,

194
00:08:07,366 --> 00:08:10,100
that's just a to the p minus 
1, and that's 1 by FLT.

195
00:08:10,100 --> 00:08:11,033


196
00:08:11,033 --> 00:08:13,533
We know that a is not the
same as 0 in Z mod p.

197
00:08:13,533 --> 00:08:14,633


198
00:08:14,633 --> 00:08:16,966
Another corollary: if r is 
equal to s plus k p, then

199
00:08:16,966 --> 00:08:19,300
a to the r is congruent 
to a to the s plus k 

200
00:08:19,300 --> 00:08:21,266
so no p up here, mod p.

201
00:08:21,266 --> 00:08:22,500


202
00:08:22,500 --> 00:08:24,800
And again, this just 
uses the first corollary.

203
00:08:24,800 --> 00:08:26,366


204
00:08:26,366 --> 00:08:29,533
Oh I should mention here, this
is a typo here that I didn't fix.

205
00:08:29,533 --> 00:08:33,600
So where p is a prime and a is 
an integer and r, s, and k…

206
00:08:33,600 --> 00:08:34,933


207
00:08:34,933 --> 00:08:36,300
they should be positive

208
00:08:36,300 --> 00:08:39,433
and the reasons why 
they should be positive,

209
00:08:39,433 --> 00:08:40,066


210
00:08:40,066 --> 00:08:42,033
or at least non-negative, is that

211
00:08:42,033 --> 00:08:45,600
you get some weird situations. 
So if r was negative, let's say,

212
00:08:45,600 --> 00:08:47,833
then I have a to the r,

213
00:08:47,833 --> 00:08:51,566
r is negative, so this is like saying 
a to the inverse to some rth power,

214
00:08:51,566 --> 00:08:53,333
but I don't know that a is invertible.

215
00:08:53,333 --> 00:08:55,866
So I need to be a little bit careful 
here, I apologize for this typo.

216
00:08:55,866 --> 00:08:59,066
But r, s, and k should be natural
numbers here not integers.

217
00:08:59,066 --> 00:09:00,333


218
00:09:00,333 --> 00:09:03,700
But again the proof is actually just 
identical to the corollary above -

219
00:09:03,700 --> 00:09:06,000
well the proof just uses the 
corollary above, it's not identical

220
00:09:06,000 --> 00:09:09,466
but it uses that corollary. And
this corollary, the last corollary,

221
00:09:09,466 --> 00:09:13,466
is basically the same as the third corollary except 
we allow for the fact that a [can] be invertible.

222
00:09:13,466 --> 00:09:16,500
So prove that if p 
does not divide a

223
00:09:16,500 --> 00:09:19,233
and r is congruent 
to s mod p minus 1,

224
00:09:19,233 --> 00:09:21,600
then a to the r is congruent 
to a to the s mod p.

225
00:09:21,600 --> 00:09:24,366
So here we allow r and s to be 
negative, which is not a problem

226
00:09:24,366 --> 00:09:27,100
because a is
invertible mod p.

227
00:09:27,100 --> 00:09:27,833


228
00:09:27,833 --> 00:09:30,533
So something - that's a slight 
subtlety, something to think about,

229
00:09:30,533 --> 00:09:34,233
maybe on the bus. Why 
can't we really do this

230
00:09:34,233 --> 00:09:36,233
over the integers, in general.