20110309, 14:26  #34  
Jan 2010
germany
2×13 Posts 
Quote:
That is exactly what I meant. Sure I could have done the proof a lot shorter and easier with the multiplikation of (2^{(k)})^{n1) But the result is the same. 

20110309, 14:37  #35  
"Bob Silverman"
Nov 2003
North of Boston
16510_{8} Posts 
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^p1. 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:
Quote:
Quote:
Quote:
(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)^(n1) = 1 mod n, then (2^a + 2^(b+1))^(n1) = 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))^(n1) = 1 mod n UNLESS (2^a + 2^(b+1)) is coprime to n. There is no way to prove the latter. Indeed, if 2^p1 is prime, then (2^a + 2^(b+1)) will be coprime. But if 2^p1 is composite, then it might not be. Unless I missed something. 

20110309, 14:37  #36  
Jan 2010
germany
1A_{16} Posts 
Quote:
Thanks for the interesting PDF about 'millerrabin test'. I will read that. 

20110309, 15:32  #37  
Aug 2006
5,987 Posts 
Trivially, yes.
Quote:
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. 

20110309, 18:55  #38  
Jan 2010
germany
2×13 Posts 
Quote:
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 coprime to n. 

20110314, 11:41  #39  
Feb 2005
2^{2}·5·13 Posts 
Quote:
Assume that . Since is an odd prime and , we have that for all . On the other hand, is equivalent to , a contradiction. Hence, . However, that does not make your proof correct, since the last congruence below is unjustified: 

20110314, 18:36  #40  
Jan 2010
germany
1A_{16} Posts 
Quote:
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*x1 Operation on both sides. I did this only on the right side of this congruation: (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 ? 

20110314, 22:10  #41  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
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. 

20110314, 22:17  #42  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:
Quote:


20110314, 23:43  #43 
Jan 2010
germany
32_{8} Posts 

20110314, 23:51  #44 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
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.

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 