# Application of Fermat's Little Theorem

## 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?

## Answers and Replies

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

I like Serena
Homework Helper
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.

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
Homework Helper
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
Mentor
I still think to work with ##[4^2]_{17}## is by far less complicated.

ehild
Homework Helper
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.