Application of Fermat's Little Theorem

[Enharmonics]

Homework Statement

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

Homework 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)$

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?

 

[fresh_42]

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

 

[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.

Instead we have:
$[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.

 

[Enharmonics]

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.

Instead we have:
$[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.

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.

 

[I like Serena]

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)

... 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!

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?

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}$

 

[fresh_42]

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

 

[ehild]

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