- #1

- 29

- 2

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