mersenneforum.org > Math A property about the order of divisors of (Mq-1)/2
 Register FAQ Search Today's Posts Mark Forums Read

 2005-11-12, 16:54 #1 T.Rex     Feb 2004 France 91610 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=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
 2005-11-12, 23:36 #2 T.Rex     Feb 2004 France 39416 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
2005-11-13, 13:13   #3
T.Rex

Feb 2004
France

22·229 Posts

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 ?)

(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

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

Nov 2005

24×3 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

 Similar Threads Thread Thread Starter Forum Replies Last Post firejuggler Prime Sierpinski Project 2 2012-01-10 17:14 Raman Puzzles 13 2010-02-13 05:25 Bundu Puzzles 22 2009-09-22 01:30 Citrix Math 10 2006-02-08 04:09 dsouza123 Math 4 2003-10-31 05:49

All times are UTC. The time now is 08:35.

Sat May 15 08:35:41 UTC 2021 up 37 days, 3:16, 0 users, load averages: 2.27, 1.86, 1.75

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.