НОД(x^m-1,x^n-1) равен x^d-1, где d=НОД(m,n).

задан 31 Окт '16 18:45

Примените алгоритм Евклида к числам из условия. Пусть для определённости m>=n. Тогда x^m-1=x^{m-n}(x^n-1)+(x^{m-n}-1). Это значит, что НОД будет тот же, что и для чисел x^n-1, x^{m-n}-1. То есть с показателями степеней происходит то же, что в обычном алгоритме Евклида, который и даёт число d.

(31 Окт '16 19:09) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×48
×18
×12

задан
31 Окт '16 18:45

показан
214 раз

обновлен
31 Окт '16 19:09

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru