Делимость

Систематическое изучение делимости началось в древнегреческой математике. Книги VII—IX «Начал» Евклида (около 300 года до н. э.) целиком посвящены теории чисел и содержат в геометрической форме почти всё, что составляет современное элементарное учение о делимости: определение делителя и кратного, алгоритм последовательного вычитания для нахождения наибольшей общей меры (предложения VII.1—2), лемму о простом делителе произведения (VII.30), доказательство бесконечности множества простых чисел (IX.20) и критерий чётного совершенного числа (IX.36)^[6].

Числа при этом трактовались как отрезки, а делимость — как соизмеримость: одно число «измеряет» другое, если укладывается в нём целое число раз. Алгоритм Евклида в этой трактовке представлял собой последовательное откладывание меньшего отрезка на большем.

Никомах Герасский в «Введении в арифметику» (около 100 года н. э.) классифицировал числа по сравнению суммы их собственных делителей с самим числом: совершенные, избыточные и недостаточные^[7].

Распространение позиционной десятичной записи сделало практически важными признаки делимости; их приводит, в частности, Леонардо Пизанский в «Книге абака» (1202)^[8].

Новый этап связан с П. Ферма, который в 1640-х годах сформулировал малую теорему и применил метод бесконечного спуска к вопросам делимости. Л. Эйлер ввёл функцию ${\displaystyle \varphi (n)}$ и доказал обобщение теоремы Ферма, а также установил связь делимости с дзета-функцией через эйлерово произведение^[9][10][11].

Решающий шаг сделал К. Ф. Гаусс в «Арифметических исследованиях» (1801). Он ввёл язык сравнений с обозначением ${\displaystyle a\equiv b{\pmod {m}}}$, что позволило говорить о делимости алгебраически — как о равенстве в кольце вычетов, — и дал первое полное доказательство основной теоремы арифметики^[12].

В середине XIX века выяснилось, что однозначность разложения на простые множители — не универсальное свойство. В кольце ${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$

${\displaystyle 6=2\cdot 3=(1+{\sqrt {-5}})(1-{\sqrt {-5}}),}$

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

Э. Куммер в 1847 году восстановил однозначность, введя «идеальные числа», а Р. Дедекинд в 1871 году заменил их идеалами — подмножествами кольца, замкнутыми относительно сложения и умножения на элементы кольца. В дедекиндовых кольцах однозначно разлагается на простые множители всякий идеал, даже когда для элементов это неверно. Так изучение делимости породило современную коммутативную алгебру^[13].

Аналитическое направление, начатое Дирихле, привело к проблеме делителей, над которой работали Вороной, Харди, ван дер Корпут и Хаксли. В 1978 году делимость приобрела прикладное значение: криптосистема RSA опирается на резкую асимметрию между лёгкостью перемножения простых чисел и трудностью обратной задачи — разложения на множителиБухштаб А. А. Теория чисел : учебное пособие для физ.-мат. фак. пед. ин-тов. — 2-е изд., испр.. — М.: Просвещение, 1966. — С. 13—14..

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

• ${\displaystyle b\mid a}$ — «${\displaystyle b}$ делит ${\displaystyle a}$»; это международное обозначение, принятое в большинстве современных руководств;
• ${\displaystyle a,\vdots ,b}$ — «${\displaystyle a}$ делится на ${\displaystyle b}$»; запись распространена в русскоязычной учебной литературе^[18].

Отрицание обозначается перечёркнутым символом: ${\displaystyle b\nmid a}$. Например, ${\displaystyle 3\mid 12}$, но ${\displaystyle 5\nmid 12}$.

• Нуль делится на любое ненулевое число, причём частное равно нулю: ${\displaystyle 0=a\cdot 0}$. Таким образом, всякое ненулевое целое число является делителем нуля в смысле отношения делимости (это не следует смешивать с алгебраическим понятием «делитель нуля», означающим ненулевой элемент ${\displaystyle x}$, для которого ${\displaystyle xy=0}$ при некотором ${\displaystyle y\neq 0}$; в кольце целых чисел таких элементов нет).
• Любое целое число делится на единицу: ${\displaystyle a=1\cdot a}$.
• Единица делится только на ${\displaystyle 1}$ и ${\displaystyle -1}$: из ${\displaystyle 1=aq}$ следует ${\displaystyle |a|\cdot |q|=1}$, откуда ${\displaystyle a=\pm 1}$. Числа ${\displaystyle \pm 1}$ — единственные обратимые элементы кольца целых чисел.
• Если ${\displaystyle b\mid a}$ и ${\displaystyle a\neq 0}$, то ${\displaystyle |a|\geqslant |b|}$. Равносильно: если ${\displaystyle b\mid a}$ и ${\displaystyle |b|>|a|}$, то ${\displaystyle a=0}$. Отсюда следует, что у ненулевого числа лишь конечное число делителей.
• ${\displaystyle b\mid a}$ тогда и только тогда, когда ${\displaystyle |b|\mid |a|}$.
• Линейность. Если ${\displaystyle b\mid a_{1},;b\mid a_{2},;\ldots ,;b\mid a_{n}}$, то ${\displaystyle b}$ делит любую целочисленную линейную комбинацию: ${\displaystyle b\mid (c_{1}a_{1}+c_{2}a_{2}+\dots +c_{n}a_{n})}$. В частности, ${\displaystyle b}$ делит сумму и разность.
• Если ${\displaystyle b\mid a}$, то ${\displaystyle bc\mid ac}$ для любого ${\displaystyle c}$; обратно, если ${\displaystyle bc\mid ac}$ и ${\displaystyle c\neq 0}$, то ${\displaystyle b\mid a}$.
• Лемма Евклида. Если простое число ${\displaystyle p}$ делит произведение ${\displaystyle ab}$, то оно делит хотя бы один из сомножителей. Это утверждение — ключ к доказательству единственности разложения на простые множители^[26].

На множестве натуральных чисел отношение делимости является отношением частичного порядка^[27]:

• рефлексивность: ${\displaystyle a\mid a}$, поскольку ${\displaystyle a=a\cdot 1}$;
• Транзитивность: если ${\displaystyle b\mid a}$ и ${\displaystyle c\mid b}$, то ${\displaystyle c\mid a}$;
• антисимметричность: если ${\displaystyle b\mid a}$ и ${\displaystyle a\mid b}$, то ${\displaystyle a=b}$ (для натуральных чисел).

Этот порядок частичный, а не линейный: числа ${\displaystyle 2}$ и ${\displaystyle 3}$ несравнимы, ни одно не делит другое. Наименьшим элементом служит ${\displaystyle 1}$ (единица делит всё), наибольшим — ${\displaystyle 0}$, если его включить в рассмотрение (нуль делится на всё). Относительно этого порядка множество натуральных чисел образует решётку, в которой точная нижняя грань пары — наибольший общий делитель, а точная верхняя — наименьшее общее кратное.

В кольце целых чисел антисимметричность нарушается: ${\displaystyle 2\mid -2}$ и ${\displaystyle -2\mid 2}$, но ${\displaystyle 2\neq -2}$. Поэтому там делимость задаёт лишь предпорядок; частичный порядок возникает после отождествления ассоциированных элементов, то есть отличающихся обратимым множителем^[28].

А. А. Карацуба обнаружил, что среднее арифметическое всех делителей числа ${\displaystyle n}$, то есть величина ${\displaystyle \rho (n)=\sigma (n)/\tau (n)}$, в среднем растёт как

${\displaystyle \rho (n)\sim {\frac {c_{1}n}{\sqrt {\ln n}}}}$,

то есть медленнее, чем само число, но лишь на логарифмический множитель^[41][42]. Численное значение постоянной, вычисленное М. А. Королёвым, составляет

${\displaystyle c_{1}={\frac {1}{\sqrt {\pi }}}\prod _{p}\left({\frac {p^{3/2}}{\sqrt {p-1}}},\ln \left(1+{\frac {1}{p}}\right)\right)\approx 0{,}71381,}$

где произведение берётся по всем простым числам^[43]. Константа возникает из метода Сельберга — Деланжа: функция ${\displaystyle \rho (n)/n}$ мультипликативна и на простых числах равна ${\displaystyle (1+1/p)/2}$, что даёт средний порядок с показателем ${\displaystyle \kappa =1/2}$ и множителем ${\displaystyle 1/\Gamma (1/2)=1/{\sqrt {\pi }}}$^[44].

Делимость — фундамент элементарной теории чисел: на ней строятся теория сравнений, китайская теорема об остатках, диофантовы уравнения. Линейное уравнение ${\displaystyle ax+by=c}$ разрешимо в целых числах тогда и только тогда, когда ${\displaystyle \gcd(a,b)\mid c}$ — критерий формулируется целиком в терминах делимости^[45][46].

В общей алгебре делимость определяется в любом кольце и служит для классификации колец: области целостности, факториальные кольца, кольца главных идеалов, евклидовы кольца. Аналогичная теория для кольца многочленов даёт алгоритм Евклида для многочленов, разложение на неприводимые множители и понятие наибольшего общего делителя многочленов^[47].

Стойкость RSA основана на том, что перемножить два больших простых числа легко, а разложить произведение обратно — вычислительно трудно. При этом сама схема использует делимость и на этапе построения ключей: показатели связаны сравнением ${\displaystyle ed\equiv 1{\pmod {\varphi (n)}}}$, которое решается расширенным алгоритмом Евклида^[48].

Вероятностные тесты простоты проверяют выполнение сравнений, вытекающих из малой теоремы Ферма. Хеш-таблицы используют остаток от деления как индекс корзины, причём в качестве модуля обычно берут простое число, чтобы уменьшить число коллизий.

Помехоустойчивое кодирование систематически применяет делимость многочленов: циклический избыточный код вычисляет остаток от деления многочлена сообщения на порождающий многочлен, а код Рида — Соломона строит кодовые слова как многочлены, делящиеся на заданный.

Контрольные цифры в номерах документов проверяются условием делимости взвешенной суммы. Для десятизначного ISBN-10 требуется

${\displaystyle \sum _{i=1}^{10}(11-i),a_{i}\equiv 0{\pmod {11}},}$

а для тринадцатизначного ISBN-13 используются веса 1 и 3 с проверкой по модулю 10.

Календарные расчёты опираются на делимость: год високосен в григорианском календаре, если он делится на 4, но не делится на 100, за исключением делящихся на 400. Определение дня недели по дате сводится к вычислению остатка по модулю 7. На делимости основаны также расчёт передаточных чисел в механике и построение музыкальных строёв, где интервалы задаются отношениями небольших целых чисел.

В произвольном коммутативном кольце ${\displaystyle R}$ говорят, что ${\displaystyle b}$ делит ${\displaystyle a}$, если ${\displaystyle a=bq}$ для некоторого ${\displaystyle q\in R}$. Основные понятия при этом расслаиваются на два, совпадающие в целых числах, но различные в общем случае:

• элемент ${\displaystyle p}$ называется неприводимым, если он не обратим и из ${\displaystyle p=xy}$ следует обратимость ${\displaystyle x}$ или ${\displaystyle y}$;
• элемент ${\displaystyle p}$ называется простым, если из ${\displaystyle p\mid xy}$ следует ${\displaystyle p\mid x}$ или ${\displaystyle p\mid y}$. Всякий простой элемент области целостности неприводим, обратное же верно не всегда: в ${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$ число ${\displaystyle 2}$ неприводимо, но не просто, так как делит ${\displaystyle 6=(1+{\sqrt {-5}})(1-{\sqrt {-5}})}$, не деля ни одного из сомножителей. Кольца, в которых оба понятия совпадают и разложение единственно, называются факториальными^[49].

Справедливы строгие включения: евклидовы кольца ⊂ кольца главных идеалов ⊂ факториальные кольца ⊂ области целостности. Кольцо ${\displaystyle \mathbb {Z} }$, кольцо многочленов ${\displaystyle K[x]}$ над полем и кольцо гауссовых целых чисел ${\displaystyle \mathbb {Z} [i]}$ евклидовы^[50].

В кольце ${\displaystyle \mathbb {Z} [i]={a+bi\mid a,b\in \mathbb {Z} }}$ делимость исследуется с помощью нормы ${\displaystyle N(a+bi)=a^{2}+b^{2}}$, которая мультипликативна. Простые числа обычной арифметики ведут себя по-разному: ${\displaystyle 5=(2+i)(2-i)}$ перестаёт быть простым, тогда как ${\displaystyle 3}$ остаётся простым и в ${\displaystyle \mathbb {Z} [i]}$. Согласно теореме Ферма — Эйлера, простое ${\displaystyle p}$ разлагается в ${\displaystyle \mathbb {Z} [i]}$ тогда и только тогда, когда ${\displaystyle p=2}$ или ${\displaystyle p\equiv 1{\pmod {4}}}$^[51].

Наиболее общая форма теории получается при переходе от элементов к идеалам: включение ${\displaystyle (a)\subseteq (b)}$ равносильно тому, что ${\displaystyle b}$ делит ${\displaystyle a}$, — «делить значит содержать». В дедекиндовых кольцах, в частности в кольцах целых алгебраических чисел, всякий ненулевой идеал единственным образом разлагается в произведение простых идеалов, даже если однозначность разложения элементов нарушена^[52].