Prove that $q\equiv (q\mod 2^n)+\lfloor\frac{q}{2^n}\rfloor(\mod 2^n-1)$

Question

Prove that $q\equiv (q\mod 2^n)+\lfloor\frac{q}{2^n}\rfloor(\mod 2^n-1)$.

This expression is given in Lucas-Lehmer Primality Test. I am wondering if there is a proof of this, as it is not listed on the page. Thank You.

Answer 1

Let $a$ and $q$ be positive integers. Then we can write $q$ in terms of $a$ as $$q = \alpha a + \beta,$$ where integers $\alpha \ge 0$ and $0 \le \beta < a$ are the quotient and remainder after division when $q$ is divided by $a$. Observe that $$q \equiv \beta \mod{a},$$ and $$\left\lfloor \frac{q}{a}\right\rfloor = \left\lfloor \alpha + \frac{\beta}{a}\right\rfloor = \alpha.$$ Therefore, $$q = a\cdot \left\lfloor \frac{q}{a}\right\rfloor + (q \mod{a}) = (a-1)\cdot \left\lfloor \frac{q}{a}\right\rfloor +\left\lfloor \frac{q}{a}\right\rfloor+ (q \mod{a}).$$ Consequently, $$q \equiv (q \mod{a}) + \left\lfloor \frac{q}{a}\right\rfloor \mod{a-1}.$$ In your case, $a = 2^n$.