mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Closed Thread
 
Thread Tools
Old 2020-09-01, 02:39   #1
baih
 
baih's Avatar
 
Jun 2019

2·17 Posts
Default a nice remark about mersene composite

a nice remark
Mersenne Number 2n-1

x2 = (2n-2)-1 mod 2n-1

there is no solution for x if 2n-1 composite
baih is offline  
Old 2020-09-01, 03:16   #2
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

5·67 Posts
Post

Claim: If 2^n-1 is not prime, then 2^(n-2)-1 is a quadratic non-residue mod 2^n-1.

The claim is false, however the contrapositive is true:

If 2^n-1 is prime, then 2^(n-2)-1 is a quadratic residue mod 2^n-1.

n = 2 is a special case implying that x^2 = 0 mod 3, which has solution x = 0 (trivial).

In all other cases, n must be odd. For simplicity, suppose p = 2^n-1.

2^(n-2)-1 = (p - 3)/4

p = 1 mod 3, and since p is prime, quadratic reciprocity tells us that x^2 = -3 mod p is solvable.

Hence, x^2 = (p - 3)/4 mod p,
4*x^2 = p - 3 mod p, or (2*x)^2 = -3 mod p.
The map x --> 2*x is a bijection in Zp/Z. Done. Proven.

Now what remains is to show when your claim is false (given n is composite):

If every prime q | p is congruent to 1 mod 3, then the claim is false.

Since q = 1 mod 3, x^2 = -3 mod q will have a solution,

using the Chinese Remainder Theorem allows us to construct a solution x to x^2 = -3 mod p, so the conclusion follows.

There are infinitely many composite numbers of the form 2^n-1 such that the claim is false.

If n = 3^k, then 2^n-1 is a counterexample if k > 2, since every prime q | 2^(3^k) - 1, the order of 2 mod q by definition divides 3^k, and trivially cannot be 1, so q = 1 mod 3.

I do not find your claim interesting at all, what I find interesting is finding the density of primes n such that each prime q | 2^n-1 is congruent to 1 mod 3:

Any arbitrary integer N has about ln(ln(N)) prime factors, so 2^n-1 will have on average, ln(n) prime factors by this assumption.

The probability that all of these factors are congruent to 1 mod 3 is about 1/2^(ln(n)). I suppose there is a better estimate?
carpetpool is offline  
Old 2020-09-01, 11:32   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×1,523 Posts
Default

Quote:
Originally Posted by baih View Post
a nice remark
Mersenne Number 2n-1

x2 = (2n-2)-1 mod 2n-1

there is no solution for x if 2n-1 composite
The smallest prime exponent which furnishes a counterexample is n = 37. Thread closed.
Dr Sardonicus is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nice-to-have's kar_bon Prime Wiki 1 2019-02-26 09:57
Nice pic Dubslow Forum Feedback 0 2012-05-02 02:13
Let's do another nice big GNFS job! fivemack Factoring 84 2011-04-26 10:22
Mersene Prime and Number Theory Ricie Miscellaneous Math 24 2009-08-14 15:31
6 digit numbers and the mersene 40 Sykes1024 Math 7 2004-02-10 09:43

All times are UTC. The time now is 05:30.


Mon Nov 28 05:30:04 UTC 2022 up 102 days, 2:58, 0 users, load averages: 0.58, 0.92, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔