mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-03-04, 16:16   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

164748 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You just changed your original statement.

Your original statement was that x^n = x is not true when n = 2^p-1
is composite. Here x = 2^a + 2^b for a!= b

This is different from x^{n-1} = 1 is not true when n = 2^p-1 is
composite.
Note that 34 = 2^1 + 2^5 and 34^255 = 34 mod 255. Enough said?

Not enough? Note that 65 = 2^0 + 2^6 and 65^510 = 1 mod 511.

Still not enough? 72 = 2^3 + 2^6 and 72^510 = 1 mod 511.

I am sure that one could find additional counter-examples.

There was no reason to believe that an integer with Hamming weight 2
could not be a false witness to Mersenne numbers.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-04, 16:29   #13
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

Quote:
Originally Posted by mart_r View Post
Well, (211+21)2046 \equiv 1 (mod 2047).
a-b=10 \not\equiv 11 (mod 2047)
No. This is false.

set p=11
->n=2^{p}-1 = 2047

for this:
(2^{11}+2^{1})^{2046} \equiv (\;(2^{11} + 2^{1})\;mod(\;2047)\;)^{2046} \equiv 3^{2046} \equiv 1013\;(mod\; 2047)
sascha77 is offline   Reply With Quote
Old 2011-03-04, 16:39   #14
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Note that 34 = 2^1 + 2^5 and 34^255 = 34 mod 255. Enough said?

Not enough? Note that 65 = 2^0 + 2^6 and 65^510 = 1 mod 511.

Still not enough? 72 = 2^3 + 2^6 and 72^510 = 1 mod 511.

I am sure that one could find additional counter-examples.

There was no reason to believe that an integer with Hamming weight 2
could not be a false witness to Mersenne numbers.

OK. my fault. I forgotten to mention that mersenne Numbers are Numbers of the Form n = 2^{p}-1 with:
The variable p is prime !!!!!


If the mersenne number n with n=2^{p}-1 is also prime then this
Mersenne Number is called Mersenne Prime.



Your example with mod 511 ->  511 -> 2^{9}-1

9 is not prime. -> 511 is not a mersenne number.

And 255 = 2^{8}-1 .

-> 8 is also not prime -> 255 is not a mersenne number

Last fiddled with by sascha77 on 2011-03-04 at 16:44
sascha77 is offline   Reply With Quote
Old 2011-03-04, 18:26   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

164748 Posts
Default

Quote:
Originally Posted by sascha77 View Post
OK. my fault. I forgotten to mention that mersenne Numbers are Numbers of the Form n = 2^{p}-1 with:
The variable p is prime !!!!!
That is one definition. You will also find the definition
spread throughout the literature that a Mersenne Number is of the
form 2^n-1 for any n .




Quote:
Your example with mod 511 ->  511 -> 2^{9}-1
It is likely that I can find other counter-examples for the case n = prime
if I look hard enough.

It isn't worth my time.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-04, 18:52   #16
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

2·34·5 Posts
Default

Quote:
Originally Posted by sascha77 View Post
No. This is false.

set p=11
->n=2^{p}-1 = 2047

for this:
(2^{11}+2^{1})^{2046} \equiv (\;(2^{11} + 2^{1})\;mod(\;2047)\;)^{2046} \equiv 3^{2046} \equiv 1013\;(mod\; 2047)
Oops, sorry. Messed up 1 with 21
mart_r is offline   Reply With Quote
Old 2011-03-04, 19:07   #17
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default

I noticed that my first post in this topic was mathematically not detailled enough and I forgot to mention some assumptions.
(Especially that p must always be prime)
For this reason I redefine my previous post:



(2^a+2^b)^{n} \equiv 2^a+2^b\;(mod \;n)

n=2^{p}-1 WITH p is prime !!!

a \in N\; and\; b \in N.

A.) let n be prime with n=2^p-1:
if n is prime then for every a and b the congruence is true.

--------------------------------------------------------------------
B.) Let n be not prime with n=2^p-1 (But p is prime):

B.1.) If you choose a=b when the above congruence is always true.

B.2.) If you choose a and b so that |b-a|\equiv p\;(mod \;n)
when the congruence is also always true.

B.3) But for the other combinations of a and b the above congruence
is always false.

(A) (B.1) and (B.2) can easily be proven. But (B.3) is hard to prove.
Therefore is (B.3) my conjecture.
-----------------------------------------------------------------


**************************************************
Proof of A:
This is trivial, because A follows directly from the "Fermatsche Satz".
**************************************************

**************************************************
proof of B.1:


(2^x)^{p} \equiv 1 \;(mod\; n) is always true.

This is because 2 has always the order p in Z/Z_{(2^{p}-1)} with p prime.

2^p\equiv1\;(mod\;2^{p}-1)

-> for every x you have: (2^{x})^{p}\equiv1\;mod(2^{p}-1)
Because:

 (2^{x})^{p}=(2^{p})^{x}\equiv1^{x}\equiv1\;(mod \;2^{p}-1)

Now we look at the variable n:

n = 2^{p}-1 = (2*p*k+1) (This is because of the factorisation of the form 2^{p}-1)

->  (n-1) \equiv 0 \; (mod\; p)

for every x you have now:

(2^{x})^{n-1}\equiv1\;(mod\;n) --> <br />
    (2^{x})^{n}\equiv2^{x} \;(mod\; n)

Therefore:

when you choose a and b so that a=b then you have:

{(2^{a}+2^{a})}^{n} = {(2^{(a+1)})}^{n} \equiv 2^{a+1}\equiv 2^{a}+2^{b}\;mod\; (n)

**************************************************



**************************************************
proof of B.2:

If you choose a and b so that |b-a|\equiv p\;(mod\;n)

then b is b=(a+p*k) with k\in N.

->

(2^{a} + 2^{b})^{n}\equiv (2^{a} + 2^{(a+p*k)})^{n}\equiv ({2^{a}}+{2^{a}}*{2^{(p*k)}})^{n}\equiv (2^{a}*2^{a}*1)^{n}\equiv(2^{a+1})^{n}\equiv 2^{(a+1)} \;(mod\; n )

**************************************************

Last fiddled with by sascha77 on 2011-03-04 at 19:50
sascha77 is offline   Reply With Quote
Old 2011-03-04, 19:42   #18
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

81010 Posts
Default

Deployed some Pari code:
forprime(p=67,83,print(p);n=2^p-1;for(a=2,999,for(b=0,a-1,x=2^a+2^b;c=x;for(i=1,p-2,c=(c^2*x)%n);c=(c^2)%n;if(c==1&&(a-b)%p<>0,print("counterexample found: a="a", b="b)))))
[The forprime-range is to be set manually after every Mp=prime, e.g. next it would be forprime(p=97,103,...]

No counterexample for a<1000, b<a, p<71 yet.

I would guess there are likely to be counterexamples (e.g. Carmichael numbers with Hamming weight 2), but they're probably hard to find.

Last fiddled with by mart_r on 2011-03-04 at 19:47
mart_r is offline   Reply With Quote
Old 2011-03-04, 20:00   #19
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default

Quote:
Originally Posted by mart_r View Post
Deployed some Pari code:
forprime(p=67,83,print(p);n=2^p-1;for(a=2,999,for(b=0,a-1,x=2^a+2^b;c=x;for(i=1,p-2,c=(c^2*x)%n);c=(c^2)%n;if(c==1&&(a-b)%p<>0,print("counterexample found: a="a", b="b)))))
[The forprime-range is to be set manually after every Mp=prime, e.g. next it would be forprime(p=97,103,...]

No counterexample for a<1000, b<a, p<71 yet.

I would guess there are likely to be counterexamples (e.g. Carmichael numbers with Hamming weight 2), but they're probably hard to find.

Thanks !!!
Yes it could be that there exist a counterexample.
But nobody knows this until it is found. ;-)
A hint: You only need to test a and b to the size of p.
this means: test a for a<=p and b for b<=p
Because of the modulo-operation these values of 2^a repeat after p-steps.
sascha77 is offline   Reply With Quote
Old 2011-03-04, 20:28   #20
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

2×34×5 Posts
Default

Fair enough.

So, no counterexamples for p<=353.
Stopping here. Someone with a faster PC, i.e. with more than one core, could check further.
mart_r is offline   Reply With Quote
Old 2011-03-04, 20:53   #21
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

1D3C16 Posts
Default

Quote:
Originally Posted by sascha77 View Post
Thanks !!!
Yes it could be that there exist a counterexample.
But nobody knows this until it is found. ;-)
A hint: You only need to test a and b to the size of p.
this means: test a for a<=p and b for b<=p
Because of the modulo-operation these values of 2^a repeat after p-steps.
You are looking at the intersection of two sparse sets (false witnesses
to 2^p-1 and integers with Hamming weight 2) and hoping that the
intersection isn't empty.

There are no analytic tools available to approach the problem because
[AFAIK] there is almost nothing known about how false witnesses
are distributed mod P. It is easy to get a sharp counting function for
weight-2 integers up to B , but their distribution is clearly not uniform.

Heuristics based on probabilistic methods are likely to fail, because
the sets involved are not uniformly distributed.

Even if the result is true, it has almost no applicability anyway. LL will
be faster.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-07, 23:53   #22
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×3×1,657 Posts
Default

Unsurprisingly, there were no counterexamples up to p<1450.
A modified one-liner
forprime(p=2,3000,if(!isprime(n=2^p-1),print(p);for(a=1,p-1,for(b=0,a-1,x=2^a+2^b;c=x;for(i=3,p,c=(c^2*x)%n);if((c^2)%n==1,print("found: a="a", b="b))))))
can run without need to skip prime Mp's and can run forever lazily...


____
A bit faster:
forprime(p=2,3000,if(!isprime(n=2^p-1),print(p);for(a=1,p-1,for(b=0,a-1,x=(2^a+2^b)%n;x2=(x^2)%n;c=x;for(i=1,p,c=(c^2)%n);if(c==x2,print("found: a="a", b="b))))))

...Is there a better mod exponent in Pari? Mod(2^a+2^b,n)^n ?

Last fiddled with by Batalov on 2011-03-08 at 00:09 Reason: (not a master of Pari, I am)
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
A conjecture on a new property of Mersenne primes Thiele Math 18 2010-05-23 05:35
Number of Factors for a Mersenne Number kurtulmehtap Math 12 2010-05-03 14:02
Curious property of Mersenne numbers. arithmeticae Lounge 5 2008-10-27 06:15
A property of prime Mersenne numbers under LLT T.Rex Math 12 2005-09-12 07:56

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


Fri Oct 7 05:48:48 UTC 2022 up 50 days, 3:17, 0 users, load averages: 0.78, 1.06, 1.07

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.

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