برهان نظرية في ال numbers theory

[hussam]

برهنت نظرية:
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


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