Делимость

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

Определение

Если для некоторого целого числа a и целого числа b существует такое целое число q, что bq = a, то говорят, что число aделится нацело на b или, что b делит a.

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

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

Обозначения

•  означает, что a делится на b

• b | a или b \ a означает, что b делит a, или, что то же самое: b — делитель a.

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

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

• У каждого натурального числа, большего 1, есть хотя бы один простой делитель.

• Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.

• Вне зависимости от делимости целого числа a на целое число  , число a всегда можно разделить на b с остатком, то есть представить в виде:

 где  .

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

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

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

• Два целых числа a и b называются равноделимыми на целое число m, если либо и a, и b делится на m, либо ни a, ни b не делится на него.

Свойства

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

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

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

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

,

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

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

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

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

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

• Если   то 

• Свойство делимости является отношением нестрогого порядка и, в частности, оно:

  • рефлексивно, т.е. любое целое число делится на себя же: 

  • транзитивно, т.е. если   и   то 

  • антисимметрично, т.е. если   и   то либо   либо