Find an integer $x$ such that $2^x \equiv 3\pmod{p}$ given prime $p$

Question

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

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

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

Answer 1

You know that

Mod[a^(p - 1), p] == 1

In particular

Mod[2^(p - 1), p] == 1

And multiplying by 3

Mod[3 2^(p - 1), p] == 3

Now we divide and multiply by 2

Mod[3 2 2^(p - 2), p] == 3

Rearranging:

Mod[2 (3 2^(p - 2)), p] == 3

So

x === (3 2^(p - 2))