Делимость

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

Определение

Если для некоторого целого числа [math]\displaystyle{ a }[/math] и целого числа [math]\displaystyle{ b }[/math] существует такое целое число [math]\displaystyle{ q }[/math], что [math]\displaystyle{ bq=a, }[/math] то говорят, что число [math]\displaystyle{ a }[/math] делится нацело на [math]\displaystyle{ b }[/math] или что [math]\displaystyle{ b }[/math] делит [math]\displaystyle{ a. }[/math]

При этом число [math]\displaystyle{ b }[/math] называется делителем числа [math]\displaystyle{ a }[/math], делимое [math]\displaystyle{ a }[/math] будет кратным числа [math]\displaystyle{ b }[/math], а число [math]\displaystyle{ q }[/math] называется частным от деления [math]\displaystyle{ a }[/math] на [math]\displaystyle{ b }[/math].

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

Обозначения

• [math]\displaystyle{ a\,\vdots\, b }[/math] означает, что [math]\displaystyle{ a }[/math] делится на [math]\displaystyle{ b }[/math], или что число [math]\displaystyle{ a }[/math] кратно числу [math]\displaystyle{ b }[/math].

• [math]\displaystyle{ b\mid a }[/math] означает, что [math]\displaystyle{ b }[/math] делит [math]\displaystyle{ a }[/math], или, что то же самое: [math]\displaystyle{ b }[/math] — делитель [math]\displaystyle{ a }[/math].

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

• У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
• У каждого натурального числа, большего [math]\displaystyle{ 1 }[/math], есть хотя бы один простой делитель.
• Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
• Используется также понятие тривиальных делителей: это само число и единица. Таким образом, простое число может быть определено как число, не имеющее никаких делителей, помимо тривиальных.
• Вне зависимости от делимости целого числа [math]\displaystyle{ a }[/math] на целое число [math]\displaystyle{ b\ne 0 }[/math], число [math]\displaystyle{ a }[/math] всегда можно разделить на [math]\displaystyle{ b }[/math] с остатком, то есть представить в виде:

  [math]\displaystyle{ a=b\,q + r, }[/math] где [math]\displaystyle{ 0 \leqslant r \lt |b| }[/math].

В этом соотношении число [math]\displaystyle{ q }[/math] называется неполным частным, а число [math]\displaystyle{ r }[/math] — остатком от деления [math]\displaystyle{ a }[/math] на [math]\displaystyle{ b }[/math]. Как частное, так и остаток определяются однозначно.

Число [math]\displaystyle{ a }[/math] делится нацело на [math]\displaystyle{ b }[/math] тогда и только тогда, когда остаток от деления [math]\displaystyle{ a }[/math] на [math]\displaystyle{ b }[/math] равен нулю.

• Всякое число, делящее как [math]\displaystyle{ a }[/math], так и [math]\displaystyle{ b }[/math], называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя: [math]\displaystyle{ +1 }[/math] и [math]\displaystyle{ -1 }[/math]. Если других общих делителей нет, то эти числа называются взаимно простыми.
• Два целых числа [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] называются равноделимыми на целое число [math]\displaystyle{ m }[/math], если либо и [math]\displaystyle{ a }[/math], и [math]\displaystyle{ b }[/math] делится на [math]\displaystyle{ m }[/math], либо ни [math]\displaystyle{ a }[/math], ни [math]\displaystyle{ b }[/math] не делится на него.
• Говорят, что число [math]\displaystyle{ a }[/math] кратно числу [math]\displaystyle{ b }[/math], если [math]\displaystyle{ a }[/math] делится на [math]\displaystyle{ b }[/math] без остатка. Если число [math]\displaystyle{ c }[/math] делится без остатка на числа [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math], то оно называется их общим кратным. Наименьшее такое натуральное [math]\displaystyle{ c }[/math] называется наименьшим общим кратным чисел [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math].

Свойства

Замечание: во всех формулах этого раздела предполагается, что [math]\displaystyle{ a,\,b,\,c }[/math] — целые числа.

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

[math]\displaystyle{ \quad0\,\vdots\,a. }[/math]

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

[math]\displaystyle{ \quad a\,\vdots\,1. }[/math]

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

[math]\displaystyle{ a\,\vdots\,0\quad\Rightarrow\quad a = 0 }[/math],

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

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

[math]\displaystyle{ 1\,\vdots\,a\quad\Rightarrow\quad a = \pm 1. }[/math]

• Для любого целого числа [math]\displaystyle{ a \ne 0 }[/math] найдётся такое целое число [math]\displaystyle{ b \ne a, }[/math] для которого [math]\displaystyle{ b\,\vdots\,a. }[/math]

• Если [math]\displaystyle{ a\,\vdots\,b }[/math] и [math]\displaystyle{ \left|b\right| \gt \left|a\right|, }[/math] то [math]\displaystyle{ a\,=\,0. }[/math] Отсюда же следует, что если [math]\displaystyle{ a\,\vdots\,b }[/math] и [math]\displaystyle{ a \ne 0 }[/math] то [math]\displaystyle{ \left|a\right| \geqslant \left|b\right|. }[/math]

• Для того чтобы [math]\displaystyle{ a\,\vdots\,b }[/math] необходимо и достаточно, чтобы [math]\displaystyle{ \left|a\right| \vdots \left|b\right|. }[/math]

• Если [math]\displaystyle{ a_1\,\vdots\,b,\,a_2\,\vdots\,b,\,\dots,\,a_n\,\vdots\,b, }[/math] то [math]\displaystyle{ \left( a_1 + a_2 + \dots + a_n \right)\,\vdots\,b. }[/math]

• Отношение делимости натуральных чисел является отношением нестрогого порядка и, в частности, оно:
  • рефлексивно, то есть любое целое число делится на себя же: [math]\displaystyle{ \quad a\,\vdots\,a. }[/math]
  • транзитивно, то есть если [math]\displaystyle{ a\,\vdots\,b }[/math] и [math]\displaystyle{ b\,\vdots\,c, }[/math] то [math]\displaystyle{ a\,\vdots\,c. }[/math]
  • антисимметрично, то есть если [math]\displaystyle{ a\,\vdots\,b }[/math] и [math]\displaystyle{ b\,\vdots\,a, }[/math] то [math]\displaystyle{ a\,=\,b. }[/math]

В системе целых чисел выполняются только первые два из этих трёх свойств; например, [math]\displaystyle{ 2\,\vdots-2 }[/math] и [math]\displaystyle{ -2\,\vdots\,2, }[/math] но [math]\displaystyle{ 2 \ne -2 }[/math]. То есть отношение делимости целых чисел является только лишь предпорядком.

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

Основная статья: Число делителей

Число положительных делителей натурального числа [math]\displaystyle{ n, }[/math] обычно обозначаемое [math]\displaystyle{ \tau(n), }[/math] является мультипликативной функцией, для неё верна асимптотическая формула Дирихле:

[math]\displaystyle{ \sum_{n=1}^N\tau(n)=N\ln N+(2\,\gamma-1)N+O\left(N^\theta\right). }[/math]

Здесь [math]\displaystyle{ \gamma }[/math] — постоянная Эйлера — Маскерони, а для [math]\displaystyle{ \theta }[/math] Дирихле получил значение [math]\displaystyle{ \frac{1}{2}. }[/math] Этот результат многократно улучшался, и в настоящее время наилучший известный результат [math]\displaystyle{ \theta=\frac{131}{416} }[/math] (получен в 2003 году Хаксли). Однако, наименьшее значение [math]\displaystyle{ \theta }[/math], при котором эта формула останется верной, неизвестен (доказано, что он не меньше, чем [math]\displaystyle{ \frac{1}{4} }[/math]).

При этом средний делитель большого числа n в среднем растёт как [math]\displaystyle{ \frac{c_1 n}{\sqrt{\ln n}} }[/math], что было обнаружено А. Карацубой. По компьютерным оценкам М. Королёва [math]\displaystyle{ c_1=\frac{1}{\pi}\prod_p \left(\frac{p^{3/2}}{\sqrt{p-1}} \ln\left(1+\frac{1}{p}\right)\right)\approx 0{,}7138067 }[/math].

Обобщения

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

См. также

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

Ссылки

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

Литература

• Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
• Воробьев Н. Н. Признаки делимости. — 4-е изд. — М.: Наука, 1988. — Т. 38. — 96 с. — (Популярные лекции по математике). — ISBN 5-02-013731-6.
• Делимость // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 95. — 352 с.