View Single Post
 2011-03-04, 19:07 #17 sascha77     Jan 2010 germany 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. $2^p\equiv1\;(mod\;2^{p}-1)$ -> for every $x$ you have: $(2^{x})^{p}\equiv1\;mod(2^{p}-1)$ Because: $(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)$ --> $ (2^{x})^{n}\equiv2^{x} \;(mod\; n)$ Therefore: 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