Question about a mersenne-number property - Page 4

sascha77 · 2011-03-09, 14:26

Quote:

Originally Posted by R.D. Silverman

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.

R.D. Silverman · 2011-03-09, 14:37

Quote:

Originally Posted by sascha77

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)\; $
$\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.

sascha77 · 2011-03-09, 14:37

Quote:

Originally Posted by ATH

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.

CRGreathouse · 2011-03-09, 15:32

Quote:

Originally Posted by ATH

His conjectures includes 1 as a non-witness for all numbers.

Trivially, yes.

Quote:

Originally Posted by ATH

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

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.

sascha77 · 2011-03-09, 18:55

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.

maxal · 2011-03-14, 11:41

Quote:

Originally Posted by sascha77

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

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

sascha77 · 2011-03-14, 18:36

Quote:

Originally Posted by maxal

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 ?

R.D. Silverman · 2011-03-14, 22:10

Quote:

Originally Posted by sascha77

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.

science_man_88 · 2011-03-14, 22:17

Quote:

Originally Posted by R.D. Silverman

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

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.

sascha77 · 2011-03-14, 23:43

Quote:

Originally Posted by science_man_88

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

$ 2^{(a*b)}-1 = (2^{a}-1) * (2^{(0*a)}+2^{(1*a)}+2^{(2*a)}+2^{(3*a)}+ \; ......\; + 2^{((b-1) * a)})$

science_man_88 · 2011-03-14, 23:51

Quote:

Originally Posted by sascha77

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

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

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