Question about a mersenne-number property - Page 3

science_man_88 · 2011-03-08, 17:44

Quote:

Originally Posted by Batalov

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

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)

it also appears faster on my machine at the same a b and n values I used in my test.

science_man_88 · 2011-03-08, 18:52

Quote:

Originally Posted by sascha77

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)$

1013 is the sum of the first 9 Mersenne numbers with x being any x. wonder what happens for p=23

CRGreathouse · 2011-03-08, 21:04

Quote:

Originally Posted by Batalov

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

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^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))
			)
		)
	)
)}

to

Code:

{forprime(p=2,3000,
	if(!isprime(n=2^p-1),
		print(p);
		two=Mod(2,n);
		for(a=1,p-1,
			t=two^a;
			for(b=0,a-1,
				c=t+two^b;
				x2=c^2;
				c=c^(2^p);
				if(c==x2,print("found: a="a", b="b))
			)
		)
	)
)}

sascha77 · 2011-03-08, 21:51

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^p-1 (p prime).

And the following:

$3^{n-1} \equiv\;1\;(mod\; n)$

was from many people already intensive searched and no one has still found an composite number n=2^p-1 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.

sascha77 · 2011-03-09, 00:10

I will now try to proof that if somebody have found an composite number n=2^p-1 (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) $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$

For every prime number $p$ and for every $a$ and $b$ with $0\le a \le p-2 \; , \; (a+1) \le b \le (p-1)$
is the above congruation false with $n=2^{p}-1$ if $n$ 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 $a$ and $b$ with an same value k then
the result will be the same. (Regardless if $n$ is prime or not)

$n=2^{p}-1$ , $p$ is prime

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

for every $k \in N$ 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.

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

---> $(2^{a}+2^{b+1})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$

--------------------------------------------------------------------

******************************************************
proof of (2):

$ (2^{a}+2^{b})^{n-1} \equiv \; (2^{a}+2^{b}) * (2^{a}+2^{b})^{n-2} $

$ \equiv \; 2^{a} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^{a}+2^{b})^{n-2}$

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

$\equiv \;2^{a} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2}$

$\equiv \; 2^{a} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2} + 2^{b} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2}$

$\equiv \; 2^{a+k} * ( 2^{a+k}+2^{b+k})^{n-2} + 2^{b+k} * (2^{a+k}+2^{b+k})^{n-2}$

$\equiv (2^{a+k}+2^{b+k})^{n-1}$

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

proof of (3) :

lets Define a function $f(x) = 2*x-1$

if we now do the function with the left and right side we get:

$f( (2^{a}+2^{b})^{n-1}) \; \equiv\; f(1) \;(\;mod\;n)$
$2*(2^{a}+2^{b})^{n-1}-1\; \equiv\; 1 \;(\;mod\;n)$

The congruence is still the neutral element 1.

And if we have found an a and an b so that the congruence is true:

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

We can now because of (1) upper the variables a and b by a value k so that (a+k) = 0.

We then have :

$(2^{0}+2^{b'})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$

----> $(2^{0}+2^{b'})^{n}\; \equiv\; 2^{0}+2{b'} \;(\;mod\;n)$

Now we use also here the function f(x):
(First multiply then subtract one)

$2^{0}+2^{b'} \;(\;mod\;n)\; / * 2$
$\equiv \; 2^{1}+2^{b'+1} \;(\;mod\;n)\;$

Now subtract the number 1:

$\equiv \; 2^{1}+2^{b'+1} \;\;-1 \; \equiv \; 2^{0}+2^{b'+1} \;(\;mod\;n)\; $
$\equiv (2^{0}+2^{b'+1})^{n} \; (\;mod \; n)$

Then we shift the exponents both back so that $2^{(0)}$ gets to its initial value $2^{(a)}$
we then have:

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

And if we do recursive this method we can make the distance between a and b as big as we want.

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

sascha77 · 2011-03-09, 00:13

Quote:

Originally Posted by science_man_88

1013 is the sum of the first 9 Mersenne numbers with x being any x. wonder what happens for p=23

I do not know exactly what you mean.
Is it possible that you show me your idea with an example ?

thanks.

wblipp · 2011-03-09, 02:53

Quote:

Originally Posted by sascha77

I think we do not need to calculate more.

Are you still working on this? See Bob Silverman's hint in post #3. It follows VERY quickly from that hint.

Batalov · 2011-03-09, 02:56

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^29-1. It is probably known. And then many for 2^23-1 and many more for 2^29-1...

R.D. Silverman · 2011-03-09, 03:43

Quote:

Originally Posted by sascha77

I will now try to proof that if somebody have found an composite number n=2^p-1 (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) $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$

For every prime number $p$ and for every $a$ and $b$ with $0\le a \le p-2 \; , \; (a+1) \le b \le (p-1)$
is the above congruation false with $n=2^{p}-1$ if $n$ 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 $a$ and $b$ with an same value k then
the result will be the same. (Regardless if $n$ is prime or not)

$n=2^{p}-1$ , $p$ is prime

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

for every $k \in N$ the congruence is true.

You are disguising what is going on. All you have done is multiply
(2^a + 2^b)^(n-1) by 2^(k(n-1)) [all mod n]

But 2^(n-1) = 1 for all n = 2^p-1, even when 2^p-1 isn't prime, because
2 is always a false withness for 2^p-1.

I will look at the rest later. I am sleepy at the moment.

CRGreathouse · 2011-03-09, 06:32

Quote:

Originally Posted by Batalov

Are there any* known false witnesses for 2^p-1 with prime p>11?

Sure -- are there any composite 2^p - 1, p > 11 prime, lacking false witnesses?

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.

ATH · 2011-03-09, 14:07

I find the subject of witness and false/non-witness for Miller-Rabin 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 non-witness 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=2p-1 and r odd.

I have my own conjecture for n=p^2, p prime:
The number of non-witnesses is p-1, and they are pairwise symmetric about p^2/2, the 1st is 1 and the p-1'th is p^2-1.
If we call the k'th non-witness nw(k) then: nw(k)+nw(p-k) = p^2.

It is only based on computations not on heuristics or any attempt to prove it.

2011-03-09, 00:10	#27
sascha77 Jan 2010 germany 2×13 Posts	I will now try to proof that if somebody have found an composite number n=2^p-1 (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) $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ For every prime number $p$ and for every $a$ and $b$ with $0\le a \le p-2 \; , \; (a+1) \le b \le (p-1)$ is the above congruation false with $n=2^{p}-1$ if $n$ 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 $a$ and $b$ with an same value k then the result will be the same. (Regardless if $n$ is prime or not) $n=2^{p}-1$ , $p$ is prime $(2^{a+k}+2^{b+k})^{n-1}\; \equiv\; (2^{a}+2^{b})^{n-1}\;(\;mod\;n)$ for every $k \in N$ 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. $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ ---> $(2^{a}+2^{b+1})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ -------------------------------------------------------------------- ****************************************************** proof of (2): $<br /> (2^{a}+2^{b})^{n-1} \equiv \; (2^{a}+2^{b}) * (2^{a}+2^{b})^{n-2}<br />$ $<br /> \equiv \;<br /> 2^{a} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^{a}+2^{b})^{n-2}$ $\equiv \; 2^{a} * 1 * (2^{a}+2^{b})^{n-2} + 2^{b} * 1 * (2^{a}+2^{b})^{n-2}<br /> \equiv \; 2^{a} * (2^k)^{n-1} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^k)^{n-1} * (2^{a}+2^{b})^{n-2} \;$ $\equiv \;2^{a} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2} + 2^{b} * (2^k)^{n-2} * 2^{k} * (2^{a}+2^{b})^{n-2}$ $\equiv \;<br /> 2^{a} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2} + 2^{b} * 2^{k} * (2^{k} * (2^{a}+2^{b}))^{n-2}$ $\equiv \;<br /> 2^{a+k} * ( 2^{a+k}+2^{b+k})^{n-2} + 2^{b+k} * (2^{a+k}+2^{b+k})^{n-2}$ $\equiv<br /> (2^{a+k}+2^{b+k})^{n-1}$ ****************************************************** proof of (3) : lets Define a function $f(x) = 2x-1$ if we now do the function with the left and right side we get: $f( (2^{a}+2^{b})^{n-1}) \; \equiv\; f(1) \;(\;mod\;n)$ $2(2^{a}+2^{b})^{n-1}-1\; \equiv\; 1 \;(\;mod\;n)$ The congruence is still the neutral element 1. And if we have found an a and an b so that the congruence is true: $(2^{a}+2^{b})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ We can now because of (1) upper the variables a and b by a value k so that (a+k) = 0. We then have : $(2^{0}+2^{b'})^{n-1}\; \equiv\; 1 \;(\;mod\;n)$ ----> $(2^{0}+2^{b'})^{n}\; \equiv\; 2^{0}+2{b'} \;(\;mod\;n)$ Now we use also here the function f(x): (First multiply then subtract one) $2^{0}+2^{b'} \;(\;mod\;n)\; / * 2$ $\equiv \; 2^{1}+2^{b'+1} \;(\;mod\;n)\;$ Now subtract the number 1: $\equiv \; 2^{1}+2^{b'+1} \;\;-1 \; \equiv \; 2^{0}+2^{b'+1} \;(\;mod\;n)\; <br />$ $\equiv (2^{0}+2^{b'+1})^{n} \; (\;mod \; n)$ Then we shift the exponents both back so that $2^{(0)}$ gets to its initial value $2^{(a)}$ we then have: $<br /> \equiv (2^{a}+2^{b+1})^{n} \; (\;mod \; n)$ 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 2011-03-09 at 00:22

2011-03-09, 02:56	#30
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10059₁₀ 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^29-1. It is probably known. And then many for 2^23-1 and many more for 2^29-1... Last fiddled with by Batalov on 2011-03-09 at 03:46*

2011-03-09, 14:07	#33
ATH Einyen Dec 2003 Denmark 19·181 Posts	I find the subject of witness and false/non-witness for Miller-Rabin 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 non-witness for all numbers. Conjecture 1 checks out for all 168,331 n=pq<10^6 where p,q are distinct primes. Conjecture 2 checks out for n=pq<510^8 p,q primes where p=2r+1, q=4r+1=2p-1 and r odd. I have my own conjecture for n=p^2, p prime: The number of non-witnesses is p-1, and they are pairwise symmetric about p^2/2, the 1st is 1 and the p-1'th is p^2-1. If we call the k'th non-witness nw(k) then: nw(k)+nw(p-k) = p^2. It is only based on computations not on heuristics or any attempt to prove it. Last fiddled with by ATH on 2011-03-09 at 14:11*

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

2011-03-08, 21:51	#26
sascha77 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^p-1 (p prime). And the following: $3^{n-1} \equiv\;1\;(mod\; n)$ was from many people already intensive searched and no one has still found an composite number n=2^p-1 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.