Дели́мость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

Определение

Если для некоторого целого числа и целого числа существует такое целое число , что то говорят, что число делится нацело на или что делит

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

Хотя свойство делимости определено на всём множестве целых чисел, обычно рассматривается лишь делимость натуральных чисел. В частности, функция количества делителей натурального числа подсчитывает лишь его положительные делители.

Обозначения означает, что делится на , или что число кратно числу .

означает, что делит , или, что то же самое:  — делитель .

Связанные определения У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным. У каждого натурального числа, большего , есть хотя бы один простой делитель. Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица. Используется также понятие тривиальных делителей: это само число и единица. Таким образом, простое число может быть определено как число, не имеющее никаких делителей, помимо тривиальных. Вне зависимости от делимости целого числа на целое число , число всегда можно разделить на с остатком, то есть представить в виде: где . В этом соотношении число называется неполным частным, а число  — остатком от деления на . Как частное, так и остаток определяются однозначно. Число делится нацело на тогда и только тогда, когда остаток от деления на равен нулю. Всякое число, делящее как , так и , называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя: и . Если других общих делителей нет, то эти числа называются взаимно простыми. Два целых числа и называются равноделимыми на целое число , если либо и , и делится на , либо ни , ни не делится на него. Говорят, что число кратно числу , если делится на без остатка. Если число делится без остатка на числа и , то оно называется их общим кратным. Наименьшее такое натуральное называется наименьшим общим кратным чисел и .

Свойства Замечание: во всех формулах этого раздела предполагается, что  — целые числа.

Любое целое число является делителем нуля:

и частное (при ) равно нулю.

Любое целое число делится на единицу:

На ноль делится только ноль: , причём частное в этом случае однозначно не определено.

Единица делится только на единицу:

Для любого целого числа найдётся такое целое число для которого

Если и то Отсюда же следует, что если и то

Для того чтобы необходимо и достаточно, чтобы

Если то

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

Число делителей

Число положительных делителей натурального числа обычно обозначаемое является мультипликативной функцией, для неё верна асимптотическая формула Дирихле:

Здесь  — постоянная Эйлера — Маскерони, а для Дирихле получил значение Этот результат многократно улучшался, и в настоящее время наилучший известный результат (получен в 2003 году Хаксли). Однако наименьшее значение , при котором эта формула останется верной, неизвестно (доказано, что оно не меньше, чем ).

При этом средний делитель большого числа n в среднем растёт как , что было обнаружено А. Карацубой. По компьютерным оценкам М. Королёва .

Обобщения

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

См. также Кратность Деление (математика) Деление с остатком Признаки делимости Модульная арифметика Конгруэнтность (алгебра) Сравнение по модулю Кольцо (математика) Факторизация

Ссылки Видео о делимости

Примечания

Литература Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.

Категория:Математические отношения Категория:Теория чисел Категория:Арифметика Категория:Делимость и остатки