Hello everyone. In this video, I'd like to talk about the following problem
as an application of Fermat's Little Theorem.
So does 7 divide x to the 12 plus x squared plus 3 for some integer x?
Okay, on first glance, this seems like a really difficult problem.
By the way, make sure you try the problem first before watching the end of the video.
What idea are we going to use here? Well x to the 12 seems like a very big number
I mean, a priori, it seems like we have to look at this for every single integer x,
but it turns out we don't have to, right? We can use some tricks from congruences
to help us solve this problem.
So let's go and see how those are done.
So the solution to this, okay, so first off we want to know if 7 divides it then
what are we really trying to do? We are trying to determine
if
the polynomial is congruent to 0 mod 7.
Okay, so we are trying to determine if this polynomial is congruent to 0 mod 7.
How do we do this?
Well let's examine the following: let's look at…
let's use Fermat’s Little Theorem, let's say it like this.
Fermat’s Little Theorem…
which states - what does it state?
a to the power of 6 is equivalent to 1
mod 7
whenever…
whenever what? Whenever
7 does not divide a.
So let's see where Fermat’s Little Theorem comes into play.
So in this setting, with p equal to 7, so remember 7 is a prime,
here we have a to the p minus 1, so a to the 6, is congruent to 1 mod 7.
This is true whenever 7 doesn't divide a.
7 divides a then a to the whatever is congruent to 0, okay?
Alright.
So first let's take care of -
okay so if we want to use this, then we need to show that 7 doesn't divide a. So first
let's break this up into the case when it does. So…
if
7 divides x
then what do we know?
Okay so here we can just actually compute this.
If 7 divides x,
then
x is equivalent to 0 mod 7.
So 7 divides x, then x is congruent to 0 mod 7, that's clearly true.
That's what this - that’s, I mean, by definition.
7 divides x minus 0 so x is congruent to 0 mod 7.
Now what we can do is we can just actually plug this into our polynomial.
And what are we going to get? Well if we plug it in,
we're going to get 0 to the power of 12
plus 0 squared
plus 3 and that's equivalent to 3.
So here we see that when x is congruent to 0, then this polynomial is definitely not 0
So 7 doesn't divide this integer whatever it is
when [7 divides x].
So now what can we do? Well now let's suppose…
let me suppose that 7…
let’s suppose now that 7 doesn't divide x. What do we get now?
Now we can use Fermat’s Little Theorem, right?
By FLT, we have that
x to the power of 6 is equivalent 1 mod 7
and squaring gives…
gives that x is congruent - or x to the 12 is congruent to 1 mod 7.
So by FLT we have that x to the 6 is congruent to 1 mod 7,
and squaring gives us that x to the 12 is congruent to 1 mod 7.
I'm going to use capital L.
Okay, just because it looks a little better.
Okay so this takes care of that big power, that x to the 12 power.
Now we're just left with x squared plus -
well now we're left with dealing with x squared plus 3. So let's actually plug this in.
So substituting
gives…
what are we going to get? We're going to get 1 to the 12
plus x squared [plus 3] and this is congruent to
this. So let's actually plug it in, what do we get? So
if we plug in that x to the 12 is congruent to 1 mod 7 -
oh I guess I don't need that power of 12 here, we already know that it's equal to 1.
Still true, but let's make it look right.
There we go. So 1 plus x squared plus 3, so that’s x squared plus 4 mod 7, okay.
Now we're looking to see if x squared plus 4
is congruent to 0 mod 7 for any number x.
Well any non-zero x, right?
So when we think mod 7, we're only thinking about
7 integers: 0, 1, 2, 3, 4, 5, 6, essentially, right?
Everything's equal up to the remainder so we only have to look at those 7 remainders.
We already know that 7 doesn’t divide x, so that leaves us with just 6 numbers.
Now you can think of them as 1, 2, 3, 4, 5, 6,
or you can think of them as plus minus 1, plus minus 2, and plus minus 3,
okay, and that might make your life a little easier since you're squaring.
If you square a positive or a negative, it doesn't really matter.
So substituting,
so trying all
6 values
gives...
so let's just plug them in,
okay? So what are the 6 values? Well plus minus 1,
plus minus 2, and plus minus 3,
and this is equivalent - so the first case is equivalent to 5.
What's the second case?
So the first case is 5, the second case is going to be plus minus 2 squared,
and that's not 5 despite what [is] going to appear.
Plus minus 2 squared is 4, 4 plus 4 is 8, that's 1.
So let's fix that, 4 plus 4 should be
8, which is 1 mod 7,
and in the last case, what do we have?
Plus minus 3, so 3 squared is 9, 9 plus 4 is 13,
that's the same as 6 mod 7.
Now let's fix these numbers up, there we go.
So plus minus 3 squared is 9, 9 plus 4 is 13, 13 mod 7 is 6.
So none of these values is 0,
therefore 7 never divides the integer.
Since none of the above values are 0,
we have that 7
never divides
the polynomial given.
And that's it. So this gives us a complete proof. Let's start from the top and
and see what happened, okay?
So we asked the question: does 7 divide this integer
for some integer x?
What are we trying to determine? We're trying to determine if this
polynomial type thing, which we're thinking of as an integer, is congruent to 0 mod 7.
So what's the idea here? Well x to the 12 is too big to just compute by hand, right,
and we don't need to look at all the values of x because we're looking mod 7.
So we only need to look from 0 to 6, but even like
3 to the 12 might be too large for you to really want to deal with, okay?
So how do we deal with it? Well we can use Fermat’s Little Theorem,
right, which says okay well if I take let's say 3,
3 to the 6 is congruent to 1 mod 7.
So in particular, 3 to the 12 is congruent to 1 mod 7, that'll make life easier
because anytime x is not divisible by 7,
then we can say that x to the 12 is congruent to 1.
So let's do that.
So first off, we take care of the case when 7 divides x
because if we want to use Fermat’s Little Theorem,
we need to make sure that 7 doesn't divide our integer.
So taking care of the 0 case,
it's very easy, plug it in and go.
Now we suppose that 7 doesn't divide x, so by Fermat’s Little Theorem,
we have that x to the 6 is congruent to 1 mod 7, then squaring gives us x is congruent to 12…
or x to the 12 is congruent to 1 mod 7, sorry.
Substituting gives - so we can get rid of the x to the 12,
this becomes x squared plus 4,
and then let's just try all the possibilities, right?
There's only 3, plug them in, you get 5, 1, and 6,
none of 5, 1, and 6 are 7, and 3 wasn't 7 either,
and so we have at 7 never divides this integer.
And we're done.
So hopefully this gives you a little bit of insight as to how to use FLT to solve a
slightly different example,
and that's all I have to say.
Again, maybe I'll say one last thing, I have one more thing to say,
try some of these on your own. Make sure you understand the statement of Fermat’s Little Theorem,
and make sure - this is one of these theorems that you really do want to memorize.
You don't want to have to look it up every time you need to use it. You just want to use it
when you need it and go through.
The same can be said about a lot of these Properties of Congruences.
You probably don't want to be stating every single time
oh I added two numbers that were the same
and so I use Properties of Congruences.
You probably just want to do this more naturally and more fluidly
like you would with an equal sign, right?
You wouldn't write down every time you say, for example, switched
a and b in a plus b, right?
That would just be too much,
right, and it's the same sort of thing with congruences.
You want to be able to do these as quickly as you would deal with an equality.
So hopefully this gives you a little bit more confidence. Good luck with your assignment.