Задать вопрос Регистрация
Помочь другим

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

Ответы 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 

  • Добавить свой ответ

Еще вопросы

Топ пользователей

Войти через Google

 или

Забыли пароль?

У меня нет аккаунта, я хочу Зарегистрироваться

How much to ban the user?
1 hour 1 day 100 years