Hello everyone. In this video, I'd like to talk about the following problem as an application of Fermat's Little Theorem.
Does $7$ divide $x^{12}+x^2+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^{12}$ seems like a very big number and, 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 the solution to this, okay, so first off we want to know if $7$ divides $x^{12}+x^2+3$, then what are we really trying to do? We are trying to determine if
$$x^{12}+x^2+3\equiv 0\pmod 7$$How do we do this? Well let's examine the following: Fermat’s Little Theorem states that
$$a^6\equiv 1 \pmod 7$$whenever $7\nmid a$.
So let's see where Fermat’s Little Theorem comes into play. So in this setting, with $p=7$, so remember $7$ is a prime, here we have $a^{p-1}=a^6\equiv 1 \pmod 7$. This is true whenever $7\nmid a$. If $7\mid a$ then $a^{anything}\equiv 0 \pmod 7$
So if we want to use this, then we need to show that $7\nmid x$. So first let's break this up into the case when it does.
So if $7\mid x$ then what do we know? Okay so here we can just actually compute this. If $7\mid x$, then $x\equiv 0\pmod 7$.
$$x^{12}+x^2+3\equiv (0)^{12}+(0)^2+3\equiv 3\pmod 7$$So here we see that when $x\equiv 0$, then this polynomial is definitely not $0$. So $7\nmid x^{12}+x^2+3$ when $7\mid x$.
So now what can we do? Well now let's suppose that $7\nmid x$. What do we get now? Now we can use Fermat’s Little Theorem, right? By F$\ell$T, we have that $x^6\equiv 1\pmod 7$ and squaring gives that $x^{12}\equiv 1 \pmod 7$. Substituting gives
$$x^{12}+x^2+3\equiv 1+x^2+3\equiv x^2+4\pmod 7$$Now we're looking to see if $x^2+4\equiv 0 \pmod 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\nmid 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 $\pm 1$, $\pm 2$, and $\pm 3$. 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
$$\begin{align*} (\pm 1)^2+4&\equiv 5 \pmod 7\\ (\pm 2)^2+4&\equiv 1 \pmod 7\\ (\pm 3)^2+4&\equiv 6 \pmod 7 \end{align*}$$So none of these values are $0$, therefore $7\nmid x^{12}+x^2+3$.
And that's it. So this gives us a complete proof. Let's start from the top and see what happened, okay? So we asked the question: does $7$ divide $x^{12}+x^2+3$ for some integer $x$? What are we trying to determine? We're trying to determine if $x^{12}+x^2+3\equiv 0\pmod 7$.
So what's the idea here? Well $x^{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^{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^6\equiv 1 \pmod 7$. So in particular, $3^{12}\equiv 1 \pmod 7$, that'll make life easier because anytime $7\nmid x$, then we can say that $x^{12}\equiv 1$.
So let's do that. So first off, we take care of the case when $7\mid 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\nmid x$, so by Fermat’s Little Theorem, we have that $x^6\equiv 1\pmod 7$, then squaring gives us $x^{12}\equiv 1 \pmod 7$.
Substituting gives $x^{12}+x^2+3\equiv x^2+4 \pmod 7$, 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\nmid x^{12}+x^2+3$. And we're done.
So hopefully this gives you a little bit of insight as to how to use F$\ell$T to solve a slightly different example. Again, maybe I'll say one last thing, try some of these on your own. Make sure you understand the statement of Fermat’s Little Theorem. 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+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.