mersenneforum.org - View Single Post - A property about the order of divisors of (Mq-1)/2

John Renze · 2005-11-14, 18:23

Quote:

Originally Posted by T.Rex

Let q prime and $\large M_q=2^q-1$ prime.

Let define: $\large order(d,2)$ the least i such that $\large 2^i \equiv \pm 1 \ \pmod{d}$ .

$\large \varphi(d)$ is the Euler function (number of numbers lower than d and coprime with d).

Then, if $\ \large d \ \mid \ (M_q-1)/2$ with d>1 , then $\large order(d,2) \ \mid \ q-1$ and $\large \ order(d,2) \ \mid \ \varphi(d)$ .

Is that well-known ?

This looks to be simple manipulations of the definition of order. For starters, $\ (M_q-1)/2 = 2^{q-1} - 1$ . Then, $2^{q-1} \equiv 1 \pmod{d}$ implies that the order of 2 modulo d divides q-1. The second claim is Lagrange's Theorem.

The definition of order you give is different from the commonly accepted one, which has 1 instead of $\pm 1$ . You may wish to consider switching.

Hope this helps,
John