1
$\begingroup$

Why does the following equation hold? $$\frac{2^{lk}-1}{2^l-1}\bmod p=(2^{lk}-1)(2^l-1)^{p-2} \bmod p,$$ where $p=100000007$

That is (in more standard mathematical notation), $$\frac{2^{lk}-1}{2^l-1}\equiv (2^{lk}-1)(2^l-1)^{p-2} \pmod p$$ Does this equality depend upon value of p?

$\endgroup$
  • $\begingroup$ It depends on the fact that $p$ is prime. $\endgroup$ – Daniel Fischer Jul 28 '13 at 21:53
1
$\begingroup$

As it ends up, $p$ is a prime number. For any prime number, Fermat's little theorem tells us that

for any prime $p$, and for any $a$ for which $a\neq 0 \pmod p$: $$a^{p-1}\equiv1\pmod p$$

In this context, that means that $(2^l-1)^{p-1}\equiv 1$, as long as $2^l-1$ is not a multiple of $p$. It follows that $$ \begin{align} (2^{lk}-1)/(2^l-1) &\equiv (2^{lk}-1)/(2^l-1) * 1 \pmod p\\ &\equiv (2^{lk}-1)/(2^l-1) * (2^l-1)^{p-1} \pmod p\\ &\equiv (2^{lk}-1)(2^l-1)^{p-2} \pmod p \end{align} $$

So to directly answer your question: yes, the answer does depend on what $p$ is. This theorem will work for any prime $p$ and the right choice of $l$, but those aren't the only situations where this equality will happen to hold.

$\endgroup$
  • $\begingroup$ As long, as $p\nmid 2^l-1$, otherwise the expression is not even well-defined. For instance, take $l=0$. (More generally, $p\mid 2^l-1$, iff $ord_{\mathbb Z_p^*}(2)\mid l$) $\endgroup$ – Tomas Jul 28 '13 at 22:58

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.