Fermat's Little Theorem - Prim. Root - Find x

80 Views Asked by At

So I am studying for finals and I am not able to solve the problem:

Let $p=3∗2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x \equiv 3 \mod p$

Any guidance or tips would be great. I assumed it dealt with Fermat's Little theorem.

1

There are 1 best solutions below

0
On

$$3\cdot2^{11484018}\equiv1\pmod p$$

$$\implies 3\equiv2^{^-11484018}$$

Now, $2^{p-1}\equiv1\pmod p\implies 2^{^-11484018}\equiv2^{p-1-11484018}\pmod p$