# Application of Fermat's Little Theorem

• Enharmonics
In summary: I just didn't notice that because I wrote my reply long time ago.In summary, to find the remainder of ##4^{87}## in the division by ##17##, we can use Fermat's Little Theorem which states that if ##p## is prime and ##a## is an integer not divisible by ##p##, then ##a^{p-1} \equiv 1 (\mod \space p)##. By applying this theorem, we can rewrite ##4^{87}## as ##4^{16*5 + 7}##, and by using the definition of modulo, we can simplify it to ##4^{16}##. By noting that ##16 = 87 - 16*5
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?

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

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.

I like Serena said:
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.

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.

Enharmonics said:
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}##

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

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.

## 1. What is Fermat's Little Theorem?

Fermat's Little Theorem states that if p is a prime number, then for any integer a, the number a^p - a is an integer multiple of p.

## 2. How is Fermat's Little Theorem applied in mathematics?

Fermat's Little Theorem is commonly used in number theory and cryptography. It is used to prove the primality of numbers and to generate pseudorandom numbers.

## 3. What is the significance of Fermat's Little Theorem in cryptography?

Fermat's Little Theorem is used in the RSA encryption algorithm, which is widely used for secure communication over the internet. It helps to ensure that the encrypted message cannot be easily deciphered without the knowledge of the private key.

## 4. Can Fermat's Little Theorem be applied to non-prime numbers?

No, Fermat's Little Theorem only applies to prime numbers. It can be extended to some composite numbers, but this requires additional conditions to be satisfied.

## 5. Where can one find real-world applications of Fermat's Little Theorem?

Fermat's Little Theorem has applications in a variety of fields, including computer science, cryptography, and number theory. It is also used in the fields of physics and chemistry in the study of prime numbers and their properties.

Replies
1
Views
2K
Replies
6
Views
1K
Replies
1
Views
5K
Replies
5
Views
1K
Replies
14
Views
988
Replies
2
Views
1K
Replies
3
Views
2K
Replies
3
Views
1K
Replies
7
Views
2K
Replies
7
Views
2K