منتديات الرياضيات العربية - عرض مشاركة واحدة

13-02-2009, 12:43 AM

برهنت نظرية:
$GCD(2^n - 1,2^m - 1) = 1 <=> GCD(n,m)=1$
برهان الاتجاه الاول
$GCD(2^n - 1,2^m - 1) = 1 =>GCD(n,m)=1$

نفرض ان $GCD(n,m)=k$
اذا
$n=k^s$
و $n=k^p$
$2^m -1=2^ks -1$
$2^n -1=2^kp -1$
$x=2^k$ نتذكر القانون $a^x-1=(a-1)(a^{x-1} +...+x+1)$ لكل a اكبر من 0
$x^s-1=(x-1)(x^{s-1}+...+x+1)$
$x^p-1=(x-1)(x^{p-1}+...+x+1)$
(x-1) عامل مشترك وهذا يناقض الافتراض $GCD(2^n - 1,2^m - 1) = 1$
لذا يجب ان يكون $x-1=1$
k=1
$GCD(n,m)=1$

الاتجاه الثاني
نفرض $GCD(n,m)=1$ ونبرهن $GCD(2^n-1,2^m-1)=1$

نفرض ان r هو قاسم مشترك ل $2^n-1$ , $2^m-1$
$2^m\equiv2^n\equiv1\bmod r$
علينا ان نبرهن ان r=1
حسب الغورثم اقليدس وبالعلم ان $GCD(n,m)=1$
$am+bn=1$
اذا
$2^1=2^{am+bn}=2^{am} 2^{bn}$
$\equiv 1^a 1^b\bmod r \equiv 1$

$2\equiv 1 \bmod r$
r=1

اتمنى ان برهاني قد اعجبكم