1

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?

dfeuer
  • 9,069
user74207
  • 197

1 Answers1

1

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.

Ben Grossmann
  • 225,327
  • 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$) – Tomas Jul 28 '13 at 22:58