Question about a mersenne-number property - Page 2

R.D. Silverman · 2011-03-04, 16:16

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.

sascha77 · 2011-03-04, 16:29

Quote:

Originally Posted by mart_r

Well, (2¹¹+2¹)²⁰⁴⁶ $\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)$

sascha77 · 2011-03-04, 16:39

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

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

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.

mart_r · 2011-03-04, 18:52

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

sascha77 · 2011-03-04, 19:07

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)$ --> $<br /> (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 )$

**************************************************

mart_r · 2011-03-04, 19:42

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<a, p<71 yet.

I would guess there are likely to be counterexamples (e.g. Carmichael numbers with Hamming weight 2), but they're probably hard to find.

sascha77 · 2011-03-04, 20:00

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<a, p<71 yet.

I would guess there are likely to be counterexamples (e.g. Carmichael numbers with Hamming weight 2), but they're probably hard to find.

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.

mart_r · 2011-03-04, 20:28

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.

R.D. Silverman · 2011-03-04, 20:53

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.

Batalov · 2011-03-07, 23:53

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 ?

2011-03-04, 19:07	#17
sascha77 Jan 2010 germany 11010₂ 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 = (2pk+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)$ --> $<br /> (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+pk)$ with $k\in N$ . -> $(2^{a} + 2^{b})^{n}\equiv (2^{a} + 2^{(a+pk)})^{n}\equiv ({2^{a}}+{2^{a}}{2^{(pk)}})^{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... 3²·5·19 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^2x)%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<a, p<71 yet. I would guess there are likely to be counterexamples (e.g. Carmichael numbers with Hamming weight 2), but they're probably hard to find. Last fiddled with by mart_r on 2011-03-04 at 19:47*

2011-03-07, 23:53	#22
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10,061 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^2x)%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
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

2011-03-04, 20:28	#20
mart_r Dec 2008 you know...around... 3²·5·19 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.