# How is the following relation involving modulo operation equal?

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?

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

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.
• 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