# Application of Fermat's Little Theorem

Tags:
1. Nov 19, 2016

### Enharmonics

1. The problem statement, all variables and given/known data

Find the remainder of $4^{87}$ in the division by $17$.

2. Relevant equations

Fermat's Little Theorem:

If $p$ is prime and $a$ is an integer not divisible by $p$, then

$a^{p-1} \equiv 1 (\mod \space p)$

or equivalently,

$a^p \equiv a (\mod \space p)$

3. The attempt at a solution

I began by directly applying the theorem, since $p=17$ is prime and doesn't divide $a=4$:

$17|4^{17} - 4 \rightarrow 17|4(4^{16} - 1) \rightarrow 17|4^{16}-1$

By definition of the modulo, $p|a-b \rightarrow a \equiv b (\mod \space p)$ , so $4^{16} \equiv 1 (\mod \space 17)$

Next I note that $87 = 16 * 5 + 7$, so

$[4^{87}]_{17} = [4^{16*5 + 7}]_{17} = [4^{16*5}]_{17} * [4^7]_{17} = [4^{16}]^5_{17} * [4^7]_{17} = [1]^5_{17} * [4^7]_{17} = [1]_{17} * [4^7]_{17} = [4^7]_{17}$

Then I repeated the process from the beginning based on the result I just got:

$17|4^7 - 4 \rightarrow 17|4(4^6 - 1) \rightarrow 17|4^6-1$, where $4^6 \equiv 1 (\mod \space 17)$

Since $87 = 6 * 14 + 3$, I wrote

$[4^{87}]_{17} = [4^{6*14 + 3}]_{17} = [4^6]^{14}_{17} * [4^3]_{17} = [1]_{17} * [4^3]_{17} = [4^3]_{17}$

At this point it seems easy enough to note that $4^3 = 64$ and

$64 = 17*3 + 13$

So the remainder is 13... I think? Is this procedure correct?

Just in case it is, I actually tried repeating the process once more when I got $[4^3]_{17}$, so that

$17|4^3 - 4 \rightarrow 17|4(4^2 - 1) \rightarrow 17|4^2 -1$

And, repeating the same procedure of rewriting the exponent, arrived at $[4^{87}]_{17} = [4]_{17}$.

Of course, 4 doesn't yield a remainder of 13 when divided by 17, unlike $4^7$ and $4^3$.

Naturally, it's easy enough to note that $4^2 -1 < 17$, so $17$ doesn't divide $4^2 - 1$. I'm a little confused here, though... is it necessary for the term $a^{p-1} - 1$ to be larger than $p$ for the application of the theorem to work?

2. Nov 19, 2016

### Staff: Mentor

I haven't checked your calculation, but why don't you work with $4^2$?

3. Nov 19, 2016

### I like Serena

Hi Enharmonics!

You were fine until you "repeated the process".
Unfortunately $17|4^7-4$ is not true.
Where did you get it from? It's not Fermat's little theorem.

$[4^6]_{17}=[(4^3)^2]_{17}=[64^2]_{17}=[13^2]_{17}=[(-4)^2]_{17}=[16]_{17}=[-1]_{17}$

So we have $4^6\equiv -1 \pmod{17}$ and $17|4^7+4$.
It's by accident that it still yields the correct remainder 13.

4. Nov 19, 2016

### Enharmonics

I got $17|4^7-4$ from the fact given by re-applying the fact that $p|a^p-a$ (taken from Fermat's Little Theorem). I thought that since I found it by using the fact that $17|4^{17} - 4$, it would be okay to use. I kinda suspected it wasn't okay, since it would be uncharacteristically easy and formulaic given the subject matter (Discrete Math), so imagine how excited I was when I actually got the right answer! (even though it turned out to be by accident)

I'm a bit lost now, though. If $17|4^7-4$ isn't valid, how come you start at $[4^6]_{17}$ when our last result was $[4^87]_{17} = [4^7]_{17}$? Is it by using the fact that $a^{p-1} = 1 (\mod \space p)$?

Also, how did you do these particular steps:

$... [64^2]_{17}=[13^2]_{17}=[(-4)^2]_{17}= ...$

Is it just by using the Division Algorithm, i.e. $64 = 17*1 + 13$, $13 = 17*1 + (-4)$ ?

Finally, how do I use the final result $4^6 = -1 (\mod \space 17)$ and $17|4^7 +4$ to show that the remainder is 13?

Thanks.

5. Nov 20, 2016

### I like Serena

... but that's not a re-application...
A reapplication is either $7|4^7-4$ or $17|4^{17}-4$.
That's because the $p$ occurs twice and has to be the same!

Yes. It's the division algorithm.

Let's get back on track.
We have:

$[4^{87}]_{17} \equiv 4^{7} \equiv (4^3)^2\cdot 4 \equiv 64^2 \cdot 4 \equiv (-4)^2 \cdot 4 \equiv 64 \equiv 13 \pmod{17}$

6. Nov 20, 2016

### Staff: Mentor

I still think to work with $[4^2]_{17}$ is by far less complicated.

7. Nov 20, 2016

### ehild

Fermat's Little was not needed. 487=4*1643=4*(17-1)43. From the Binomial Theorem, all terms of (a-1)n divides by a, except the last term, which is (-1)n. So 1643=-1 mod 17. It is straightforward from here.
edit: I think it is the same as fresh's hint.