mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-03-09, 14:26   #34
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
Yes. That is right.
That is exactly what I meant.
Sure I could have done the proof a lot shorter and easier with the multiplikation of (2^{(k)})^{n-1)
But the result is the same.
sascha77 is offline   Reply With Quote
Old 2011-03-09, 14:37   #35
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by sascha77 View Post
proof of (3) :

lets Define a function f(x) = 2*x-1
f is a function that is well defined over R. You have failed to prove
that it is a function over Z/nZ for n = 2^p-1. In fact, one can
prove that it is a ring homomporphism. This will be sufficient for the
manipulations you want later, but it needs proof.
Quote:

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.
OK. 1 is a fixed point of the homomorphism.

Quote:
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.
OK. So you let k = n - a and put b' = b + n - a. (== b-a mod n)
Quote:
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)
OK.


Quote:
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)
OK. You have shown that if (2^a + 2^b)^(n-1) =1 mod n, then
(2^a + 2^(b+1))^n = 2^a + 2^(b+1) mod n.

But this does not prove the original proposition. You were to show
that if (2^a + 2^b)^(n-1) = 1 mod n, then (2^a + 2^(b+1))^(n-1) = 1
mod n. What you have shown is something different.

You can't use (2^a + 2^(b+1))^n = 2^a + 2^(b+1) mod n
to conclude (2^a + 2^(b+1))^(n-1) = 1 mod n UNLESS
(2^a + 2^(b+1)) is co-prime to n. There is no way to prove
the latter.

Indeed, if 2^p-1 is prime, then (2^a + 2^(b+1)) will be coprime.
But if 2^p-1 is composite, then it might not be.

Unless I missed something.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-09, 14:37   #36
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default

Quote:
Originally Posted by ATH View Post
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.

Thanks for the interesting PDF about 'miller-rabin test'.
I will read that.
sascha77 is offline   Reply With Quote
Old 2011-03-09, 15:32   #37
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111010010102 Posts
Default

Quote:
Originally Posted by ATH View Post
His conjectures includes 1 as a non-witness for all numbers.
Trivially, yes.

Quote:
Originally Posted by ATH View Post
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 think both follow from the general formula for the number of nonwitnesses, which is more complicated. See, e.g., A141768. I haven't done the derivation myself, though.

Quote:
Originally Posted by ATH View Post
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.
The symmetry follows from noticing that k^2 = (-k)^2 = (n - k)^2 mod n. The number of nonwitnesses follows from the general formula. So your conjecture is correct.
CRGreathouse is online now   Reply With Quote
Old 2011-03-09, 18:55   #38
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default

Quote:
You can't use (2^a + 2^(b+1))^n = 2^a + 2^(b+1) mod n
to conclude (2^a + 2^(b+1))^(n-1) = 1 mod n UNLESS
(2^a + 2^(b+1)) is co-prime to n. There is no way to prove
the latter.

Indeed, if 2^p-1 is prime, then (2^a + 2^(b+1)) will be coprime.
But if 2^p-1 is composite, then it might not be.

Unless I missed something.

Many thanks for your great help !
Yet I know exactly where the (big) failure is.
It seems now impossible for me too, to prove that (2^a+2^b) is always co-prime to n.
sascha77 is offline   Reply With Quote
Old 2011-03-14, 11:41   #39
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by sascha77 View Post
It seems now impossible for me too, to prove that (2^a+2^b) is always co-prime to n.
That's easy to prove.
Assume that q=\gcd(2^a+2^b,n)>1. Since p is an odd prime and 2^p \equiv 1\pmod{q}, we have that 2^k \not\equiv -1\pmod{q} for all k. On the other hand, 2^a+2^b\equiv 0\pmod{q} is equivalent to 2^{a-b}\equiv -1\pmod{q}, a contradiction. Hence, q=1.

However, that does not make your proof correct, since the last congruence below is unjustified:

Quote:
Originally Posted by sascha77 View Post
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)
maxal is offline   Reply With Quote
Old 2011-03-14, 18:36   #40
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

Quote:
Originally Posted by maxal View Post
That's easy to prove.
Assume that q=\gcd(2^a+2^b,n)>1. Since p is an odd prime and 2^p \equiv 1\pmod{q}, we have that 2^k \not\equiv -1\pmod{q} for all k. On the other hand, 2^a+2^b\equiv 0\pmod{q} is equivalent to 2^{a-b}\equiv -1\pmod{q}, a contradiction. Hence, q=1.

However, that does not make your proof correct, since the last congruence below is unjustified:

Thanks.
I like your proof. Short and elegant.
-> Yes the last congruence is unjustified.
It must be shown that we can do the f(x)=2*x-1 Operation on both sides. I did this only on the right side of this congruation:
(2^{0}+2^{b'})^{n} \equiv \; 2^{0}+2^{b'} \; (mod\; n}

(Silverman already said that the function f(x) must be shown.)
That the 'minus 1' must not influence the congruation seems for me the hard part. But if this is resolved would it then be correct ?
sascha77 is offline   Reply With Quote
Old 2011-03-14, 22:10   #41
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by sascha77 View Post
Thanks.
I like your proof. Short and elegant.
-> Yes the last congruence is unjustified.
It must be shown that we can do the f(x)=2*x-1 Operation on both sides. I did this only on the right side of this congruation:
(2^{0}+2^{b'})^{n} \equiv \; 2^{0}+2^{b'} \; (mod\; n}

(Silverman already said that the function f(x) must be shown.)
That the 'minus 1' must not influence the congruation seems for me the hard part. But if this is resolved would it then be correct ?
No. The RHS is (1 + 2^(b')) mod n.

This is equivalent to (1 + 2^b')^(phi(n) + 1) by Lagrange's Theorem.
(this is what the LHS should be)

phi(n) + 1 = n iff n is prime.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-14, 22:17   #42
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
No. The RHS is (1 + 2^(b')) mod n.

This is equivalent to (1 + 2^b')^(phi(n) + 1) by Lagrange's Theorem.
(this is what the LHS should be)

phi(n) + 1 = n iff n is prime.
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 !!!!!


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
unless I'm misunderstanding it's taken to be prime.
science_man_88 is offline   Reply With Quote
Old 2011-03-14, 23:43   #43
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
unless I'm misunderstanding it's taken to be prime.

->When p is composite then 2^{p}-1 can never be prime.

Therefore p must be prime so that 2^{p}-1 could be prime.

Its because of the factorization.

When for example p = a*b, then

<br />
<br />
2^{(a*b)}-1 = (2^{a}-1) * (2^{(0*a)}+2^{(1*a)}+2^{(2*a)}+2^{(3*a)}+ \; ......\; + 2^{((b-1) * a)})
sascha77 is offline   Reply With Quote
Old 2011-03-14, 23:51   #44
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by sascha77 View Post
->When p is composite then 2^{p}-1 can never be prime.

Therefore p must be prime so that 2^{p}-1 could be prime.

Its because of the factorization.

When for example p = a*b, then

<br />
<br />
2^{(a*b)}-1 = (2^{a}-1) * (2^{(0*a)}+2^{(1*a)}+2^{(2*a)}+2^{(3*a)}+ \; ......\; + 2^{((b-1) * a)})
not quite what I meant he was arguing that it must be prime but my understanding had n prime already so it doesn't need clarification if true.
science_man_88 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 04:39.

Wed Jan 27 04:39:42 UTC 2021 up 55 days, 51 mins, 0 users, load averages: 2.11, 2.51, 2.86

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