Алгоритм Евклида
Ошибка.
Попробуйте повторить позже
При каком условии на 
и 
уравнение
имеет решение в целых числах?
Совершенно очевидно, что если 
, то левая часть делится на 
, значит, и правая часть должна делиться на 
, но 1
точно на 
не делится.
Если же 
, то применим алгоритм Евклида к числам 
и 
. При этом на очередном шаге будем выражать
новые числа линейным образом через 
и 
. Например, после первого шага мы ищем 
, если 
,
потом снова вычитаем из большего меньшее, и так далее. В итоге мы придем к тому, что одно из чисел в скобках станет
равно 1, и при этом будет выражено линейно через 
и 
. Значит, мы смогли выразить 1 в виде 
, что и
требовалось.
Замечание. А что произойдет, если справа написать не 1, а 
? Во-первых, на 
можно сократить. Если после этого 
не
делится на 
, то решений, очевидно, нет. Если делится, то решения есть по тому же алгоритму Евклида. В конце надо лишь
домножить на 
. Более интересен вопрос найти все решения подобного ЛДУ, но этот вопрос мы оставим для самостоятельных
размышлений.
при взаимно простых 
и 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
