Order of 3 modulo a Mersenne prime

  • Thread starter T.Rex
  • Start date
  • Tags
    Prime
In summary, the conversation discusses a conjecture about the Mersenne prime numbers and the order of 3 in relation to them. The conjecture is that the highest power of 3 that divides the order of 3 mod Mq is 2. However, this conjecture is proven wrong by counter-examples found by David BroadHurst. The conversation also mentions updates to the paper and the possibility of a new conjecture.
  • #1
T.Rex
62
0
Hi,

I have the following (new, I think) conjecture about the Mersenne prime numbers, where: [tex]M_q = 2^q - 1[/tex] with [tex]q[/tex] prime.
I've checked it up to q = 110503 (M29).

Conjecture (Reix): [tex]\large \ order(3,M_q) = \frac {M_q - 1}{3^O}[/tex] where: [tex]\ \large O = 0,1,2[/tex] .

With [tex]I =[/tex] greatest [tex]i[/tex] such that [tex]M_q \equiv 1 \pmod{3^i}[/tex] , then we have: [tex]O \leq I[/tex] but no always: [tex]O = I[/tex] .

A longer description with experimental data is available at: ConjectureOrder3Mersenne.

Samuel Wagstaff was not aware of this conjecture and has no idea (yet) about how to prove it.

I need a proof...
Any idea ?

Tony
 
Physics news on Phys.org
  • #2
If I understand this correctly we are supposing that 3^3 is the highest dividing power, but take the 27th Mersenne prime, as shown in a table, and consider: [tex]\frac{2^{44496}-1}{81} [/tex] is an integer.

Also, I would suggest trying to check out the 40th Mersenne prime, and find, [tex]\frac{2^{20996010}-1}{243}[/tex] is an integer.
 
Last edited:
  • #3
T.Rex: I've checked it up to q = 110503 (M29)

If you want to see some check work on Mersenne 27, notice that 2^2000==4 Mod 81.

Thus dividing out 44496/2000 = 22 + Remainder 496. 496 = 2*248. Thus:

[tex]4^{22}*4^{248}-1\equiv 4^{270}-1 \equiv0 Mod 81 [/tex]
 
  • #4
The conjecture is wrong.

The conjecture is wrong.
David BroadHurst has found counter-examples.
The terrible "law of small numbers" has struck again... :cry::mad::confused::frown: (but the numbers were not so small...).
I've updated the paper and just conjectured that the highest power of 3 that divides the order of 3 mod M_q is 2. But it is not so much interesting...
Never mind, we learn by knowing what's false too.
I've updated the http://tony.reix.free.fr/Mersenne/ConjectureOrder3Mersenne.pdf" [Broken].
Sorry, the way David found the counter-examples was not so difficult...
Tony
 
Last edited by a moderator:
  • #5
robert Ihnot said:
If I understand this correctly we are supposing that 3^3 is the highest dividing power...
Not exactly, Robert. For q=44497, 4 is the highest power of 3 that divides Mq-1, but 1 is the highest power of 3 in the relationship between (Mq-1) and order(3,Mq).
I have other reasons to think that 2 is the highest power of 3 in this relationship. But I need to clarify that before conjecturing again (one mistake is enough !).
Thanks,
Tony
 

1. What is the "Order of 3 modulo a Mersenne prime"?

The "Order of 3 modulo a Mersenne prime" refers to the smallest positive integer k such that 3k ≡ 1 (mod p), where p is a Mersenne prime. In other words, it is the smallest power of 3 that leaves a remainder of 1 when divided by the Mersenne prime.

2. How is the order of 3 modulo a Mersenne prime calculated?

The order of 3 modulo a Mersenne prime can be calculated using the primitive root theorem. This theorem states that the order of an integer a modulo n is equal to φ(n), where φ is Euler's totient function and represents the number of positive integers less than n that are relatively prime to n. In the case of 3 modulo a Mersenne prime, the order is equal to φ(p).

3. What is the significance of the order of 3 modulo a Mersenne prime?

The order of 3 modulo a Mersenne prime has significant implications in the field of number theory. It is closely related to the discrete logarithm problem, which is used in various cryptographic algorithms. Additionally, the order of 3 modulo a Mersenne prime is also connected to the Carmichael function, which has applications in cryptography and prime number factorization.

4. Can the order of 3 modulo a Mersenne prime be any number?

No, the order of 3 modulo a Mersenne prime can only be certain values. By Fermat's little theorem, the order must be a divisor of p-1. In addition, the order cannot be equal to p-1 itself, as that would make 3 a primitive root of p, which is not possible for Mersenne primes.

5. How does the order of 3 modulo a Mersenne prime relate to the distribution of primes?

The order of 3 modulo a Mersenne prime has been used to study the distribution of primes. It has been shown that for certain values of k, there are infinitely many Mersenne primes of the form 3k − 1. This has led to further research on the generalized Riemann hypothesis, which is a conjecture about the distribution of prime numbers.

Similar threads

Replies
5
Views
314
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Linear and Abstract Algebra
Replies
11
Views
3K
  • Linear and Abstract Algebra
Replies
9
Views
3K
  • Linear and Abstract Algebra
Replies
1
Views
622
  • Linear and Abstract Algebra
Replies
11
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
929
  • Linear and Abstract Algebra
Replies
5
Views
2K
Back
Top