Делимость

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

Определение


 Если для некоторого целого числа a и целого числа b существует такое целое число q, что bq=a, то говорят, что число a делится нацело на b или что b делит a.
 При этом число b называется делителем числа a, делимое a будет кратным числа b, а число q называется частным от деления a на b.
 Хотя свойство делимости определено на всём множестве целых чисел, обычно рассматривается лишь делимость натуральных чисел. В частности, функция количества делителей натурального числа подсчитывает лишь его положительные делители.

Обозначения



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


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

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



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


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

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

Свойства



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

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


0a.

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


a1.

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


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

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


1aa=±1.

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


  • Если ab и |b|>|a|, то a=0. Отсюда же следует, что если ab и a0 то |a||b|.


  • Для того чтобы ab необходимо и достаточно, чтобы |a||b|.


  • Если a1b,a2b,,anb, то (a1+a2++an)b.


  • Свойство делимости является отношением нестрогого порядка и, в частности, оно:
    • рефлексивно, то есть любое целое число делится на себя же: aa.
    • транзитивно, то есть если ab и bc, то ac.
    • антисимметрично, то есть если ab и ba, то либо a=b, либо a=b.

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


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

n=1Nτ(n)=NlnN+(2γ1)N+O(Nθ),
  в которой γ — постоянная Эйлера — Маскерони, а для θ Дирихле получил значение 12. Этот результат многократно улучшался, и в настоящее время наилучший известный результат θ=131416 (получен в 2003 году Хаксли). Однако, наименьшее значение θ, при котором эта формула останется верной, неизвестен (доказано, что он не меньше, чем 14).
 При этом средний делитель большого числа n в среднем растёт как c1nlnn, что было обнаружено А. Карацубой.. По компьютерным оценкам М. Королёва c1=1πp(p3/2p1ln(1+1p))0,7138067.

Обобщения


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