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 $a^p\equiv a\pmod{p}$ which reduces to $a^{p-1}\equiv 1\pmod{p}$ only in case $p\nmid a .$

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

 

[mario99]

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

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

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

hint: $8p-4 = 8(p - 1) + 4$

 

[James Smithson]

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

This is the case if $a=3\neq p$ as in your example, but not automatically. We get by using the original statement of Fermat's little theorem the equation
$$3^{(8p-4)}=(3^8)^p\cdot 3^{-4} \equiv (3^8)\cdot 3^{-4}=3^4=81\pmod{p}.$$Here is where we need $p\neq 3$ since otherwise our equation would reduce to $0\equiv 0\pmod{3}.$ We need to know $p$ to proceed any further so $81$ 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 $p \geq 83$.

 

[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 $p=5$ then
$$3^{8p-4}=3^{36}= 9^{18}\equiv 4^{18} \equiv (-1)^{18}=1 \pmod{5}$$and $81\equiv 1\pmod{5},$ too.

 

[mario99]

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

hint: $8p-4 = 8(p - 1) + 4$

You need to think why you need $p \geq 83$.

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

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

$\displaystyle 3^{8p - 4} \ \text{mod} \ p = 3^{8(p - 1) + 4} \ \text{mod} \ p$

$\displaystyle = (3^{8(p - 1)} \cdot 3^{4}) \ \text{mod} \ p$

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

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

And here is the key step:

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

But

You know the value of $81 \ \text{mod} \ p$ in general when $p > 81$ which is just $81$. (So $81 \equiv r \ (\text{mod} \ p)$ will be true by default for any $3 < p < 81$, 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:

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

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

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

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

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

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

$\displaystyle = 81 \ \text{mod} \ p = 81$