Question

Докажите, что НОД ((2^n) -1, (2^m) -1) = (2^(НОД(m,n))) -1 для любых натуральных m и n

Answer 1

Можно применить Алгоритм Евклида: 
  $m\ \textgreater \ n\\ (2^{m}-1, 2^{n}-1) = (2^{m}-1-(2^{n}-1) , 2^{n}-1) = (2^{m}-2^{n}, 2^{n}-1) = \\ (2^{n}(2^{m-n}-1)+2^{n}-1, 2^{n}-1) = (2^{m-n}-1 , 2^{n}-1)=\\ = ( 2^{n}(2^{m-2n}-1)+2^{n}-1, 2^{n}-1) = (2^{m-2n}-1 , 2^{n}-1) =...$
итд, то есть если внимательно посмотреть на степени, то в них происходит тот же Алгоритм Евклида нахождения НОД что и чисел без основания, получаем что в конце получим НОД чисел $(m,n)$ откуда и $(2^{m}-1,2^{n}-1) = 2^{(m,n)}-1$