Теорема о делении с остатком¶

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

¶Формулировка теоремы

Для любых целых чисел \(a\) (делимое) и \(b\) (делитель, \(b \neq 0\)) существует единственная пара целых чисел \(q\) (неполное частное) и \(r\) (остаток), такая что:

\[ a = b \cdot q + r, \quad 0 \leqslant r < |b|. \]

Здесь \(|b|\) — модуль числа \(b\). Если \(b > 0\), то остаток \(r\) лежит в диапазоне от 0 до \(b-1\) включительно. Если \(b < 0\), то остаток \(r\) лежит в диапазоне от 0 до \(|b|-1\) включительно.

¶Примеры

1. Деление 17 на 5: \(17 = 5 \cdot 3 + 2\), где \(q = 3\), \(r = 2\).
2. Деление −17 на 5: \(-17 = 5 \cdot (-4) + 3\), где \(q = -4\), \(r = 3\). Обратите внимание: остаток положителен (0 ≤ 3 < 5).
3. Деление 17 на −5: \(17 = (-5) \cdot (-3) + 2\), где \(q = -3\), \(r = 2\).
4. Деление −17 на −5: \(-17 = (-5) \cdot 4 + 3\), где \(q = 4\), \(r = 3\).

¶Доказательство

¶Существование

Рассмотрим множество целых чисел вида \(a - b \cdot k\), где \(k\) пробегает все целые числа. Выберем такое \(k\), что разность неотрицательна. Например, при \(b > 0\) можно взять \(k = \lfloor a/b \rfloor\) (целая часть от деления). Тогда \(r = a - b \cdot k\) удовлетворяет условию \(0 \leqslant r < b\). Для \(b < 0\) аналогично берётся \(k = \lceil a/b \rceil\) или \(k = \lfloor a/|b| \rfloor\) с учётом знака. Полученное \(r\) удовлетворяет неравенству \(0 \leqslant r < |b|\).

¶Единственность

Предположим, существуют две пары \((q_1, r_1)\) и \((q_2, r_2)\), удовлетворяющие условиям: \[ a = b q_1 + r_1 = b q_2 + r_2, \quad 0 \leqslant r_1, r_2 < |b|. \] Тогда \(b(q_1 - q_2) = r_2 - r_1\). Левая часть делится на \(|b|\), правая по модулю меньше \(|b|\). Следовательно, \(r_2 - r_1 = 0\) и \(q_1 - q_2 = 0\), то есть пары совпадают.

¶Следствия и обобщения

¶Деление с остатком в кольце целых чисел

Теорема является частным случаем более общего понятия евклидова кольца. Кольцо целых чисел \(\mathbb{Z}\) является евклидовым, где в качестве нормы выступает абсолютная величина. В любом евклидовом кольце (например, кольце многочленов над полем) выполняется аналогичная теорема: для любых элементов \(a\) и \(b \neq 0\) существуют \(q\) и \(r\) такие, что \(a = b q + r\) и \(N(r) < N(b)\), где \(N\) — евклидова норма.

¶Алгоритм Евклида

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

¶Арифметика остатков (модульная арифметика)

Остаток от деления на \(m\) позволяет определить классы вычетов по модулю \(m\). Два числа считаются сравнимыми по модулю \(m\), если они дают одинаковые остатки при делении на \(m\). Это лежит в основе модульной арифметики, используемой в криптографии (например, RSA), теории кодирования и вычислительной технике.

¶Варианты определения остатка

В математической литературе и программировании встречаются разные соглашения о знаке остатка. В классической формулировке теоремы остаток всегда неотрицателен (0 ≤ r < |b|). Однако в некоторых языках программирования (например, C, C++, Java до Java 8, Python) реализовано деление с округлением к нулю, где остаток может быть отрицательным, если делимое отрицательно. В таких случаях условие теоремы заменяется на \(|r| < |b|\) и знак остатка совпадает со знаком делимого. В современной математике предпочтительнее неотрицательный остаток, так как он обеспечивает единственность и удобство в теоретических построениях.

¶Применение

• Алгоритмы: проверка чётности, нахождение цифр числа, разложение на множители, алгоритм Евклида.
• Криптография: шифрование с открытым ключом (RSA), протокол Диффи — Хеллмана.
• Теория чисел: доказательство свойств делимости, решение диофантовых уравнений, китайская теорема об остатках.
• Программирование: работа с циклическими структурами (например, индексация массивов), хеширование, генерация псевдослучайных чисел.
• Компьютерная арифметика: реализация деления в процессорах, операции с целыми числами произвольной точности.

¶История

Понятие деления с остатком известно с древности. В «Началах» Евклида (около 300 г. до н. э.) приводится алгоритм нахождения наибольшей общей меры двух отрезков, который по сути является геометрическим аналогом алгоритма Евклида, основанного на последовательном делении с остатком. В современной алгебраической формулировке теорема была осознана в XIX веке в рамках развития теории чисел и абстрактной алгебры (работы Гаусса, Дирихле, Дедекинда). В XX веке понятие евклидова кольца обобщило теорему на произвольные кольца с делением.

¶Интересные факты

• В некоторых системах (например, в языке программирования Python) оператор % возвращает именно неотрицательный остаток, что соответствует классической математической формулировке.
• Теорема о делении с остатком справедлива не только для целых чисел, но и для многочленов, гауссовых целых чисел, целых чисел Эйзенштейна и других евклидовых колец.
• Существует обобщение теоремы на случай деления с остатком в кольце целых чисел с произвольной нормой, однако для целых чисел классическая норма (абсолютная величина) является наиболее естественной.

¶Источники

• Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.
• Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — М.: Наука, 1965.
• Кострикин А. И. Введение в алгебру. Часть I. Основы алгебры. — М.: Физматлит, 2004.
• Ленг С. Алгебра. — М.: Мир, 1968.
• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — М.: Вильямс, 2007.