Question about a mersenne-number property

sascha77 · 2011-03-03, 23:02

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

science_man_88 · 2011-03-03, 23:32

Quote:

Originally Posted by sascha77

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.

R.D. Silverman · 2011-03-03, 23:45

Quote:

Originally Posted by sascha77

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.

science_man_88 · 2011-03-03, 23:52

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.

ixfd64 · 2011-03-04, 00:02

Inb4miscmaththreads.

sascha77 · 2011-03-04, 01:03

Quote:

Originally Posted by science_man_88

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

science_man_88 · 2011-03-04, 01:24

Quote:

Originally Posted by sascha77

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.

sascha77 · 2011-03-04, 02:44

Quote:

Originally Posted by R.D. Silverman

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 !

Uncwilly · 2011-03-04, 03:40

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.

mart_r · 2011-03-04, 16:01

Quote:

Originally Posted by sascha77

$(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, (2¹¹+2¹)²⁰⁴⁶ $\equiv$ 1 (mod 2047).
a-b=10 $\not\equiv$ 11 (mod 2047)

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

Quote:

Originally Posted by sascha77

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.

2011-03-03, 23:02	#1
sascha77 Jan 2010 germany 1A₁₆ Posts	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' ?

2011-03-03, 23:52	#4
science_man_88 "Forget I exist" Jul 2009 Dartmouth NS 2·3·23·61 Posts	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*

2011-03-04, 03:40	#9
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2²·7·389 Posts	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

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, 00:02	#5
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 5×499 Posts	Inb4miscmaththreads.