Второй способ решения диофантова уравнения

1. Решить диофантово уравнение

Решение.

Пользуясь обобщенным алгоритмом Евклида, находим наибольший общий делитель чисел 3196 и 3349 и его линейное представление:

Шаг 1.

В столбец записываем делимое и его линейное представление .

В столбец то же самое для делителя:

.

Всегда для столбца , а для столбца . Значение не заполняется.

Для остальных столбцов указанные переменные последовательно вычисляются.

Шаг 2.

Вычислим переменные 3 столбца (следующего за столбцом ).

Делим с остатком 3196 на 3349: .

Частное 0 записываем в строку третьего столбца, а остаток 3196 в строку .

Вычисляем по правилу: . В нашем случае

.

По такому же правилу вычисляем и :

.

Шаг 3.

На этом шаге аналогично вычисляем переменные 4 столбца.

И так далее.

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

Например, для 5 столбца:

.

Вычисления ведутся до получения 0 - ого остатка. В данном случае это произойдет при заполнении 7 столбца. Это значит, что предыдущий остаток и есть наибольший общий делитель, в данном случае число 17. Таким образом, имеем линейное представление:

.

Запишем это равенство так:

.

Правая часть исходного уравнения делится на 17, поэтому умножая последнее равенство на 2, получим:

.

Получаем частное решение системы:

.

Из последнего столбца составленной выше таблицы получаем равенство:

, из которого следует, что для любого целого числа выполняется: . А это дает формулы для общего решения:

.

Удобно взять частное решение, для которого является наименьшим неотрицательным числом. Тогда получим:

Ответ:

Заметим, что коэффициенты последнего столбца с точностью до знаков равны частным отделение чисел и на наибольший общий делитель :

, а .

2. Вычислите 3/19 в кольце вычетов по модулю 35.

Сначала найдём 1/19 в кольце вычетов по модулю 35. Обратите внимание, что мы практически должны вычислить дробь для выражения с целыми числами!

Запишем формулировку задачи так.

x = 1/19 (mod 35)

И, наконец: найти целые числа x и y такие, что:

(причём x должен быть одним из остатков при делении на 35, то есть лежать в пределах от 0 до 34 включительно).

Подобную задачу мы уже решали – это диофантово уравнение, только достаточно получить одну пару целых чисел, удовлетворяющую условию, а затем заменить полученный x остатком от его деления на 35.

Применим сначала алгоритм Евклида для чисел 19 и 35, затем обобщённый алгоритм Евклида.

35 = 19 ∙ 1 + 16

19 = 16 ∙ 1 + 3

16 = 3 ∙ 5 + 1

3 = 1 ∙ 3

Теперь выразим 1 = НОД (19, 35) в виде линейной комбинации чисел 19 и 35.

1 = 16 – 3 ∙ 5 = 16 – (19 – 16) ∙ 5 = 16 ∙ 6 – 19 ∙ 5 = (35 – 19) ∙ 6 – 19 ∙ 5 = 35 ∙ 6 – 19 ∙ 11.

Итак, при поиске решения уравнения мы получили x = -11.

Поскольку x должен быть одним из остатков при делении на 35, мы должны заменить -11 остатком от деления на 35. Тогда получим число 24. Это число равно 1/19 в кольце вычетов по модулю 35.

Наконец, вспомним, что мы искали значение 3/19. Для этого умножим число 24 на 3 и разделим результат на 35 с остатком. Получим число 2.

Ответ: 2.

Примечание.

Ответ в этой задаче легко проверить. В самом деле, если мы умножим число 2 на 19, получим число 38, что сравнимо с 3 по модулю 35. То есть 19 x ≡ 3 (mod 35), а, значит,

x = 3/19 в кольце вычетов по модулю 35.

3. Китайская теорема об остатках.

Найти наименьшее натуральное число, которое при делении на 3 даёт остаток 2, при делении на 5 остаток 3, при делении на 7 остаток 2.

Представим искомое число в виде суммы трёх чисел:

одно кратно 5 и 7 и даёт остаток 2 при делении на 3 (поскольку сравнение имеет решение, похожее сравнение было разобрано в задаче 2),

второе кратно 3 и 5 и даёт остаток 2 при делении на 7 (по аналогичной причине),

третье кратно 7 и 3 и даёт остаток 3 при делении на 5.

Первое число будет равно 35, второе равно 30, третье равно 63. Сумма этих чисел равна 128.

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

Чтобы получить минимальное число, нужно разделить наш промежуточный результат 128 на произведение чисел 3, 5 и 7, то есть на число 105. Остаток равен 23, это и есть ответ. Проверьте, что он действительно даёт требуемые остатки.

Ответ: 23.

Примечание. Именно в такой формулировке, с этими числами, была разобрана эта задача в самом древнем из дошедших до нас источников – китайском сочинении III века н.э. Поэтому соответствующая теорема называется китайской теоремой об остатках.

4. Системы счисления.

Решите уравнение, записанное в 9-ичной системе счисления.

5x + 120 = 532

Решение запишите в 9-ичной и десятичной системах счисления.

(Это означает, например, что 500 в 9-ичной системе равно , поскольку число 9 в 9-ичной системе играет ту же роль, что число 10 в десятичной системе счисления).

Далее вычисляем в десятичной системе.

5x = 434 – 99 = 335

x = 335 : 5 = 67 (в десятичной системе).

x =

Ответ:

5. Найти представление рационального числа 343/155 непрерывной дробью.

Как только в знаменателе получили целое число, можем собрать все результаты в одну многоэтажную дробь.

Обычно такой ответ записывают в виде: (2; 4, 1, 2, 3, 3).

Техника вычислений (в предисловии: указать рекомендации, что считать вручную, а что на калькуляторе или компьютере, а также рекомендации о разделении материала на лекции и семинары).

Материалы для семинаров (для обязательного решения предлагаются задачи с номерами 1, 7, 8, 9, 10, остальные задачи приведены в качестве дополнительного материала)

ОТВЕТЫ ДЛЯ САМОКОНТРОЛЯ

Комбинаторика

Задачи комбинаторики.

1. Найти количество объектов, удовлетворяющих некоторым условиям.

2. Занумеровать их и построить алгоритм нахождения элемента по номеру и номера по элементу.

Правило произведения

Если А содержит n элементов, множество В содержит m элементов, то множество пар вида (a_i, b_j), где a_i  А, b_j  B, содержит mn элементов.

Пример

Сколько способов поставить две шахматные ладьи на доску 8х8 так, чтобы они не «били» друг друга?

Решение.

Есть 64 способа поставить первую ладью, и на каждый из них приходится по 49 способов поставить вторую ладью (поскольку первая ладья занимает одну клетку, и бьёт при этом 14 клеток, то остаётся 49 клеток для второй ладьи). Таким образом, получим 64  49 вариантов расстановки двух ладей.

Но при этом каждую расстановку при таком подсчёте мы сосчитаем дважды, поскольку могли бы начать с первой ладьи, а могли бы со второй. Поэтому найденное количество нужно разделить на 2.

64  49 / 2 = 1568.

Ответ. 1568.

Пример 2

Сколько существует трёхзначных чисел, у которых все цифры различны?

Решение. Для первой цифры 9 вариантов, от 1 до 9. Когда её выбрали, для второй цифры тоже 9 вариантов, поскольку она не должна совпасть с первой. Когда выбрали первые две цифры, то для третьей осталось 8 вариантов.

По правилу произведения получим ответ: .

Ответ: 648.