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.

  • 1
    $\begingroup$ Hint: Using euclidean division: $q=k*2^n+a=a+k+k*(2^n-1)$, now do the computation. $\endgroup$ – Moya Sep 14 '18 at 2:30

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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.