Question about a mersenne-number property
 

I discovered a nice property about mersenne numbers.


[TEX](2^a+2^b)^{n}\equiv 2^a + 2^b\; (mod\; n)[/TEX]

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

1.) [TEX]a = b[/TEX]

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


- For the other combinations of the variable [TEX]a[/TEX] and [TEX]b[/TEX] 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. :grin:

My question is:
Can this conjecture be true or is this just an example for the 'laws of small numbers' ?

[QUOTE=sascha77;254247]I discovered a nice property about mersenne numbers.


[TEX](2^a+2^b)^{n}\equiv 2^a + 2^b\; (mod\; n)[/TEX]

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

1.) [TEX]a = b[/TEX]

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


- For the other combinations of the variable [TEX]a[/TEX] and [TEX]b[/TEX] 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. :grin:

My question is:
Can this conjecture be true or is this just an example for the 'laws of small numbers' ?[/QUOTE]

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.

[QUOTE=sascha77;254247]I discovered a nice property about mersenne numbers.


[TEX](2^a+2^b)^{n}\equiv 2^a + 2^b\; (mod\; n)[/TEX]

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

1.) [TEX]a = b[/TEX]

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


- For the other combinations of the variable [TEX]a[/TEX] and [TEX]b[/TEX] 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. :grin:

My question is:
Can this conjecture be true or is this just an example for the 'laws of small numbers' ?[/QUOTE]

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: [b]Binomial Theorem[/b].

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

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) [COLOR="Red"]except[/COLOR] when z == 1.

Inb4miscmaththreads.

[QUOTE=science_man_88;254252]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) [COLOR=Red]except[/COLOR] when z == 1.[/QUOTE]



I think you did really a mistake.:smile:

[TEX]2^x - 2^{(x-z)} = 2^x - \frac{2^x}{2^z} = \frac{2^x*(2^z-1)}{2^z}[/TEX]

[QUOTE=sascha77;254256]I think you did really a mistake.:smile:

[TEX]2^x - 2^{(x-z)} = 2^x - \frac{2^x}{2^z} = \frac{2^x*(2^z-1)}{2^z}[/TEX][/QUOTE]

[TEX]\frac{2^x*(2^z-1)}{2^z}[/TEX]

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.

[QUOTE=R.D. Silverman;254251]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: [B]Binomial Theorem[/B].

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


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 :

[TEX](X-a)^n \equiv\; (X^n -a) \;(mod \;n)[/TEX]

if [TEX]gcd(a,n) = 1[/TEX] 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:

[TEX](X-1)^5 = -1 + 5X -10X^2 + 10X^3-5X^4 + X^5[/TEX]

[TEX]-1 + 5X -10X^2 + 10X^3-5X^4 + X^5 \;mod \;5\; = \;4 + X^5[/TEX]

-> 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 [B]Mersenne[/B] [B]Prime[/B] [B]n[/B] (n=(2^p)-1, n is prime)
this is always true:

[TEX](2^a+2^b)^n \equiv 2^a+2^b\;(mod\; n)[/TEX]

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

[TEX](2^a+2^b)^n \equiv 2^a+2^b\;(mod\; n)[/TEX]

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


"Kleine Fermatsche Satz" : For all [TEX]a[/TEX] and all [TEX]n[/TEX] true:

[TEX]a^{\varphi{(n)}} \equiv 1\; (mod \;n) [/TEX]

[B]If n [/B][B]is prime then[/B] [TEX]\varphi{(n)}=n-1[/TEX]
( [TEX]\varphi{}[/TEX] is the Eulers totient function )

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

[TEX](2^a+2^b)^n \equiv 2^a+2^b\;(mod\; n)[/TEX]



...And if you have :

[TEX](x)^n \equiv x\; (mod \;n) [/TEX]

you get this:

[TEX]-> x^{(n-1)} \equiv 1 \;(mod \;n)[/TEX]

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 [TEX]x^{(n-1)} \equiv 1\; (mod \;n ) [/TEX]

is [B]NEVER POSSIBLE[/B] when [B]n[/B] is [B]NOT PRIME[/B].

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

Again:

[TEX](2^a+2^b)^n \equiv 2^a+2^b \;(mod \;n) [/TEX]

Let [TEX]n = 2^{p}-1[/TEX] and [B]n[/B] is [B]not Prime[/B].

If now [TEX]a\not=b[/TEX] [B]and[/B] [TEX]|a-b|\not\equiv \;p\;(mod\;n)[/TEX] then the

above congruation is ALWAYS false.


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

[TEX]x^{(n-1)}\equiv 1 \;(mod \;n)[/TEX]

is [B]NEVER true [/B] when n=2^p-1 is [B]not prime[/B] !

Sascha,

Bob Silverman is an [B]expert[/B]. 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.


[SIZE="1"][COLOR="Silver"]semi-random image attached.[/COLOR][/SIZE]

[QUOTE=sascha77;254261]
[TEX](2^a+2^b)^n \equiv 2^a+2^b \;(mod \;n) [/TEX]

Let [TEX]n = 2^{p}-1[/TEX] and [B]n[/B] is [B]not Prime[/B].

If now [TEX]a\not=b[/TEX] [B]and[/B] [TEX]|a-b|\not\equiv \;p\;(mod\;n)[/TEX] then the

above congruation is ALWAYS false.


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

[TEX]x^{(n-1)}\equiv 1 \;(mod \;n)[/TEX]

is [B]NEVER true [/B] when n=2^p-1 is [B]not prime[/B] ![/QUOTE]

Well, (2[SUP]11[/SUP]+2[SUP]1[/SUP])[SUP]2046[/SUP] [TEX]\equiv[/TEX] 1 (mod 2047).
a-b=10 [TEX]\not\equiv[/TEX] 11 (mod 2047)

[QUOTE=sascha77;254261]


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

[TEX]x^{(n-1)}\equiv 1 \;(mod \;n)[/TEX]

is [B]NEVER true [/B] when n=2^p-1 is [B]not prime[/B] ![/QUOTE]

You just [b]changed[/b] 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.