mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-03-03, 23:02   #1
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2·13 Posts
Default Question about a mersenne-number property

I discovered a nice property about mersenne numbers.


(2^a+2^b)^{n}\equiv 2^a + 2^b\; (mod\; n)

When  n=2^{p}-1 is not prime then this is true only for the two trivial cases:

1.) a = b

2.) If there exist an x for :  2^a+2^b \equiv 2^x the
above congruence is also true.
This is the case when choosing a and b , so that
|b-a| \equiv p\;(mod\;n) .


- For the other combinations of the variable a and b the above congruence is
NEVER true.


I do not really know if I am right with this.
Up til now i haven't found an counterexample.

My question is:
Can this conjecture be true or is this just an example for the 'laws of small numbers' ?
sascha77 is offline   Reply With Quote
Old 2011-03-03, 23:32   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by sascha77 View Post
I discovered a nice property about mersenne numbers.


(2^a+2^b)^{n}\equiv 2^a + 2^b\; (mod\; n)

When  n=2^{p}-1 is not prime then this is true only for the two trivial cases:

1.) a = b

2.) If there exist an x for :  2^a+2^b \equiv 2^x the
above congruence is also true.
This is the case when choosing a and b , so that
|b-a| \equiv p\;(mod\;n) .


- For the other combinations of the variable a and b the above congruence is
NEVER true.


I do not really know if I am right with this.
Up til now i haven't found an counterexample.

My question is:
Can this conjecture be true or is this just an example for the 'laws of small numbers' ?
well if I did the math correct the only other time it could be true is a= b-1 so can you come up with the answer from that ?, okay never mind messed up my math.

Last fiddled with by science_man_88 on 2011-03-03 at 23:41
science_man_88 is offline   Reply With Quote
Old 2011-03-03, 23:45   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by sascha77 View Post
I discovered a nice property about mersenne numbers.


(2^a+2^b)^{n}\equiv 2^a + 2^b\; (mod\; n)

When  n=2^{p}-1 is not prime then this is true only for the two trivial cases:

1.) a = b

2.) If there exist an x for :  2^a+2^b \equiv 2^x the
above congruence is also true.
This is the case when choosing a and b , so that
|b-a| \equiv p\;(mod\;n) .


- For the other combinations of the variable a and b the above congruence is
NEVER true.


I do not really know if I am right with this.
Up til now i haven't found an counterexample.

My question is:
Can this conjecture be true or is this just an example for the 'laws of small numbers' ?
This piece of stupidity is another example of what I say when I tell people
that they should not go near number theory until they have mastered
high school mathematics.

Hint: Binomial Theorem.

Consider (x + y)^n mod n for arbitrary x,y \in N and n prime.
R.D. Silverman is offline   Reply With Quote
Old 2011-03-03, 23:52   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

well 2^x - 2^(x-z) = (2^z-1)*2^(x-z) since I redid the math. From the fact that (2^y)/(2^a) = 2^(y-a) it's impossible to add up to a multiplier (2^z-1) with only one other power of 2 other than 2^(x-z) except when z == 1.

Last fiddled with by science_man_88 on 2011-03-04 at 00:52
science_man_88 is offline   Reply With Quote
Old 2011-03-04, 00:02   #5
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

22·3·197 Posts
Default

Inb4miscmaththreads.
ixfd64 is online now   Reply With Quote
Old 2011-03-04, 01:03   #6
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

2×13 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
well 2^x - 2^(x-z) = (2^z-1)*2^(x-z) since I redid the math. From the fact that (2^y)/(2^a) = 2^(y-a) it's impossible to add up to a multiplier (2^z-1) with only one other power of 2 other than 2^(x-z) except when z == 1.


I think you did really a mistake.

2^x - 2^{(x-z)} = 2^x - \frac{2^x}{2^z} = \frac{2^x*(2^z-1)}{2^z}
sascha77 is offline   Reply With Quote
Old 2011-03-04, 01:24   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by sascha77 View Post
I think you did really a mistake.

2^x - 2^{(x-z)} = 2^x - \frac{2^x}{2^z} = \frac{2^x*(2^z-1)}{2^z}
\frac{2^x*(2^z-1)}{2^z}

according to your math you can reconvert it to 2^(x-z)*(2^z-1) which means unless you say the last one is a error my math holds up to yours.

Last fiddled with by science_man_88 on 2011-03-04 at 01:25
science_man_88 is offline   Reply With Quote
Old 2011-03-04, 02:44   #8
sascha77
 
sascha77's Avatar
 
Jan 2010
germany

328 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This piece of stupidity is another example of what I say when I tell people
that they should not go near number theory until they have mastered
high school mathematics.

Hint: Binomial Theorem.

Consider (x + y)^n mod n for arbitrary x,y \in N and n prime.

I think you did not read carefully what i wrote or
my english grammar was too bad.

Let me show you what I did and what i meant:


I played with the Lemma :

(X-a)^n \equiv\; (X^n -a) \;(mod \;n)

if gcd(a,n) = 1 and the congruent is correct then n is prime.
And shure I know that I dont may put a number to X.
X is a free variable.

For example:

(X-1)^5 = -1 + 5X -10X^2 + 10X^3-5X^4 + X^5

-1 + 5X -10X^2 + 10X^3-5X^4 + X^5 \;mod \;5\; = \;4 + X^5

-> 5 is prime


But what I did was to play a little around with this Lemma.
So I inserted the number 2 to the variables X and a.

I know that for every Mersenne Prime n (n=(2^p)-1, n is prime)
this is always true:

(2^a+2^b)^n \equiv 2^a+2^b\;(mod\; n)

(This is because the "Kleine Fermatsche Satz".)

(2^a+2^b)^n \equiv 2^a+2^b\;(mod\; n)

\leftarrow \rightarrow\;\;(2^a+2^b)^{n-1} \equiv 1\;(mod\; n)


"Kleine Fermatsche Satz" : For all a and all n true:

a^{\varphi{(n)}} \equiv 1\; (mod \;n)

If n is prime then \varphi{(n)}=n-1
( \varphi{} is the Eulers totient function )

Therefore if  n=2^p-1 is prime when for all a and all b the following congruation is always correct:

(2^a+2^b)^n \equiv 2^a+2^b\;(mod\; n)



...And if you have :

(x)^n \equiv x\; (mod \;n)

you get this:

-> x^{(n-1)} \equiv 1 \;(mod \;n)

But if n is not prime, when it can be that for some x this is also true.

So what I did is that I looked for numbers x where the congruation x^{(n-1)} \equiv 1\; (mod \;n )

is NEVER POSSIBLE when n is NOT PRIME.

So I found a pattern. And this was my conjecture.

Again:

(2^a+2^b)^n \equiv 2^a+2^b \;(mod \;n)

Let n = 2^{p}-1 and n is not Prime.

If now a\not=b and |a-b|\not\equiv \;p\;(mod\;n) then the

above congruation is ALWAYS false.


This means that for these x = (2^a+2^b) this :

x^{(n-1)}\equiv 1 \;(mod \;n)

is NEVER true when n=2^p-1 is not prime !
sascha77 is offline   Reply With Quote
Old 2011-03-04, 03:40   #9
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2·33·173 Posts
Default

Sascha,

Bob Silverman is an expert. He likely did not mis-read what you wrote. If he suggests that you look into some area of education, do it. I think that his idea of High School math is through Math Analysis and Calculus I & II. He is often blunt, don't be scared by him though.

I have not looked into your suggestion. My math skills have severely atrophied since I left school.


semi-random image attached.
Attached Thumbnails
Click image for larger version

Name:	TheGate.png
Views:	142
Size:	236.0 KB
ID:	6310  
Uncwilly is offline   Reply With Quote
Old 2011-03-04, 16:01   #10
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

2×313 Posts
Default

Quote:
Originally Posted by sascha77 View Post
(2^a+2^b)^n \equiv 2^a+2^b \;(mod \;n)

Let n = 2^{p}-1 and n is not Prime.

If now a\not=b and |a-b|\not\equiv \;p\;(mod\;n) then the

above congruation is ALWAYS false.


This means that for these x = (2^a+2^b) this :

x^{(n-1)}\equiv 1 \;(mod \;n)

is NEVER true when n=2^p-1 is not prime !
Well, (211+21)2046 \equiv 1 (mod 2047).
a-b=10 \not\equiv 11 (mod 2047)
mart_r is offline   Reply With Quote
Old 2011-03-04, 16:08   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by sascha77 View Post


This means that for these x = (2^a+2^b) this :

x^{(n-1)}\equiv 1 \;(mod \;n)

is NEVER true when n=2^p-1 is not prime !
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.
R.D. Silverman is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 17:14.

Thu Feb 25 17:14:32 UTC 2021 up 84 days, 13:25, 0 users, load averages: 1.81, 1.89, 1.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.