Делимость

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

Определение

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

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

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

Обозначения

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

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

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

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

  $a=b\,q+r,$ где $0\leqslant r<|b|$.

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

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

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

Свойства

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

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

$\quad 0\,\vdots \,a.$

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

$\quad a\,\vdots \,1.$

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

$a\,\vdots \,0\quad \Rightarrow \quad a=0$,

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

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

$1\,\vdots \,a\quad \Rightarrow \quad a=\pm 1.$

• Для любого целого числа $a\neq 0$ найдётся такое целое число $b\neq a,$ для которого $b\,\vdots \,a.$

• Если $a\,\vdots \,b$ и $\left|b\right|>\left|a\right|,$ то $a\,=\,0.$ Отсюда же следует, что если $a\,\vdots \,b$ и $a\neq 0$ то $\left|a\right|\geqslant \left|b\right|.$

• Для того чтобы $a\,\vdots \,b$ необходимо и достаточно, чтобы $\left|a\right|\vdots \left|b\right|.$

• Если $a_{1}\,\vdots \,b,\,a_{2}\,\vdots \,b,\,\dots ,\,a_{n}\,\vdots \,b,$ то $\left(a_{1}+a_{2}+\dots +a_{n}\right)\,\vdots \,b.$

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

В системе целых чисел выполняются только первые два из этих трёх свойств; например, $2\,\vdots -2$ и $-2\,\vdots \,2,$ но $2\neq -2$. То есть отношение делимости целых чисел является только лишь предпорядком.

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

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

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

$\sum _{n=1}^{N}\tau (n)=N\ln N+(2\,\gamma -1)N+O\left(N^{\theta }\right).$

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

При этом средний делитель большого числа n в среднем растёт как ${\frac {c_{1}n}{\sqrt {\ln n}}}$, что было обнаружено А. Карацубой. По компьютерным оценкам М. Королёва $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$.

Обобщения

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

См. также

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

Ссылки

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

Литература

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