20110304, 16:16  #12  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
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 counterexamples. There was no reason to believe that an integer with Hamming weight 2 could not be a false witness to Mersenne numbers. 

20110304, 16:29  #13 
Jan 2010
germany
32_{8} Posts 

20110304, 16:39  #14  
Jan 2010
germany
2·13 Posts 
Quote:
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 with is also prime then this Mersenne Number is called Mersenne Prime. Your example with mod 511 > 9 is not prime. > 511 is not a mersenne number. And 255 = > 8 is also not prime > 255 is not a mersenne number Last fiddled with by sascha77 on 20110304 at 16:44 

20110304, 18:26  #15  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
spread throughout the literature that a Mersenne Number is of the form 2^n1 for any n . Quote:
if I look hard enough. It isn't worth my time. 

20110304, 18:52  #16 
Dec 2008
you know...around...
2×7×61 Posts 

20110304, 19:07  #17 
Jan 2010
germany
2×13 Posts 
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: WITH is prime !!! A.) let n be prime with n=2^p1: if is prime then for every and the congruence is true.  B.) Let n be not prime with n=2^p1 (But p is prime): B.1.) If you choose when the above congruence is always true. B.2.) If you choose and so that when the congruence is also always true. B.3) But for the other combinations of and 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: is always true. This is because 2 has always the order in with prime. > for every you have: Because: Now we look at the variable : (This is because of the factorisation of the form 2^{p}1) > for every you have now: > Therefore: when you choose and so that then you have: ************************************************** ************************************************** proof of B.2: If you choose and so that then is with . > ************************************************** Last fiddled with by sascha77 on 20110304 at 19:50 
20110304, 19:42  #18 
Dec 2008
you know...around...
356_{16} Posts 
Deployed some Pari code:
forprime(p=67,83,print(p);n=2^p1;for(a=2,999,for(b=0,a1,x=2^a+2^b;c=x;for(i=1,p2,c=(c^2*x)%n);c=(c^2)%n;if(c==1&&(ab)%p<>0,print("counterexample found: a="a", b="b))))) [The forprimerange 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 20110304 at 19:47 
20110304, 20:00  #19  
Jan 2010
germany
26_{10} Posts 
Quote:
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 modulooperation these values of 2^a repeat after psteps. 

20110304, 20:28  #20 
Dec 2008
you know...around...
2×7×61 Posts 
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. 
20110304, 20:53  #21  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
to 2^p1 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 weight2 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. 

20110307, 23:53  #22 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·7·479 Posts 
Unsurprisingly, there were no counterexamples up to p<1450.
A modified oneliner forprime(p=2,3000,if(!isprime(n=2^p1),print(p);for(a=1,p1,for(b=0,a1,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^p1),print(p);for(a=1,p1,for(b=0,a1,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 20110308 at 00:09 Reason: (not a master of Pari, I am) 
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  20121109 21:16 
A conjecture on a new property of Mersenne primes  Thiele  Math  18  20100523 05:35 
Number of Factors for a Mersenne Number  kurtulmehtap  Math  12  20100503 14:02 
Curious property of Mersenne numbers.  arithmeticae  Lounge  5  20081027 06:15 
A property of prime Mersenne numbers under LLT  T.Rex  Math  12  20050912 07:56 