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

 2011-03-03, 23:02 #1 sascha77     Jan 2010 germany 2×13 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:32   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

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.

Last fiddled with by science_man_88 on 2011-03-03 at 23:41

2011-03-03, 23:45   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

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.

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

Jan 2010
germany

328 Posts

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

2011-03-04, 01:24   #7
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

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.

Last fiddled with by science_man_88 on 2011-03-04 at 01:25

2011-03-04, 02:44   #8
sascha77

Jan 2010
germany

2×13 Posts

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 !

 2011-03-04, 03:40 #9 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 5×2,179 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
2011-03-04, 16:01   #10
mart_r

Dec 2008
you know...around...

15268 Posts

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

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

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

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.

 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 22:45.

Mon Feb 6 22:45:43 UTC 2023 up 172 days, 20:14, 1 user, load averages: 0.94, 1.07, 1.07