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

Определение

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

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

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

Обозначения

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

• или ^{[источник не указан 468 дней]} означает, что делит , или, что то же самое: — делитель .

Связанные определения

• У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
• У каждого натурального числа, большего 1, есть хотя бы один простой делитель.
• Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
• Вне зависимости от делимости целого числа на целое число , число a всегда можно разделить на b с остатком, то есть представить в виде:

  где .

В этом соотношении число называется неполным частным, а число r — остатком от деления на . Как частное, так и остаток определяются однозначно.

Число a делится нацело на b тогда и только тогда, когда остаток от деления a на b равен нулю.

• Всякое число, делящее как , так и , называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя: +1 и -1. Если других общих делителей нет, то эти числа называются взаимно простыми.
• Два целых числа и называются равноделимыми на целое число , если либо и , и делится на , либо ни , ни не делится на него.

Свойства

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

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

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

• На ноль делится только ноль:

,

причём частное в этом случае не определено.

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

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

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

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

• Если то

• Свойство делимости является отношением нестрогого порядка и, в частности, оно:
  • рефлексивно, т.е. любое целое число делится на себя же:
  • транзитивно, т.е. если и то
  • антисимметрично, т.е. если и то либо либо

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

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

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

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

Обобщения

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

См. также

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

Ссылки

• Видео о делимости

Примечания