Делимость

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

Определение 

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

 Если  то 

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

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

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

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

Обобщения 

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

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

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

Примечания

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

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