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

2011-03-04, 16:16   #12
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2·3·29·43 Posts

Quote:
 Originally Posted by R.D. Silverman You just changed your original statement. Your original statement was that x^n = x is not true when n = 2^p-1 is composite. Here x = 2^a + 2^b for a!= b This is different from x^{n-1} = 1 is not true when n = 2^p-1 is composite.
Note that 34 = 2^1 + 2^5 and 34^255 = 34 mod 255. Enough said?

Not enough? Note that 65 = 2^0 + 2^6 and 65^510 = 1 mod 511.

Still not enough? 72 = 2^3 + 2^6 and 72^510 = 1 mod 511.

I am sure that one could find additional counter-examples.

There was no reason to believe that an integer with Hamming weight 2
could not be a false witness to Mersenne numbers.

2011-03-04, 16:29   #13
sascha77

Jan 2010
germany

2·13 Posts

Quote:
 Originally Posted by mart_r Well, (211+21)2046 $\equiv$ 1 (mod 2047). a-b=10 $\not\equiv$ 11 (mod 2047)
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)$

2011-03-04, 16:39   #14
sascha77

Jan 2010
germany

2×13 Posts

Quote:
 Originally Posted by R.D. Silverman Note that 34 = 2^1 + 2^5 and 34^255 = 34 mod 255. Enough said? Not enough? Note that 65 = 2^0 + 2^6 and 65^510 = 1 mod 511. Still not enough? 72 = 2^3 + 2^6 and 72^510 = 1 mod 511. I am sure that one could find additional counter-examples. There was no reason to believe that an integer with Hamming weight 2 could not be a false witness to Mersenne numbers.

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

Last fiddled with by sascha77 on 2011-03-04 at 16:44

2011-03-04, 18:26   #15
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2·3·29·43 Posts

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 !!!!!
That is one definition. You will also find the definition
spread throughout the literature that a Mersenne Number is of the
form 2^n-1 for any n .

Quote:
 Your example with mod 511 -> $511 -> 2^{9}-1$
It is likely that I can find other counter-examples for the case n = prime
if I look hard enough.

It isn't worth my time.

2011-03-04, 18:52   #16
mart_r

Dec 2008
you know...around...

809 Posts

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)$
Oops, sorry. Messed up 1 with 21

 2011-03-04, 19:07 #17 sascha77     Jan 2010 germany 2·13 Posts I noticed that my first post in this topic was mathematically not detailled enough and I forgot to mention some assumptions. (Especially that p must always be prime) For this reason I redefine my previous post: $(2^a+2^b)^{n} \equiv 2^a+2^b\;(mod \;n)$ $n=2^{p}-1$ WITH $p$ is prime !!! $a \in N\; and\; b \in N.$ A.) let n be prime with n=2^p-1: if $n$ is prime then for every $a$ and $b$ the congruence is true. -------------------------------------------------------------------- B.) Let n be not prime with n=2^p-1 (But p is prime): B.1.) If you choose $a=b$ when the above congruence is always true. B.2.) If you choose $a$ and $b$ so that $|b-a|\equiv p\;(mod \;n)$ when the congruence is also always true. B.3) But for the other combinations of $a$ and $b$ the above congruence is always false. (A) (B.1) and (B.2) can easily be proven. But (B.3) is hard to prove. Therefore is (B.3) my conjecture. ----------------------------------------------------------------- ************************************************** Proof of A: This is trivial, because A follows directly from the "Fermatsche Satz". ************************************************** ************************************************** proof of B.1: $(2^x)^{p} \equiv 1 \;(mod\; n)$ is always true. This is because 2 has always the order $p$ in $Z/Z_{(2^{p}-1)}$ with $p$ prime. $2^p\equiv1\;(mod\;2^{p}-1)$ -> for every $x$ you have: $(2^{x})^{p}\equiv1\;mod(2^{p}-1)$ Because: $(2^{x})^{p}=(2^{p})^{x}\equiv1^{x}\equiv1\;(mod \;2^{p}-1)$ Now we look at the variable $n$: $n = 2^{p}-1 = (2*p*k+1)$ (This is because of the factorisation of the form 2^{p}-1) -> $(n-1) \equiv 0 \; (mod\; p)$ for every $x$ you have now: $(2^{x})^{n-1}\equiv1\;(mod\;n)$ --> $ (2^{x})^{n}\equiv2^{x} \;(mod\; n)$ Therefore: when you choose $a$ and $b$ so that $a=b$ then you have: ${(2^{a}+2^{a})}^{n} = {(2^{(a+1)})}^{n} \equiv 2^{a+1}\equiv 2^{a}+2^{b}\;mod\; (n)$ ************************************************** ************************************************** proof of B.2: If you choose $a$ and $b$ so that $|b-a|\equiv p\;(mod\;n)$ then $b$ is $b=(a+p*k)$ with $k\in N$. -> $(2^{a} + 2^{b})^{n}\equiv (2^{a} + 2^{(a+p*k)})^{n}\equiv ({2^{a}}+{2^{a}}*{2^{(p*k)}})^{n}\equiv (2^{a}*2^{a}*1)^{n}\equiv(2^{a+1})^{n}\equiv 2^{(a+1)} \;(mod\; n )$ ************************************************** Last fiddled with by sascha77 on 2011-03-04 at 19:50
 2011-03-04, 19:42 #18 mart_r     Dec 2008 you know...around... 32916 Posts Deployed some Pari code: forprime(p=67,83,print(p);n=2^p-1;for(a=2,999,for(b=0,a-1,x=2^a+2^b;c=x;for(i=1,p-2,c=(c^2*x)%n);c=(c^2)%n;if(c==1&&(a-b)%p<>0,print("counterexample found: a="a", b="b))))) [The forprime-range is to be set manually after every Mp=prime, e.g. next it would be forprime(p=97,103,...] No counterexample for a<1000, b
2011-03-04, 20:00   #19
sascha77

Jan 2010
germany

328 Posts

Quote:
 Originally Posted by mart_r Deployed some Pari code: forprime(p=67,83,print(p);n=2^p-1;for(a=2,999,for(b=0,a-1,x=2^a+2^b;c=x;for(i=1,p-2,c=(c^2*x)%n);c=(c^2)%n;if(c==1&&(a-b)%p<>0,print("counterexample found: a="a", b="b))))) [The forprime-range is to be set manually after every Mp=prime, e.g. next it would be forprime(p=97,103,...] No counterexample for a<1000, b

Thanks !!!
Yes it could be that there exist a counterexample.
But nobody knows this until it is found. ;-)
A hint: You only need to test a and b to the size of p.
this means: test a for a<=p and b for b<=p
Because of the modulo-operation these values of 2^a repeat after p-steps.

 2011-03-04, 20:28 #20 mart_r     Dec 2008 you know...around... 14518 Posts Fair enough. So, no counterexamples for p<=353. Stopping here. Someone with a faster PC, i.e. with more than one core, could check further.
2011-03-04, 20:53   #21
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2×3×29×43 Posts

Quote:
 Originally Posted by sascha77 Thanks !!! Yes it could be that there exist a counterexample. But nobody knows this until it is found. ;-) A hint: You only need to test a and b to the size of p. this means: test a for a<=p and b for b<=p Because of the modulo-operation these values of 2^a repeat after p-steps.
You are looking at the intersection of two sparse sets (false witnesses
to 2^p-1 and integers with Hamming weight 2) and hoping that the
intersection isn't empty.

There are no analytic tools available to approach the problem because
[AFAIK] there is almost nothing known about how false witnesses
are distributed mod P. It is easy to get a sharp counting function for
weight-2 integers up to B , but their distribution is clearly not uniform.

Heuristics based on probabilistic methods are likely to fail, because
the sets involved are not uniformly distributed.

Even if the result is true, it has almost no applicability anyway. LL will
be faster.

 2011-03-07, 23:53 #22 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 26D616 Posts Unsurprisingly, there were no counterexamples up to p<1450. A modified one-liner 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;c=x;for(i=3,p,c=(c^2*x)%n);if((c^2)%n==1,print("found: a="a", b="b)))))) can run without need to skip prime Mp's and can run forever lazily... ____ A bit faster: 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)))))) ...Is there a better mod exponent in Pari? Mod(2^a+2^b,n)^n ? Last fiddled with by Batalov on 2011-03-08 at 00:09 Reason: (not a master of Pari, I am)

 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 18:52.

Wed Oct 5 18:52:37 UTC 2022 up 48 days, 16:21, 0 users, load averages: 1.21, 1.28, 1.24