If $d = \gcd(2^k - 1,\ 2^l - 1)$, is $2^{xk+yl}\equiv1\quad(\text{mod}\ d)$?

Question

I'm trying to prove that if $d = \gcd(2^k-1,\ 2^l-1)$, then $2^{xk+yl}\equiv1\quad(\text{mod}\ d)$ for integers $x,\ y$ such that $xk+yl\ge0$. My original proof used the fact that $2^k\equiv1\quad(\text{mod}\ d)$ and $2^l\equiv1\quad(\text{mod}\ d)$, and so $2^{xk}\equiv2^{yl}\equiv1\quad(\text{mod}\ d)$, and multiplying them together gives the result, but this only works when $x, y$ are positive. I tested it with python and it appears to be true so long as $xk+yl\ge0$, not just $x,\ y$ positive, but I have no clue how to prove it. Any help would be appreciated.

Answer 1

You should know that congruence also apply to fraction. We say $\dfrac{p}{q} \equiv a \pmod{d}$ for $\gcd (p,q)=1, \gcd (q,d)=1$ if $p \equiv qa \pmod{d}$. For example, $\frac{1}{4} \equiv 2 \pmod{7}$.

Thus, if $x \le 0,y \ge 0$ for example, then $2^{xk}=\dfrac{1}{2^{-xk}} \equiv 1 \pmod{d}$ because $2^{-xk} = (2^k)^{-x} \equiv 1 \pmod{d}$. Thus, $2^{xk+yl} \equiv 1 \pmod{d}$.

Note that this is true for all integers $x,y$, not just $kx+yl \ge 0$. And $(2^k)^x \equiv 1 \pmod{d}$ is true for all integers $x$ as long as $2^k \equiv 1 \pmod{d}$.