20110308, 17:44  #23 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
best for length on a line I could fine is this (for what you do in the x and x2 parts):
Code:
Mod(Mod(2^a+2^b,n)^2,n) Last fiddled with by science_man_88 on 20110308 at 17:54 
20110308, 18:52  #24 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 

20110308, 21:04  #25 
Aug 2006
5,987 Posts 
Mod(2,n)^a + Mod(2,n)^b. For the square of that, use (Mod(2,n)^a + Mod(2,n)^b)^2. You can reduce the caculations in the inner loop by lifting Mod(2,n) and Mod(2,n)^a out of the b loop: go from
Code:
{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)) ) ) ) )} Code:
{forprime(p=2,3000, if(!isprime(n=2^p1), print(p); two=Mod(2,n); for(a=1,p1, t=two^a; for(b=0,a1, c=t+two^b; x2=c^2; c=c^(2^p); if(c==x2,print("found: a="a", b="b)) ) ) ) )} Last fiddled with by CRGreathouse on 20110308 at 21:11 
20110308, 21:51  #26 
Jan 2010
germany
2×13 Posts 
I think we do not need to calculate more.
Because I found out that if someone will find a counterexample with an a and an b so the other a's an b's must also fail for these n=2^p1 (p prime). And the following: was from many people already intensive searched and no one has still found an composite number n=2^p1 that holds the above congruation. So if we continue searching we would not find an counterexample because 3 = (2^0+2^1) I will in short try to give the proof about that. 
20110309, 00:10  #27 
Jan 2010
germany
2·13 Posts 
I will now try to proof that if somebody have found an composite number n=2^p1 (with p is prime) so that the congruence 'fails' then it must also fail for all the other a' and b's (with the same n)
I did my best, but there are certainly some errors in it. So I will be glad if someone find these errors (in the proof) and let me now. I hope that these are not evil ones ;) Ok. First I will introduce an equivalent conjecture which is much better : (1) For every prime number and for every and with is the above congruation false with if is not prime. (I do not want to proof that this conjecture is equivalent, we canjust take it as new conjecture)  Propositions: (2) If we add the two variables and with an same value k then the result will be the same. (Regardless if is prime or not) , is prime for every the congruence is true.  (3): If the congruence (1) is true for an a=a' and an b=b' then the congruence must also be true for a=a' and b=(b'+1) This means the variable a is the same but the variable b is by one greater as before. >  ****************************************************** proof of (2): ****************************************************** proof of (3) : lets Define a function if we now do the function with the left and right side we get: The congruence is still the neutral element 1. And if we have found an a and an b so that the congruence is true: We can now because of (1) upper the variables a and b by a value k so that (a+k) = 0. We then have : > Now we use also here the function f(x): (First multiply then subtract one) Now subtract the number 1: Then we shift the exponents both back so that gets to its initial value we then have: And if we do recursive this method we can make the distance between a and b as big as we want. ******************************************************* Last fiddled with by sascha77 on 20110309 at 00:22 
20110309, 00:13  #28 
Jan 2010
germany
2×13 Posts 

20110309, 02:53  #29 
"William"
May 2003
New Haven
3×7×113 Posts 

20110309, 02:56  #30 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,993 Posts 
Are there any* known false witnesses for 2^{p}1 with prime p>11?
____________ *any, not necessarily with Hamming weight 2 EDIT: yes. I've stepped out of pfgw (which only works with bases <=255) and with Pari, 'found' one: 349 for 2^291. It is probably known. And then many for 2^231 and many more for 2^291... Last fiddled with by Batalov on 20110309 at 03:46 
20110309, 03:43  #31  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×937 Posts 
Quote:
You are disguising what is going on. All you have done is multiply (2^a + 2^b)^(n1) by 2^(k(n1)) [all mod n] But 2^(n1) = 1 for all n = 2^p1, even when 2^p1 isn't prime, because 2 is always a false withness for 2^p1. I will look at the rest later. I am sleepy at the moment. 

20110309, 06:32  #32  
Aug 2006
13543_{8} Posts 
Quote:
Depending on how you count it, 2[SUP]23[/SUP]  1 has 1056, 1057, or 1058 false witnesses. 2[SUP]29[/SUP]  1 has over a hundred thousand. 

20110309, 14:07  #33 
Einyen
Dec 2003
Denmark
3,413 Posts 
I find the subject of witness and false/nonwitness for MillerRabin test interesting. I found this paper with 2 conjectures on oeis.org:
http://www.ma.iup.edu/MAA/proceedings/vol1/higgins.pdf http://oeis.org/A090659 His conjectures includes 1 as a nonwitness for all numbers. Conjecture 1 checks out for all 168,331 n=p*q<10^6 where p,q are distinct primes. Conjecture 2 checks out for n=p*q<5*10^8 p,q primes where p=2r+1, q=4r+1=2p1 and r odd. I have my own conjecture for n=p^2, p prime: The number of nonwitnesses is p1, and they are pairwise symmetric about p^2/2, the 1st is 1 and the p1'th is p^21. If we call the k'th nonwitness nw(k) then: nw(k)+nw(pk) = p^2. It is only based on computations not on heuristics or any attempt to prove it. Last fiddled with by ATH on 20110309 at 14:11 
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 