Частные числа в теории чисел¶

Частное — это результат деления одного числа на другое. В теории чисел под частным понимают целую часть от деления одного натурального числа на другое; если же рассматривать деление с остатком, то частное — это целочисленный результат операции деления, а остаток отбрасывается или учитывается отдельно. Понятие частного является одним из фундаментальных в арифметике и лежит в основе построения системы счисления, алгоритмов и многих разделов математики.

¶Определение и обозначения

Пусть $a$ и $b$ — натуральные числа, $b \neq 0$. Частное от деления $a$ на $b$ обозначают $a \div b$ или $\lfloor a/b \rfloor$, если говорим о целой части частного. В школьной арифметике под частным обычно понимают число $q$, такое что

$$a = b \cdot q + r, \quad 0 \le r < b,$$

где $q$ — частное, а $r$ — остаток от деления. Такое разложение единственно при указанных ограничениях и называется алгоритмом Евклида (или делением с остатком).

Если делимое делится нацело ($r = 0$), то частное называют точным. Если же $a < b$, то частное равно нулю, а остаток — самому числу $a$.

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

В кольце целых чисел $\mathbb{Z}$ операция деления определена не для всех пар: частное $a/b$ принадлежит $\mathbb{Z}$ лишь тогда, когда $b$ делит $a$ без остатка. Это ограничение приводит к необходимости введения понятия делимости, делителей, кратных и НОД (наибольшего общего делителя), что составляет основу элементарной теории чисел.

Понятие частного тесно связано с остатком от деления: два числа, дающих одинаковый остаток при делении на $b$, называются сопряжёнными по модулю $b$. Классы сопряжённых чисел образуют кольцо вычетов $\mathbb{Z}_b$ — важнейший объект современной алгебры и криптографии.

¶Частное в рациональных числах

Если разрешить деление любых двух целых чисел (кроме деления на ноль), получается множество рациональных чисел $\mathbb{Q}$. В этом случае частное $a/b$ — это рациональное число, записываемое в виде дроби. Деление в $\mathbb{Q}$ обратимо: для любого ненулевого $b$ существует обратный элемент $1/b$.

При вычислении частного в виде десятичной дроби возможны три случая: конечная дробь (например, $6 \div 3 = 2$), бесконечная периодическая дробь ($1 \div 3 = 0{,}333\ldots$) или, в общем случае для иррациональных чисел, бесконечная непериодическая дробь.

¶Частное в алгебраических структурах

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

В теории делимости для многочленов определено аналогичное понятие: если $P(x)$ и $Q(x)$ — многочлены, то частное от деления $P$ на $Q$ — это многочлен $S(x)$, такой что $P(x) = Q(x) \cdot S(x) + R(x)$, где степень $R$ меньше степени $Q$.

¶Алгоритмы вычисления частного

Наиболее известные алгоритмы вычисления частного:

• Деление столбиком — классический школьный алгоритм, основанный на пошаговом вычитании кратных делителя.
• Алгоритм Евклида — нахождение НОД через последовательное деление с остатком.
• Деление с умножением — быстрый метод, применяемый в процессорах, основанный на приближённом reciprocal.
• Алгоритм Кнута — деление длинных чисел, используемое в компьютерной арифметике.

В двоичной системе счисления деление реализуется особенно просто: сдвигом и вычитанием, что используется в аппаратной части процессоров.

¶Частное и остаток в прикладных задачах

Понятие частного широко применяется в компьютерных науках: операция целочисленного деления встроена во все языки программирования, однако в некоторых из них (например, в Python) остаток от деления отрицательных чисел определяется иначе, чем в C или Java, что приводит к известным различиям в поведении программ.

В криптографии схемы на основе кольца вычетов (RSA, Эль-Гамаль) используют свойства частного и остатка при делении по модулю. Понятие обратного элемента по модулю, без которого невозможно дешифрование, определяется через уравнение вида $a \cdot x \equiv 1 \pmod{n}$, что является обобщённым частным.

¶Историческая справка

Понятие частного известно с древнейших времён: вавилонские и египетские математики решали задачи на деление задолго до появления формальной записи. Систематическое изложение теории делимости и частного дано в трудах Евклида («Начала», около 300 года до н. э.), где описан алгоритм нахождения НОД. В средние века арабские математики (аль-Хорезми, аль-Караджи) развили теорию целочисленного деления и ввели понятие остатка.

¶Источники

• Виноградов И. М. Основы теории чисел.
• Кнут Д. Искусство программирования, том 2: полуструктурированные данные.
• Новиков Л. А. Дискретная математика для программистов.
• Борухович З. А., Пантелеев А. Н. Теория чисел.