View Single Post
Old 2005-11-14, 18:23   #4
John Renze
John Renze's Avatar
Nov 2005

3016 Posts

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 Renze is offline   Reply With Quote