Mersenne primes and the modulus operation

Question

Let $p=2^q-1$ be a Mersenne prime. I then want to prove that $$ x\equiv ((x \text{ mod } 2^q) + \lfloor x/2^q\rfloor) \quad(\text{mod } p) $$ How do I do this? Any sort of help would be greatly appreciated.

Answer 1

This does not require Mersenne primes. It’s just simple in a computer because of binary arithmetic when $M=2^q.$

Given $M>0$ then:

$$x\bmod M=x-M\left\lfloor\frac xM\right\rfloor$$

So $$\begin{align}(x\bmod M) + \left\lfloor\frac xM\right\rfloor&=x-(M-1)\left\lfloor\frac xM\right\rfloor\\ &\equiv x\pmod {M-1} \end{align}$$

Your case is $M=2^q.$ wWe don’t need $M-1$ prime.

---

When $M=10,$ this is the induction step in showing that the sum of the digits of a number is congruent to the number modulo $M-1=9,$ and you get a similar result in any base $M.$

Indeed, another way to write the above proof is to write $x$ in base $M.$

Answer 2

Let's look at the congruence modulo $2^q$: This means $\exists k\in\mathbb{Z}$, s.t. $x = k\cdot 2^q + a$ for $0 \leq a \leq 2^q-1$.

Entering this into the formula yields \begin{align} k\cdot 2^q+a&\equiv \left(a + \left\lfloor \frac{k\cdot 2^q+a}{2^q}\right\rfloor\right) \mod p \\ k\cdot 2^q + a&\equiv a + k \mod p \\ 2^q &\equiv 1 \mod p \\ 2^q -1 & \equiv 0 \mod p \end{align}

Where the last equation is certainly true and by reasoning from bottom to top you get the desired equivalence.

The step from the first to the second line does work as $ a< 2^q$, so that flooring removes this part and only $k$ is left after dividing with $2^q$.