Есть задание, выразаить НОД через исходные числа. НОД(3069 1881) = 99. Ответ: 8a - 13b. Какой алгоритм выражения через исходные числа? В гугле чет не нашел вообще.

Есть этот вопрос, но ответ сложный и не очень понятный.

задан 8 Янв '19 15:24

изменен 8 Янв '19 15:28

10|600 символов нужно символов осталось
0

Для многочленов ситуация похожая, но она более сложная. Здесь лучше исходить из алгоритма Евклида, в ходе которого было получено значение НОД, равное 99. Теперь можно взять данные алгоритма, и получить требуемое либо "сверху вниз", либо "снизу вверх". Я остановлюсь на первом варианте.

У нас a=3069, b=1881. После первого шага деления с остатком мы имеем

a=b+1188 (неполное частное здесь равно 1)

Заметим, что это равенство позволяет нам выразить 1188 через исходные числа как 1188=a-b.

Следующий шаг: b делим на 1188 с остатком:

b=1188+693

Здесь 693=b-1188=b-(a-b)=2b-a.

Теперь 1188 делим на 693. Неполное частное по-прежнему равно 1.

1188=693+495, и 495=(a-b)-(2b-a)=2a-3b

Дальше аналогично (только надо иметь в виду, что в общем случае неполные частные могут принимать любые значения, что ничему не мешает.

693=495+198, где 198=(2b-a)-(2a-3b)=5b-3a

495=198*2+99, откуда 99=(2a-3b)-2(5b-3a)=8a-13b.

Последнее действие алгоритма Евклида проверяет то, что 198 нацело делится на 99, поэтому НОД равен 99. Но здесь это учитывать было бы лишним.

ссылка

отвечен 8 Янв '19 15:49

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,697
×58

задан
8 Янв '19 15:24

показан
599 раз

обновлен
8 Янв '19 15:49

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

по почте:

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

по RSS:

Ответы

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

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