4. Элементы теории чисел

ЦЕЛЫЕ ЧИСЛА ЗАНИМАЮТ ОДНО ИЗ КЛЮЧЕВЫХ МЕСТ в дискретной математике, которая нас особенно интересует в этой книге. Поэтому нам следует получить представление об элементах теории чисел — важном разделе математики, имеющем дело со свойствами целых чисел.

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

4.1 ОТНОШЕНИЕ ДЕЛИМОСТИ

Говорят, что делит (или же делится на ), если а отношение — целое число. Это свойство чисел лежит в основе всей их элементарной теории, так что разумно обзавестись для него специальным обозначением. Поэтому будем писать

(На самом деле, в существующей математической литературе гораздо более употребительно обозначение а не Но с вертикальной чертой вышел явный перебор — ее используют при записи абсолютных величин, множеств, условных вероятностей и т. д., в то время как с наклоненной влево чертой вышел явный недобор. Помимо всего прочего, обозначение создает впечатление, что как бы является знаменателем некоторого воображаемого отношения. Так что наберемся смелости склонить наш символ делимости влево!)

То, что не делит записывается как

Имеется аналогичное соотношение кратно которое означает почти то же самое с тем лишь отличием, что не обязано быть положительным числом. Это просто означает, что при некотором целом к. Так, например, существует только одно число, кратное 0 (а именно, сам 0), но ничто не делится на 0.

Каждое целое число кратно —1, но никакое целое число (строго говоря) не делится на —1. Эти определения применимы и тогда, когда вещественные числа; например, делится на Но мы почти всегда будем пользоваться ими, когда - целые числа. В конце концов, это всего лишь элементарная теория чисел.

Наибольший общий делитель двух целых чисел тип — это наибольшее целое число, которое делит их оба:

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

Другим хорошо известным понятием является наименьшее общее кратное

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

Одним из самых привлекательных свойств является простота его вычисления с помощью известного уже 2300 лет метода, называемого алгоритмом Евклида. Для вычисления заданных величин в алгоритме Евклида используется рекуррентность

Так, например, Указанная рекуррентность законна потому, что любой общий делитель чисел тип должен быть также общим делителем как числа так и числа которое равно . Вряд ли имеется рекуррентность для сколько-нибудь близкая по своей простоте к данной. (См. упр. 2.)

Алгоритм Евклида дает нам и нечто большее: его можно обобщить так, что он будет вычислять целые числа удовлетворяющие уравнению

Вот как это делается. Бели мы просто выбираем . В противном случае мы полагаем и применяем этот метод рекурсивно — подставляя вместо и вычисляя такие, что

А поскольку то это уравнение превращается в

Левая часть может быть переписана, чтобы показать, как она зависит от

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

Но чем же так привлекательно уравнение Главным образом тем, что числа фактически подтверждают, что в каждом конкретном случае алгоритм Евклида дает правильный ответ. Предположим, что после продолжительных вычислений наш компьютер сообщил, что и что но мы относимся к этому скептически и полагаем, что на самом деле имеется больший общий делитель, который машина почему-то, проглядела! Однако этого быть не может, потому что всякий общий делитель чисел тип должен делить а посему он должен делить и — следовательно, он должен быть . К тому же можно легко проверить, что действительно делит как так и (Алгоритмы, которые доставляют свои собственные подтверждения правильности результата, называются самоподтверждающими.)

До конца этой главы мы будем много раз пользоваться уравнением (4.5). Одним из его важных следствий является следующая мини-теорема:

(Доказательство. Если число к делит как так и то оно делит , а потому делит и Обратно, если число к делит то оно делит делитель и делитель а потому делит как так и Мы всегда знали, что всякий общий делитель чисел тип должен быть меньшим или равным их — по определению наибольшего общего делителя. А теперь мы узнали, что всякий общий делитель на самом деле является делителем их наибольшего общего делителя.

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

удобным правилом

которое справедливо в силу того, что пробегает те же делители числа что и . Так, при это означает, что . Справедливо также несколько более общее равенство,

которое немедленно следует из определения (4.1). Если — положительное число, то правая часть (4.8) есть следовательно, (4.8) влечет за собой (4.7). Но равенство (4.8) справедливо и при отрицательных (В таких случает ненулевые члены в правой части появляются тогда, когда к является отрицательным делителем

Кроме того, двойная сумма по делителям может быть „переставлена" по правилу

К примеру, если то это правило приобретает следующий вид:

Равенство (4.9) можно доказать с помощью нотации Айверсона. Его левая часть есть

а правая —

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