Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Решение неопределенных уравнений при помощи алгоритма
Евклида Определение 6.1. Неопределенным уравнением будем называть уравнение вида , где и – коэффициенты уравнения, а буквами и обозначены неизвестные величины. При этом предполагается, что – целые числа, отличные от 0. Решить неопределенное уравнение, значит найти такие целые числа, которые будучи подставленными вместо неизвестных величин и , превращают уравнение в верное числовое равенство. Частный случай. Рассмотрим частный случай неопределенного уравнения, когда правая часть уравнения равна 1: (6.1) Заметим, что по теореме 5.1, это уравнение имеет решение только в случае, когда . Пусть , – одно из решений уравнения (6.1). Тогда любая пара целых чисел и , вычисляемых по формулам (6.2), где , также является решением уравнения (6.1). Действительно, . Пара чисел, вычисленных по формулам (6.2), называется общим решением уравнения (6.1), при этом говорят, что числа , составляют частное решение данного уравнения. Докажем, что множество решений уравнения (6.1) состоит только из чисел, полученных из некоторого частного решения , при помощи формул (6.2). Пусть , – некоторое частное решение уравнения (6.1), а , – также решение этого уравнения. Тогда – верные равенства. Следовательно, . Последнее равенство означает, что b. Поскольку , имеем b (по следствию 2 к теореме о необходимом и достаточном условии взаимной простоты двух чисел), а это и означает, что , где . Значит, , где . Подставим в уравнение (6.1). Получим, что . Но . Поскольку (по определению неопределенного уравнения), . Требуемое утверждение доказано. Примеры. 1) Решим уравнение . Очевидно, что , значит уравнение имеет решение. Найдем НОД чисел 12 и 17 (который, как нам известно, равен 1) при помощи алгоритма Евклида. Для этого разделим на , получим . Таким образом, первый полученный остаток . Далее, разделим на , получим , при этом . Продолжим процесс деления: , ; , . Таким образом, последний отличный от остаток равен 1, это и есть наибольший общий делитель чисел и . Найдем линейное представление НОД: Таким образом, получим частное решение: . Тогда общее решение этого уравнения имеет вид: , где .
Общий случай. В общем случае правая часть неопределенного уравнения может быть любым целым числом: . (6.3) Пусть – наибольший общий делитель чисел и . Это значит, что d и d. Поэтому для того, чтобы уравнение (6.3) имело решение необходимо и достаточно, чтобы d. Пусть d. Разделим обе части уравнения (6.3) на . Получим уравнение, равносильное уравнению (6.3), . (6.4) По свойству НОД, установленному теоремой 3, числа и взаимно просты. Тогда составим вспомогательное уравнение . (6.5) Найдем его частное решение , – при помощи алгоритма Евклида, так же, как выше было найдено решение уравнения (6.1). Тогда, очевидно, в качестве частного решения уравнения (6.4) можно взять числа и , а общим решением уравнения (6.4) является , где . Пример. Решим уравнение . Поскольку , уравнение имеет решение. Составим вспомогательное уравнение: . При помощи алгоритма Евклида представим НОД чисел и в виде линейной комбинации этих чисел с целыми коэффициентами: . Таким образом, получим частное решение вспомогательного уравнения: и частное решение исходного уравнения: . Тогда общее решение исходного уравнения имеет вид: , где .
|
|||||
Последнее изменение этой страницы: 2021-03-09; просмотров: 240; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.118.126.248 (0.007 с.) |