Fermat’s little theorem

[James Smithson]

I know how it works and I have been answering lots of questions and getting them correct however I have stumbled upon some question that to me makes no sense and I belive it may be a translation issue for me as sometimes I translate it wrong with English as a second language.


The question in hand is saying the following

Let p be a prime number with p (not equal) 3.
Use Fermat’s little theorem to find an integer b such that 3^(8p−4) ≡ b (mod p)


My understanding so far in this topic is that

a^p-1 ≡ 1(mod p)

so im trying to understand the question and i plug in what translates to me so :

a=3?
b=1?

so
a^(8p−4) ≡ 1 (mod p)

but then this is not the rule what is this 8 and 4 and how can i understand with no prior explanation.

I feel very dumb today that I do not understand the way to do it.


thank you for any help it is always appreciated

James

 

[fresh_42]

The statement is actually [imath] a^p\equiv a\pmod{p} [/imath] which reduces to [imath] a^{p-1}\equiv 1\pmod{p} [/imath] only in case [imath] p\nmid a . [/imath]

This is the case if [imath] a=3\neq p [/imath] as in your example, but not automatically. We get by using the original statement of Fermat's little theorem the equation
[math] 3^{(8p-4)}=(3^8)^p\cdot 3^{-4} \equiv (3^8)\cdot 3^{-4}=3^4=81\pmod{p}. [/math]Here is where we need [imath] p\neq 3 [/imath] since otherwise our equation would reduce to [imath] 0\equiv 0\pmod{3}. [/imath] We need to know [imath] p [/imath] to proceed any further so [imath] 81 [/imath] is the best we can get.

 

[mario99]

The statement is actually [imath] a^p\equiv a\pmod{p} [/imath] which reduces to [imath] a^{p-1}\equiv 1\pmod{p} [/imath] only in case [imath] p\nmid a . [/imath]

This is the case if [imath] a=3\neq p [/imath] as in your example, but not automatically. We get by using the original statement of Fermat's little theorem the equation
[math] 3^{(8p-4)}=(3^8)^p\cdot 3^{-4} \equiv (3^8)\cdot 3^{-4}=3^4=81\pmod{p}. [/math]Here is where we need [imath] p\neq 3 [/imath] since otherwise our equation would reduce to [imath] 0\equiv 0\pmod{3}. [/imath] We need to know [imath] p [/imath] to proceed any further so [imath] 81 [/imath] is the best we can get.

This is beautiful. But I would prefer to give the OP this hint and let him think.

hint: [imath]8p-4 = 8(p - 1) + 4[/imath]

 

[James Smithson]

The statement is actually [imath] a^p\equiv a\pmod{p} [/imath] which reduces to [imath] a^{p-1}\equiv 1\pmod{p} [/imath] only in case [imath] p\nmid a . [/imath]

This is the case if [imath] a=3\neq p [/imath] as in your example, but not automatically. We get by using the original statement of Fermat's little theorem the equation
[math] 3^{(8p-4)}=(3^8)^p\cdot 3^{-4} \equiv (3^8)\cdot 3^{-4}=3^4=81\pmod{p}. [/math]Here is where we need [imath] p\neq 3 [/imath] since otherwise our equation would reduce to [imath] 0\equiv 0\pmod{3}. [/imath] We need to know [imath] p [/imath] to proceed any further so [imath] 81 [/imath] is the best we can get.

I appreciate your help and can see you went in to detail but im still clueless . i think the question wants me to use a prime number thats not 3 so we could use 5 . i tried to use it in your solution and still ended up getting confused .

I appologise for my stupidity haha

 

[James Smithson]

I had another look... if i used 5 would i get the following

3^8 congruent b(mod 5)

thus b =1

i mean it seems that way as this would indeed be the remainder but i just am not sure how to word it

 

[mario99]

I had another look... if i used 5 would i get the following

3^8 congruent b(mod 5)

thus b =1

i mean it seems that way as this would indeed be the remainder but i just am not sure how to word it

You need to think why you need [imath]p \geq 83[/imath].

 

[fresh_42]

I appreciate your help and can see you went in to detail but im still clueless . i think the question wants me to use a prime number thats not 3 so we could use 5 . i tried to use it in your solution and still ended up getting confused .

I appologise for my stupidity haha

If [imath] p=5 [/imath] then
[math] 3^{8p-4}=3^{36}= 9^{18}\equiv 4^{18} \equiv (-1)^{18}=1 \pmod{5} [/math]and [imath] 81\equiv 1\pmod{5}, [/imath] too.

 

[mario99]

This is beautiful. But I would prefer to give the OP this hint and let him think.

hint: [imath]8p-4 = 8(p - 1) + 4[/imath]

You need to think why you need [imath]p \geq 83[/imath].

I will combine my hint and my post #6 to show you why they are very important to get [imath]b = 81[/imath].

I assume that you will be familiar with the properties that I will use.

[imath]\displaystyle 3^{8p - 4} \ \text{mod} \ p = 3^{8(p - 1) + 4} \ \text{mod} \ p[/imath]

[imath]\displaystyle = (3^{8(p - 1)} \cdot 3^{4}) \ \text{mod} \ p[/imath]

[imath]\displaystyle = \big[(3^{8(p - 1)} \ \text{mod} \ p) \cdot (3^{4} \ \text{mod} \ p)\big] \ \text{mod} \ p[/imath]

[imath]\displaystyle = \big[(3^{p - 1})^{8} \ \text{mod} \ p) \cdot (81 \ \text{mod} \ p)\big] \ \text{mod} \ p[/imath]

And here is the key step:

You don't know the value of [imath]81 \ \text{mod} \ p[/imath] in general when [imath]p < 81[/imath].

But

You know the value of [imath]81 \ \text{mod} \ p[/imath] in general when [imath]p > 81[/imath] which is just [imath]81[/imath]. (So [imath]81 \equiv r \ (\text{mod} \ p)[/imath] will be true by default for any [imath]3 < p < 81[/imath], although it is not obvious for the naked eyes as was explained to you by professor fresh_42 in post #7.)

So you complete your analysis with the general case that you know its values!

We have arrived to this step:

[imath]\displaystyle = \big[(3^{p - 1})^{8} \ \text{mod} \ p) \cdot (81 \ \text{mod} \ p)\big] \ \text{mod} \ p[/imath]

[imath]\displaystyle = \big[\big([3^{p - 1} \ \text{mod} \ p]^8 \ \text{mod} \ p\big) \cdot (81)\big] \ \text{mod} \ p[/imath]

[imath]\displaystyle = \big[\big([1 \ \text{mod} \ p]^8 \ \text{mod} \ p\big) \cdot (81)\big] \ \text{mod} \ p[/imath]

[imath]\displaystyle = \big[(1^8 \ \text{mod} \ p) \cdot (81)\big] \ \text{mod} \ p[/imath]

[imath]\displaystyle = \big[(1 \ \text{mod} \ p) \cdot (81)\big] \ \text{mod} \ p[/imath]

[imath]\displaystyle = \big[1 \cdot (81)\big] \ \text{mod} \ p[/imath]

[imath]\displaystyle = 81 \ \text{mod} \ p = 81[/imath]