Да се докаже, че ако (m,n)=1, то

[studentT]

Здравейте

Решавам една задача в момента, но имам нужда от помощ.
Условие:
Да се докаче, че ако (m,n) = 1, то [tex](2^m - 1, 2^n - 1)=1[/tex]

Решение:
Приемам, че d дели 2^m -1 и 2^n - 1. Тогава d - нечетно.
d трябва да дели и сборът и разликата на тези две.
т.е. d / (2^m - 2^n) и d / (2^m + 2^n - 2) но съм до тук. Как се дорешава?

Благодаря предварително

[red_bull4o]

Според мен от това,че
[tex]( a^{n }-1 , a^{m }-1 ) = a^{(n,m)}-1
=> 2^{(n,m)}-1=2^{1}-1=1.[/tex]
мисля, че това е цялото решение колега

[Станислав]

За да докажеш, че [tex]\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1[/tex] можеш да използваш и циклотомични полиноми и по-точно формулата [tex]x^n-1=\prod_{d|n} \Phi_d(x)[/tex].

[inveidar]

За да докажеш, че [tex]\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1[/tex] можеш да използваш и циклотомични полиноми и по-точно формулата [tex]x^n-1=\prod_{d|n} \Phi_d(x)[/tex].

Уау!!! Станиславе, ти ще побъркаш момчето с тази циклотомия!!!
Ще пусна едно нормално решение, но по-късно!

[Станислав]

20 дена по-късно не пусна твоето решение... Не че има особен смисъл, но все пак като се каже нещо е хубаво да се спазва

[inveidar]

Добре, бе! Забравил бях.

Нека [tex]a\ne1[/tex]естествено число. Ще покажем, че [tex](a^{m}-1,a^{n}-1)=a^{d}-1[/tex], където [tex]d=(m,n)[/tex]. Б.О.О ще допуснем, че [tex]n\ge m[/tex]. При [tex]m=0[/tex] твърдението е очевидно. Нека [tex]m>0[/tex]. Тогава [tex]n=m.q+r,[/tex] където [tex]0\le r<m[/tex]. Следователно [tex]a^{n}-1=a^{m.q}.a^{r}-1=a^{m.q}.a^{r}-a^{r}+a^{r}-1=a^{r}.(a^{m.q}-1)+(a^{r}-1)=a^{r}.((a^{m})^{q}-1)+(a^{r}-1)=[/tex][tex]A(a^{m}-1)+(a^{r}-1)[/tex], където А е цяло число. От тези равенства следва че
[tex](a^{n}-1,a^{m}-1)=(a^{m}-1,a^{r}-1)[/tex]. Сега, като си спомним алгоритъма на Евклид за намиране на [tex](m,n)[/tex] лесно достигаме до [tex](a^{m}-1,a^{n}-1)=a^{d}-1[/tex]. Твърдението от задачата е частен случай на това по-обще твърдение.