Линейные диофантовы уравнения с двумя неизвестными

Найти все целые x и y, такие, что ax + by = c (где a, b, c – целые числа).

Уравнения в целых числах называют диофантовыми по имени древнегреческого математика Диофанта, жившего, предположительно, в III веке н.э. Линейные диофантовы уравнения содержат неизвестные величины только в первой степени.

Напоминаем, что решить уравнение – значит найти все его решения и доказать, что других нет. В частности, если уравнение имеет бесконечно много решений, нужно описать всё множество решений некоторой общей формулой, а не ограничиться одним или несколькими примерами. С другой стороны, если уравнение имеет пустое множество решений, то обосновать этот факт – тоже означает решить уравнение.

Пример

2x + 5y = 17 (2)

Сначала найдём множество решений уравнения 2x + 5y = 1.

2  3 – 5  1 = 1, поэтому можем считать, что x₀ = 3, y₀ = –1.

Поскольку мы решаем уравнение 2x + 5y = 17, а не 2x + 5y = 1, то значения x₀ и y₀ нужно увеличить в 17 раз.

Получим: 17x₀ = 51, 17y₀ = –17.

В этом случае 2  (17x₀) + 5  (17y₀) = 17.

Но задача состоит в том, чтобы найти все пары целых чисел, удовлетворяющих равенству (2).

Если увеличить 17x₀ на 5t, а 17y₀ уменьшить на 2t (где t – некоторое целое число), то пара чисел x = 17x₀ + 5t и y = 17y₀ – 2t будет удовлетворять условию (2), поскольку слагаемое 2x увеличится на 10t, а слагаемое 5y уменьшится на 10t.

Итак, ответ:

x = 51 + 5t, y = –17 – 2t.

Примечание

Некоторые линейные диофантовы уравнения имеют пустое множество решений, например, 6x + 21y = 2. При этом левая часть равенства кратна 3, а правая часть равенства не кратна 3.

Простые числа

Определение.

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

Примечание.

Число 1 не является ни простым, ни составным.

Решето Эратосфена

Удобный способ выписать все простые числа, не превосходящие заданного натурального числа, придумал древнегреческий математик Эратосфен (276 год до н. э. — 194 год до н. э.). Идея состоит в том, чтобы выписать подряд все целые числа от 2 до некоторого числа n, а затем вычеркнуть сначала все числа, кратные 2, затем все числа, кратные 3, и так далее, вычёркивая все числа, кратные простому числу p. Можно остановить действия тогда, когда величина p² превзойдёт n.

Основная теорема арифметики

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

Примеры

1. Разложение на множители числа 1200.

2. На сколько нулей оканчивается произведение всех чисел от 1 до 100? (Его обозначают 100!, и называют «сто факториал»).

Выясним, на какую наибольшую степень числа 10 делится наше число, то есть в какой степени входят в данное число простые множители 2 и 5.

Множитель 5 встречается в 20 числах, и при этом в 4 числах он встречается в степени 2 (это числа 25, 50, 75 и 100). Поэтому в произведение множитель 5 входит в степени 24.

Число 2 входит в произведение в степени, превышающей 24.

Итак, 100! содержит 10 в степени 24, поэтому оканчивается на 24 нуля.

Степень вхождения данного простого числа в разложение факториала

Несложно разложить на простые множители факториал натурального числа, воспользовавшись рассуждениями, наподобие только что приведённых для деления 100! на 5.

Каждое простое число p входит в разложение числа n! следующее количество раз:

(Обоснование формулы состоит в том, что сначала рассматривают числа, кратные p, затем кратные квадрату p, затем кратные кубу p, и так далее).

Количество слагаемых не бесконечно, поскольку начиная с некоторого места они равны нулю.

Теорема Евклида о бесконечности множества простых чисел

Доказательство бесконечности множества простых чисел.

Предположим, что простых чисел конечное количество. Выпишем их все: p₁, p₂, … , p_n.

Затем перемножим все эти числа и прибавим 1. Рассмотрим число N = p₁ ∙ p₂ ∙ … ∙ p_n + 1.

Это число не может быть простым, поскольку больше любого из простых чисел.

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

Получаем противоречие, которое говорит о том, что простых чисел бесконечно много.

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

Определение.

Позиционная система счисления с основанием b – это способ записи чисел в виде .

При этом a_k – цифры этого числа.

Самая распространённая система счисления – десятичная, но иногда (например, в программировании) используют и двоичную систему, и восьмеричную, и шестнадцатиричную системы счисления.

Деление часа и градуса на 60 минут и 3600 секунд осталось нам в память о шестидесятиричной системе, использовавшейся в древности.

Для перехода от недесятичной системы (например, девятиричной) к десятичной запишите выражение вида , подставьте его цифры и найдите таким образом значение.

Например, , то есть число 371 в девятиричной системе равно числу 307 в десятичной системе счисления.

Обратный переход (от записи в десятичной к записи в девятеричной системе) осуществляется так. Ищем представление числа в виде , причём поиск начнём с последней цифры, которая равна остатку от деления числа на 9.

Сначала разделим число 307 на 9 с остатком, остаток равен 1. Это последняя цифра девятиричной записи числа.

(307 – 1) : 9 = 34. Остаток от деления на 9 этого числа равен 7. Поэтому вторая с конца цифра равна 7.

(34 – 7) : 9 = 3. Поэтому первая цифра равна 3.

Сравнение по модулю

Определение

Говорят, что a сравнимо с b по модулю c, если . В этом случае пишут a  b (mod c), или a  b (c).

Пример

21  15 (mod 3).

Модульная арифметика

Определение

Кольцо остатков по данному модулю n - это множество всех остатков от деления натуральных чисел на данное число n. Это множество обозначают как Z_n.

Название «кольцо остатков» связано с тем, что множество всех остатков удовлетворяет некоторым свойствам, принятым в алгебре. Подробный список этих свойств для краткости здесь приводить не будем.

Например, составим таблицу сложения в кольце остатков по модулю 4. Складывая остатки, результат сложения заменим его остатком от деления на 4.

Например, 1 + 3 заменим 0.

+	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

Таблица умножения в том же кольце остатков.

х	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

Обратите внимание на то, что в данном кольце остатков произведение двух ненулевых чисел (2 и 2) равно нулю.