Материал: LS-Sb89586

1.6. Второй способ нахождения линейного представления наибольшего общего делителя

ax + by = r

Исходные числа a и b тоже можно представить в виде линейной комбинации a и b:

aa 1 b 0,

ba 0 b 1.

Запишем это в общем виде

a a xa b ya , b a xb b yb.

Разделим a на b с остатком:

a q b r.

Подставим вместо a и b их представления

axa bya q axb byb r.

Приведя подобные, получим

a xa qxb b ya qyb r, или axr byr r.

Повторяя подобное деление необходимое число раз, получим

axd byd d

(при этом коэффициенты для следующего остатка легко находятся через коэффициенты предыдущего остатка). Пример представлен в табл. 1.1.

Таблица 1.1

Для контроля вычислений можно проверять для каждого столбца выполнение равенства axr byr r . Например, 64 · 4 + 81 · (–3) = 13.

Окончательно имеем: 64 · 19 + 81 · (–15) = 1.

6

1.7.Свойства НОД

1.Если m – любое положительное число, то (am, bm) (a, b)m .

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

Найти все целые x и y, такие, что ax + by = c (где a, b, c – целые числа). Уравнения в целых числах называют диофантовыми по имени древне-

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

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

Пример:

2x + 5y = 17. (1.2)

Сначала найдем множество решений уравнения 2x + 5y = 1. 2 3 – 5 1 = 1, поэтому можем считать, что x0 = 3, x0 = –1.

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

Получим: 17 x0 = 51, 17 y0 = –17.

В этом случае 2 (17 x0 ) + 5 (17 y0 ) = 17.

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

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

условию (1.2), поскольку слагаемое 2x увеличится на 10t, а слагаемое 5y уменьшится на 10t.

7

Итак, ответ:

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

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

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

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

составным.

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

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

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

лу p. Можно остановить действия тогда, когда величина p2 превзойдет n.

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

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

1.12.Степень вхождения данного простого числа

вразложение факториала

Несложно разложить на простые множители факториал натурального числа. Каждое простое число p входит в разложение числа n! следующее количество раз:

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

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

8

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

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

все: p1, p2 , … , pn .

Затем перемножим все эти числа и прибавим 1. Рассмотрим число

N p1 p2 ... pn 1.

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

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

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

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

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

n 1

соб записи чисел в виде ak bk , 0 ak b .

k 0

При этом ak – цифры этого числа. Самая распространенная система

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

Для перехода, например, от девятиричной системы счисления к десятичной

ричной системе равно числу 307 в десятичной системе счисления.

Обратный переход (от записи в десятичной к записи в девятеричной систе-

n 1

ме) осуществляется так. Ищем представление числа в виде ak 9k , причем по-

k 0

иск начнем с последней цифры, которая равна остатку от деления числа на 9.

9

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

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

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

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

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

Пример: 21 15 (mod 3).

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

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

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

1.17. Решение уравнений в кольце остатков по данному модулю

Сравнение ax 1(modb) всегда имеет решение, если числа a и b взаимно

просты.

Это следует из того, что выражение ax – by = 1 – это линейное представление наибольшего общего делителя a и b.

Такую задачу иногда формулируют в виде: найти 1/a в кольце вычетов по модулю b. В самом деле, выражение ax = 1 означает по сути то же самое, что x = 1/a (x – искомая величина).

10