mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-11-12, 16:54   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

91610 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2005-11-12, 23:36   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

39416 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2005-11-13, 13:13   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

22·229 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2005-11-14, 18:23   #4
John Renze
 
John Renze's Avatar
 
Nov 2005

24×3 Posts
Default

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

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.