mersenneforum.org > Math Question about a mersenne-number property
 Register FAQ Search Today's Posts Mark Forums Read

2011-03-09, 14:26   #34
sascha77

Jan 2010
germany

2×13 Posts

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.

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

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

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.

2011-03-09, 14:37   #36
sascha77

Jan 2010
germany

1A16 Posts

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

2011-03-09, 15:32   #37
CRGreathouse

Aug 2006

5,987 Posts

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.

2011-03-09, 18:55   #38
sascha77

Jan 2010
germany

2×13 Posts

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.

2011-03-14, 11:41   #39
maxal

Feb 2005

1000001002 Posts

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

2011-03-14, 18:36   #40
sascha77

Jan 2010
germany

2·13 Posts

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 ?

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

"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts

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.

2011-03-14, 22:17   #42
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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.

2011-03-14, 23:43   #43
sascha77

Jan 2010
germany

2·13 Posts

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

2011-03-14, 23:51   #44
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 Thiele Math 18 2010-05-23 05:35 kurtulmehtap Math 12 2010-05-03 14:02 arithmeticae Lounge 5 2008-10-27 06:15 T.Rex Math 12 2005-09-12 07:56

All times are UTC. The time now is 22:12.

Mon Feb 6 22:12:08 UTC 2023 up 172 days, 19:40, 1 user, load averages: 0.98, 1.18, 1.23