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\pmod p$

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

  • $\begingroup$ You'd be better off positing this on Math.SE. $\endgroup$ – sju Dec 9 '14 at 5:58
  • $\begingroup$ Hint: assume $x$ is such that $2^x\equiv3\pmod p$ with $p=3\cdot2^k−1$. $\;$ What's the smallest $y$ such that $2^{x+y}\equiv1\pmod p$? $\;$ Now, assume $p$ is prime, what would be a value of $x+y$ such that $2^{x+y}\equiv1\pmod p$? That should be enough to find a value of $x$ that could do the job. Now, prove that it does. $\endgroup$ – fgrieu Dec 9 '14 at 8:44

Hint: modular inverses are unique, therefore the following holds:

$$2^x \equiv 3 \pmod{p} ~ ~ \iff ~ ~ 2^{-x} \equiv 3^{-1} \pmod{p}$$

Now what is the inverse of $3$ modulo this particular $p$? Can you express it as a power of two modulo $p$? Solve for $x$. If you end up with a negative $x$, use Fermat's little theorem to derive a positive exponent.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.