View Single Post
Old 2011-03-04, 19:07   #17
sascha77's Avatar
Jan 2010

2·13 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.


-> for every x you have: (2^{x})^{p}\equiv1\;mod(2^{p}-1)

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


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 )


Last fiddled with by sascha77 on 2011-03-04 at 19:50
sascha77 is offline   Reply With Quote