5
$\begingroup$

Find all the primes $p,q$ such that $2^{p-q}+1\equiv0\pmod{pq}$


I'm not sure how to start this. I am guessing Fermat's little theorem has something to do with this as $2^p\equiv 2\pmod{p}$ and $2^q\equiv 2\pmod{q}$. but I can't make any progress... Any help is appreciated thanks!

$\endgroup$
4
$\begingroup$

Note first that you can rewrite your starting equation as two equations via the Chinese Remainder theorem. Now you need to examine $2^{p-q}\equiv -1 \pmod{p}, 2^{p-q} \equiv -1 \pmod{q}$. Now you can apply Fermat's little theorem and take reciprocals to get to the equations $2^{p-1} \equiv -1 \pmod{q}, 2^{q-1}\equiv -1 \pmod{p}$.

Since $p-1$ and $q-1$ are even, these equations say that $-1$ is expressible as the even power of something in both $(\Bbb Z/p\Bbb Z)^\times$ and $(\Bbb Z/q\Bbb Z)^\times$. You should pursue determining which primes $p,q$ for which this is true, as a start.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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