View Single Post
2005-11-14, 18:23   #4
John Renze

Nov 2005

3016 Posts

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