Взаимно прости числа

[ptj]

Докажете, че [tex]2^m-1[/tex] и [tex]2^n-1[/tex] са взаимно прости, тогава и само тогава когато естесвените [tex]m[/tex] и [tex]n[/tex] са взаимно прости помежду си.

[pal702004]

[tex]\gcd(m,n)=d,\;m=ad,\;n=bd[/tex]

[tex]2^{ad}-1=\frac{2^{ad}-1}{2^d-1}\cdot (2^d-1)[/tex]

Първата дроб е сума на геометрична прогресия и е естествено число. Аналогично за [tex]n[/tex], или имат общ делител [tex]2^d-1[/tex]

При [tex]d=1[/tex]

[tex]\gcd(2^m-1,2^n-1)=\gcd(2^n[2^{m-n}-1],2^n-1)=\gcd(2^{m-n}-1,2^n-1)[/tex]

Ако [tex]m,n[/tex] са взаимнопрости по алгоритъма на Евклид се спускаме до [tex]\gcd(2^r-1,2^1-1)=1[/tex]