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

2
00:00:04,600 --> 00:00:07,766
as an application of 
Fermat's Little Theorem.

3
00:00:07,766 --> 00:00:12,933
So does 7 divide x to the 12 plus x 
squared plus 3 for some integer x?

4
00:00:12,933 --> 00:00:16,166


5
00:00:16,166 --> 00:00:19,100
Okay, on first glance, this seems 
like a really difficult problem.

6
00:00:19,100 --> 00:00:22,300
By the way, make sure you try the problem 
first before watching the end of the video.

7
00:00:22,300 --> 00:00:23,600


8
00:00:23,600 --> 00:00:27,733
What idea are we going to use here? Well 
x to the 12 seems like a very big number

9
00:00:27,733 --> 00:00:28,633


10
00:00:28,633 --> 00:00:32,933
I mean, a priori, it seems like we have to
look at this for every single integer x,

11
00:00:32,933 --> 00:00:36,633
but it turns out we don't have to, right?
We can use some tricks from congruences

12
00:00:36,633 --> 00:00:39,000
to help us solve this problem.

13
00:00:39,000 --> 00:00:41,900
So let's go and see how those are done.

14
00:00:41,900 --> 00:00:43,566


15
00:00:43,566 --> 00:00:47,700
So the solution to this, okay, so first 
off we want to know if 7 divides it then

16
00:00:47,700 --> 00:00:48,666


17
00:00:48,666 --> 00:00:52,000
what are we really trying to 
do? We are trying to determine

18
00:00:52,000 --> 00:00:53,400


19
00:00:53,400 --> 00:00:55,233
if

20
00:00:55,233 --> 00:00:56,400


21
00:00:56,400 --> 00:01:00,766
the polynomial is congruent to 0 mod 7.

22
00:01:00,766 --> 00:01:01,533


23
00:01:01,533 --> 00:01:06,533
Okay, so we are trying to determine if
this polynomial is congruent to 0 mod 7.

24
00:01:06,533 --> 00:01:08,366
How do we do this?

25
00:01:08,366 --> 00:01:09,533


26
00:01:09,533 --> 00:01:12,800
Well let's examine the
following: let's look at…

27
00:01:12,800 --> 00:01:14,600


28
00:01:14,600 --> 00:01:17,400
let's use Fermat’s Little 
Theorem, let's say it like this.

29
00:01:17,400 --> 00:01:21,433
Fermat’s Little Theorem…

30
00:01:21,433 --> 00:01:23,033


31
00:01:23,033 --> 00:01:25,333
which states - what does it state?

32
00:01:25,333 --> 00:01:27,433


33
00:01:27,433 --> 00:01:32,133
a to the power of 6 is equivalent to 1

34
00:01:32,133 --> 00:01:32,766


35
00:01:32,766 --> 00:01:34,933
mod 7

36
00:01:34,933 --> 00:01:36,100


37
00:01:36,100 --> 00:01:38,233
whenever…

38
00:01:38,233 --> 00:01:40,233


39
00:01:40,233 --> 00:01:42,400
whenever what? Whenever

40
00:01:42,400 --> 00:01:43,366


41
00:01:43,366 --> 00:01:46,800
7 does not divide a.

42
00:01:46,800 --> 00:01:47,733


43
00:01:47,733 --> 00:01:48,466


44
00:01:48,466 --> 00:01:51,400
So let's see where Fermat’s Little
Theorem comes into play.

45
00:01:51,400 --> 00:01:55,466
So in this setting, with p equal to
7, so remember 7 is a prime,

46
00:01:55,466 --> 00:01:59,333
here we have a to the p minus 1, so 
a to the 6, is congruent to 1 mod 7.

47
00:01:59,333 --> 00:02:01,500
This is true whenever 7 doesn't divide a.

48
00:02:01,500 --> 00:02:06,100
7 divides a then a to the whatever 
is congruent to 0, okay?

49
00:02:06,100 --> 00:02:07,900


50
00:02:07,900 --> 00:02:10,033
Alright.

51
00:02:10,033 --> 00:02:12,633
So first let's take care of - 

52
00:02:12,633 --> 00:02:16,566
okay so if we want to use this, then we 
need to show that 7 doesn't divide a. So first

53
00:02:16,566 --> 00:02:19,033
let's break this up into the 
case when it does. So…

54
00:02:19,033 --> 00:02:21,500


55
00:02:21,500 --> 00:02:23,033


56
00:02:23,033 --> 00:02:24,633
if

57
00:02:24,633 --> 00:02:27,666
7 divides x

58
00:02:27,666 --> 00:02:29,966


59
00:02:29,966 --> 00:02:32,166
then what do we know?

60
00:02:32,166 --> 00:02:35,833


61
00:02:35,833 --> 00:02:38,466
Okay so here we can just 
actually compute this.

62
00:02:38,466 --> 00:02:41,166


63
00:02:41,166 --> 00:02:43,700
If 7 divides x,

64
00:02:43,700 --> 00:02:45,700
then

65
00:02:45,700 --> 00:02:47,700


66
00:02:47,700 --> 00:02:50,266
x is equivalent to 0 mod 7.

67
00:02:50,266 --> 00:02:53,300


68
00:02:53,300 --> 00:02:57,500
So 7 divides x, then x is congruent 
to 0 mod 7, that's clearly true.

69
00:02:57,500 --> 00:02:59,033


70
00:02:59,033 --> 00:03:01,500
That's what this - that’s, I mean, by definition.

71
00:03:01,500 --> 00:03:05,500
7 divides x minus 0 so 
x is congruent to 0 mod 7.

72
00:03:05,500 --> 00:03:09,500
Now what we can do is we can just 
actually plug this into our polynomial.

73
00:03:09,500 --> 00:03:10,966


74
00:03:10,966 --> 00:03:14,333
And what are we going to 
get? Well if we plug it in,

75
00:03:14,333 --> 00:03:15,966


76
00:03:15,966 --> 00:03:18,733
we're going to get 0 to the power of 12

77
00:03:18,733 --> 00:03:21,266
plus 0 squared

78
00:03:21,266 --> 00:03:24,833
plus 3 and that's equivalent to 3. 

79
00:03:24,833 --> 00:03:25,066


80
00:03:25,066 --> 00:03:25,566


81
00:03:25,566 --> 00:03:30,700
So here we see that when x is congruent 
to 0, then this polynomial is definitely not 0

82
00:03:30,700 --> 00:03:33,566
So 7 doesn't divide this 
integer whatever it is

83
00:03:33,566 --> 00:03:35,766
when [7 divides x].

84
00:03:35,766 --> 00:03:36,900


85
00:03:36,900 --> 00:03:39,866
So now what can we do? 
Well now let's suppose…

86
00:03:39,866 --> 00:03:41,733


87
00:03:41,733 --> 00:03:43,933
let me suppose that 7…

88
00:03:43,933 --> 00:03:46,866


89
00:03:46,866 --> 00:03:50,500
let’s suppose now that 7 doesn't 
divide x. What do we get now?

90
00:03:50,500 --> 00:03:52,866
Now we can use Fermat’s
Little Theorem, right?

91
00:03:52,866 --> 00:03:54,133


92
00:03:54,133 --> 00:03:57,766
By FLT, we have that

93
00:03:57,766 --> 00:04:00,133


94
00:04:00,133 --> 00:04:03,533
x to the power of 6 is equivalent 1 mod 7

95
00:04:03,533 --> 00:04:06,466
and squaring gives…

96
00:04:06,466 --> 00:04:11,233


97
00:04:11,233 --> 00:04:14,433


98
00:04:14,433 --> 00:04:20,200
gives that x is congruent - or x to 
the 12 is congruent to 1 mod 7.

99
00:04:20,200 --> 00:04:23,233
So by FLT we have that x to 
the 6 is congruent to 1 mod 7,

100
00:04:23,233 --> 00:04:26,766
and squaring gives us that x to 
the 12 is congruent to 1 mod 7.

101
00:04:26,766 --> 00:04:28,966
I'm going to use capital L.

102
00:04:28,966 --> 00:04:30,933


103
00:04:30,933 --> 00:04:33,566
Okay, just because
it looks a little better.

104
00:04:33,566 --> 00:04:34,866


105
00:04:34,866 --> 00:04:38,200
Okay so this takes care of that 
big power, that x to the 12 power.

106
00:04:38,200 --> 00:04:40,366
Now we're just left
with x squared plus -

107
00:04:40,366 --> 00:04:44,200
well now we're left with dealing with x 
squared plus 3. So let's actually plug this in.

108
00:04:44,200 --> 00:04:46,500


109
00:04:46,500 --> 00:04:49,533
So substituting

110
00:04:49,533 --> 00:04:50,266


111
00:04:50,266 --> 00:04:52,400
gives…

112
00:04:52,400 --> 00:04:55,433


113
00:04:55,433 --> 00:04:59,233
what are we going to get?
We're going to get 1 to the 12

114
00:04:59,233 --> 00:05:00,600


115
00:05:00,600 --> 00:05:03,900
plus x squared [plus 3] 
and this is congruent to

116
00:05:03,900 --> 00:05:05,333


117
00:05:05,333 --> 00:05:09,133
this. So let's actually plug 
it in, what do we get? So

118
00:05:09,133 --> 00:05:09,766


119
00:05:09,766 --> 00:05:12,500
if we plug in that x to the 12 
is congruent to 1 mod 7 - 

120
00:05:12,500 --> 00:05:16,400
oh I guess I don't need that power of 12 
here, we already know that it's equal to 1.

121
00:05:16,400 --> 00:05:20,600
Still true, but let's make it look right.

122
00:05:20,600 --> 00:05:21,100


123
00:05:21,100 --> 00:05:26,633
There we go. So 1 plus x squared plus 3, 
so that’s x squared plus 4 mod 7, okay.

124
00:05:26,633 --> 00:05:29,566
Now we're looking to see if x squared plus 4

125
00:05:29,566 --> 00:05:33,333
is congruent to 0 mod 
7 for any number x.

126
00:05:33,333 --> 00:05:36,200
Well any non-zero x, right?

127
00:05:36,200 --> 00:05:38,366
So when we think mod 7, 
we're only thinking about

128
00:05:38,366 --> 00:05:41,466
7 integers: 0, 1, 2, 3, 4, 5, 6, essentially, right?

129
00:05:41,466 --> 00:05:45,966
Everything's equal up to the remainder so 
we only have to look at those 7 remainders.

130
00:05:45,966 --> 00:05:50,333
We already know that 7 doesn’t divide x, 
so that leaves us with just 6 numbers.

131
00:05:50,333 --> 00:05:54,000
Now you can think of 
them as 1, 2, 3, 4, 5, 6,

132
00:05:54,000 --> 00:05:58,500
or you can think of them as plus minus 
1, plus minus 2, and plus minus 3,

133
00:05:58,500 --> 00:05:59,866


134
00:05:59,866 --> 00:06:02,700
okay, and that might make your life a 
little easier since you're squaring.

135
00:06:02,700 --> 00:06:05,366
If you square a positive or a 
negative, it doesn't really matter.

136
00:06:05,366 --> 00:06:07,466


137
00:06:07,466 --> 00:06:09,333
So substituting,

138
00:06:09,333 --> 00:06:12,366
so trying all

139
00:06:12,366 --> 00:06:14,700
6 values

140
00:06:14,700 --> 00:06:16,966
gives...

141
00:06:16,966 --> 00:06:18,266


142
00:06:18,266 --> 00:06:20,733
so let's just plug them in,

143
00:06:20,733 --> 00:06:23,966
okay? So what are the 6 
values? Well plus minus 1,

144
00:06:23,966 --> 00:06:26,833
plus minus 2, and plus minus 3,

145
00:06:26,833 --> 00:06:31,700


146
00:06:31,700 --> 00:06:35,233
and this is equivalent - so the 
first case is equivalent to 5.

147
00:06:35,233 --> 00:06:37,500


148
00:06:37,500 --> 00:06:40,700
What's the second case?

149
00:06:40,700 --> 00:06:44,933
So the first case is 5, the second case 
is going to be plus minus 2 squared,

150
00:06:44,933 --> 00:06:46,266


151
00:06:46,266 --> 00:06:49,700
and that's not 5 despite 
what [is] going to appear.

152
00:06:49,700 --> 00:06:53,133
Plus minus 2 squared is 
4, 4 plus 4 is 8, that's 1.

153
00:06:53,133 --> 00:06:55,500
So let's fix that, 4 plus 4 should be

154
00:06:55,500 --> 00:06:57,566
8, which is 1 mod 7,

155
00:06:57,566 --> 00:06:58,266


156
00:06:58,266 --> 00:07:00,166
and in the last case, what do we have?

157
00:07:00,166 --> 00:07:03,566
Plus minus 3, so 3 squared 
is 9, 9 plus 4 is 13,

158
00:07:03,566 --> 00:07:06,566
that's the same as 6 mod 7. 

159
00:07:06,566 --> 00:07:08,433


160
00:07:08,433 --> 00:07:10,966
Now let's fix these numbers up, there we go.

161
00:07:10,966 --> 00:07:15,533
So plus minus 3 squared is 9, 
9 plus 4 is 13, 13 mod 7 is 6.

162
00:07:15,533 --> 00:07:16,966


163
00:07:16,966 --> 00:07:19,400
So none of these values is 0,

164
00:07:19,400 --> 00:07:21,966
therefore 7 never divides the integer.

165
00:07:21,966 --> 00:07:23,966


166
00:07:23,966 --> 00:07:28,133
Since none of the above values are 0,

167
00:07:28,133 --> 00:07:31,300
we have that 7

168
00:07:31,300 --> 00:07:32,266


169
00:07:32,266 --> 00:07:34,300
never divides

170
00:07:34,300 --> 00:07:36,933


171
00:07:36,933 --> 00:07:40,066
the polynomial given.

172
00:07:40,066 --> 00:07:43,033


173
00:07:43,033 --> 00:07:48,666
And that's it. So this gives us a complete 
proof. Let's start from the top and

174
00:07:48,666 --> 00:07:49,933


175
00:07:49,933 --> 00:07:51,600
and see what happened, okay?

176
00:07:51,600 --> 00:07:54,966
So we asked the question: 
does 7 divide this integer

177
00:07:54,966 --> 00:07:56,300
for some integer x?

178
00:07:56,300 --> 00:07:59,100
What are we trying to determine? 
We're trying to determine if this

179
00:07:59,100 --> 00:08:03,700
polynomial type thing, which we're thinking 
of as an integer, is congruent to 0 mod 7.

180
00:08:03,700 --> 00:08:04,666


181
00:08:04,666 --> 00:08:09,166
So what's the idea here? Well x to the 12 
is too big to just compute by hand, right,

182
00:08:09,166 --> 00:08:12,133
and we don't need to look at all the 
values of x because we're looking mod 7.

183
00:08:12,133 --> 00:08:14,633
So we only need to look 
from 0 to 6, but even like

184
00:08:14,633 --> 00:08:18,200
3 to the 12 might be too large for 
you to really want to deal with, okay?

185
00:08:18,200 --> 00:08:18,833


186
00:08:18,833 --> 00:08:21,266
So how do we deal with it? Well
we can use Fermat’s Little Theorem,

187
00:08:21,266 --> 00:08:24,566
right, which says okay 
well if I take let's say 3,

188
00:08:24,566 --> 00:08:26,400
3 to the 6 is congruent to 1 mod 7.

189
00:08:26,400 --> 00:08:30,166
So in particular, 3 to the 12 is congruent 
to 1 mod 7, that'll make life easier

190
00:08:30,166 --> 00:08:31,533


191
00:08:31,533 --> 00:08:34,233
because anytime x is not divisible by 7,

192
00:08:34,233 --> 00:08:37,366
then we can say that x to 
the 12 is congruent to 1.

193
00:08:37,366 --> 00:08:39,366
So let's do that.

194
00:08:39,366 --> 00:08:42,366
So first off, we take care of 
the case when 7 divides x

195
00:08:42,366 --> 00:08:44,100
because if we want to use
Fermat’s Little Theorem,

196
00:08:44,100 --> 00:08:46,500
we need to make sure that 
7 doesn't divide our integer.

197
00:08:46,500 --> 00:08:48,566


198
00:08:48,566 --> 00:08:50,633
So taking care of the 0 case,

199
00:08:50,633 --> 00:08:52,900
it's very easy, plug it in and go.

200
00:08:52,900 --> 00:08:53,533


201
00:08:53,533 --> 00:08:57,566
Now we suppose that 7 doesn't divide 
x, so by Fermat’s Little Theorem,

202
00:08:57,566 --> 00:09:02,233
we have that x to the 6 is congruent to 1 mod 7, 
then squaring gives us x is congruent to 12…

203
00:09:02,233 --> 00:09:05,300
or x to the 12 is congruent 
to 1 mod 7, sorry. 

204
00:09:05,300 --> 00:09:08,433
Substituting gives - so we can 
get rid of the x to the 12,

205
00:09:08,433 --> 00:09:10,433
this becomes x squared plus 4,

206
00:09:10,433 --> 00:09:12,966
and then let's just try all 
the possibilities, right?

207
00:09:12,966 --> 00:09:16,133
There's only 3, plug them 
in, you get 5, 1, and 6,

208
00:09:16,133 --> 00:09:19,833
none of 5, 1, and 6 are 
7, and 3 wasn't 7 either,

209
00:09:19,833 --> 00:09:22,833
and so we have at 7 
never divides this integer.

210
00:09:22,833 --> 00:09:23,566


211
00:09:23,566 --> 00:09:25,233
And we're done.

212
00:09:25,233 --> 00:09:29,400
So hopefully this gives you a little bit of 
insight as to how to use FLT to solve a 

213
00:09:29,400 --> 00:09:31,933
slightly different example,

214
00:09:31,933 --> 00:09:32,766


215
00:09:32,766 --> 00:09:35,866
and that's all I have to say.

216
00:09:35,866 --> 00:09:40,133
Again, maybe I'll say one last thing, 
I have one more thing to say,

217
00:09:40,133 --> 00:09:41,133


218
00:09:41,133 --> 00:09:45,200
try some of these on your own. Make sure you 
understand the statement of Fermat’s Little Theorem,

219
00:09:45,200 --> 00:09:48,133
and make sure - this is one of these theorems
that you really do want to memorize.

220
00:09:48,133 --> 00:09:52,000
You don't want to have to look it up every 
time you need to use it. You just want to use it

221
00:09:52,000 --> 00:09:53,933
when you need it and go through.

222
00:09:53,933 --> 00:09:57,200
The same can be said about a lot of
these Properties of Congruences.

223
00:09:57,200 --> 00:09:59,633
You probably don't want to 
be stating every single time

224
00:09:59,633 --> 00:10:02,100
oh I added two numbers that were the same

225
00:10:02,100 --> 00:10:04,000
and so I use Properties of Congruences.

226
00:10:04,000 --> 00:10:06,633
You probably just want to do this 
more naturally and more fluidly

227
00:10:06,633 --> 00:10:08,766
like you would with an equal sign, right?

228
00:10:08,766 --> 00:10:11,600
You wouldn't write down every 
time you say, for example, switched

229
00:10:11,600 --> 00:10:13,700
a and b in a plus b, right?

230
00:10:13,700 --> 00:10:16,133
That would just be too much,

231
00:10:16,133 --> 00:10:18,133
right, and it's the same sort 
of thing with congruences.

232
00:10:18,133 --> 00:10:21,466
You want to be able to do these as quickly 
as you would deal with an equality.

233
00:10:21,466 --> 00:10:22,500


234
00:10:22,500 --> 00:10:26,266
So hopefully this gives you a little bit more
confidence. Good luck with your assignment.