На экзамене будет вопрос "Минимально возможные коэффициенты линейного представления НОД и оценка коэффициентов, получаемых из алгоритма Евклида". В связи с ним два моих вопроса:

  1. Я представляю себе, как из алгоритма Евклида получить эти коэффициенты; но как получить оценку их абс. величины?
  2. Минимально возможные (по абс. величине) коэффициенты получаются при помощи континуантов?

задан 13 Янв '16 19:14

1

@Анатолий Сул...: здесь надо точнее ставить сам вопрос, потому что величин у нас две, и тогда не ясен принцип сравнения. Скажем, одна пара может иметь вид (13, -22), а другая (-31, 7). Какая из них лучше другой?

Если же иметь в виду что-то вроде канонического способа нахождения пары натуральных чисел для решения уравнения $%ax-by=\pm d$%, то это делается при помощи цепных дробей. Что касается оценки, то x не больше модуля b, а y не больше модуля a. Это обосновывается достаточно просто.

(14 Янв '16 2:42) falcao

Спасибо, вопрос исчерпан.

(14 Янв '16 18:43) Анатолий Сул...
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×4,517
×195
×58

задан
13 Янв '16 19:14

показан
780 раз

обновлен
14 Янв '16 18:43

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

по почте:

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

по RSS:

Ответы

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

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