A property about the order of divisors of (Mq-1)/2

T.Rex · 2005-11-12, 16:54

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 ?

(It is a consequence of a paper I'm reading now)

Examples:
$\large q=5 \ , \ (M_q)/2=3*5$
$\large d=3 : \ order(d,2)=1 ,\ \varphi(d)=2$
$\large d=5 : \ order(d,2)=2 ,\ \varphi(d)=4$
$\large d=15 : \ order(d,2)=4 ,\ \varphi(d)=4$

$\large q=7 \ , \ (M_q)/2=3^2*7$
$\large d=3 : \ order(d,2)=1 ,\ \varphi(d)=2$
$\large d=7 : \ order(d,2)=3 ,\ \varphi(d)=6$
$\large d=9 : \ order(d,2)=6 ,\ \varphi(d)=6$
$\large d=21 : \ order(d,2)=6 ,\ \varphi(d)=12$
$\large d=63 : \ order(d,2)=6 ,\ \varphi(d)=36$

$\large q=13 \ , \ (M_q)/2=3^2*5*7*13$
$\large d=13 : \ order(d,2)=6 ,\ \varphi(d)=12$
etc
$\large d=65 : \ order(d,2)=6 ,\ \varphi(d)=48$
$\large d=91 :\ order(d,2)=12 ,\ \varphi(d)=72$
etc
$\large d=4095 : \ order(d,2)=12 ,\ \varphi(d)=1728$

Tony

T.Rex · 2005-11-12, 23:36

I've checked only with some q primes (109, 103, 101, 97, 83, 37, 13, 7) , but it seems that:

$\large \ d \ \mid \ M_q \ \Rightarrow \ order(d,2) = q \$ , where $\large \ order(d,2)$ is the least i such that $\large \ 2^i \ \equiv 1 \ \pmod{d}$ .

Is this property already well-known ?

Tony

T.Rex · 2005-11-13, 13:13

Quote:

Originally Posted by T.Rex

I've checked only with some q primes (109, 103, 101, 97, 83, 37, 13, 7) , but it seems that ...

This is stupid. It is the definition of d being a divisor of Mq. (I should learn more elementary Number Theory, spend more time searching by my-self, and thus say less garbage on this forum. Isn't it, Bob ?)

What about the property in first post of this thread ?
(This property is not mine. So it is probably less stupid than my own tries.)

(In the examples, $\large (M_q)/2$ should be: $\large (M_q-1)/2$ .)

Tony

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

2005-11-12, 16:54	#1
T.Rex Feb 2004 France 3×311 Posts	A property about the order of divisors of (Mq-1)/2 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 ? (It is a consequence of a paper I'm reading now) Examples: $\large q=5 \ , \ (M_q)/2=35$ $\large d=3 : \ order(d,2)=1 ,\ \varphi(d)=2$ $\large d=5 : \ order(d,2)=2 ,\ \varphi(d)=4$ $\large d=15 : \ order(d,2)=4 ,\ \varphi(d)=4$ $\large q=7 \ , \ (M_q)/2=3^27$ $\large d=3 : \ order(d,2)=1 ,\ \varphi(d)=2$ $\large d=7 : \ order(d,2)=3 ,\ \varphi(d)=6$ $\large d=9 : \ order(d,2)=6 ,\ \varphi(d)=6$ $\large d=21 : \ order(d,2)=6 ,\ \varphi(d)=12$ $\large d=63 : \ order(d,2)=6 ,\ \varphi(d)=36$ $\large q=13 \ , \ (M_q)/2=3^257*13$ $\large d=13 : \ order(d,2)=6 ,\ \varphi(d)=12$ etc $\large d=65 : \ order(d,2)=6 ,\ \varphi(d)=48$ $\large d=91 :\ order(d,2)=12 ,\ \varphi(d)=72$ etc $\large d=4095 : \ order(d,2)=12 ,\ \varphi(d)=1728$ Tony

2005-11-12, 23:36	#2
T.Rex Feb 2004 France 3×311 Posts	A property of divisors of Mq ? I've checked only with some q primes (109, 103, 101, 97, 83, 37, 13, 7) , but it seems that: $\large \ d \ \mid \ M_q \ \Rightarrow \ order(d,2) = q \$ , where $\large \ order(d,2)$ is the least i such that $\large \ 2^i \ \equiv 1 \ \pmod{d}$ . Is this property already well-known ? Tony

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Looking for fermat divisors, n=90-120	firejuggler	Prime Sierpinski Project	2	2012-01-10 17:14
Sum of two squares: Peculiar property	Raman	Puzzles	13	2010-02-13 05:25
MMO Property Calculation	Bundu	Puzzles	22	2009-09-22 01:30
Number of divisors of n?	Citrix	Math	10	2006-02-08 04:09
Special property for mod	dsouza123	Math	4	2003-10-31 05:49