Делимость

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

ОпределениеПравить

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

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

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

ОбозначенияПравить

• $a⋮<!--\; ⋮\; -->b$$a\,\vdots \,b$  означает, что $a$$a$  делится на $b$$b$ , или что число $a$$a$  кратно числу $b$$b$ .

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

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

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

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

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

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

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

СвойстваПравить

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

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

$0⋮<!--\; ⋮\; -->a.$$\quad 0\,\vdots \,a.$ 

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

$a⋮<!--\; ⋮\; -->1.$$\quad a\,\vdots \,1.$ 

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

$a⋮<!--\; ⋮\; -->0\Rightarrow <!--\; \Rightarrow \; -->a=0$$a\,\vdots \,0\quad \Rightarrow \quad a=0$ ,

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

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

$1⋮<!--\; ⋮\; -->a\Rightarrow <!--\; \Rightarrow \; -->a=\pm <!--\; \pm \; -->1.$$1\,\vdots \,a\quad \Rightarrow \quad a=\pm 1.$ 

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

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

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

• Если $a_1⋮<!--\; ⋮\; -->b,a_2⋮<!--\; ⋮\; -->b,\dots <!--\; \dots \; -->,a_n⋮<!--\; ⋮\; -->b,$$a_{1}\,\vdots \,b,\,a_{2}\,\vdots \,b,\,\dots ,\,a_{n}\,\vdots \,b,$  то $\left(a_1+a_2+\cdots <!--\; \cdots \; -->+a_n\right)⋮<!--\; ⋮\; -->b.$$\left(a_{1}+a_{2}+\dots +a_{n}\right)\,\vdots \,b.$ 

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

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

Число делителейПравить

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

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

$\underset{n=1}{\overset{N}{\sum <!--\; \sum \; -->}}\mathrm{\tau <!--\; \tau \; -->}(n)=N\ln <!--\; \; -->N+(2\mathrm{\gamma <!--\; \gamma \; -->}-<!--\; -\; -->1)N+O\left(N^{\mathrm{\theta <!--\; \theta \; -->}}\right).$$\sum _{n=1}^{N}\tau (n)=N\ln N+(2\,\gamma -1)N+O\left(N^{\theta }\right).$ 

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

При этом средний делитель большого числа n в среднем растёт как $\frac{c_{1}n}{\sqrt{\ln <!--\; \; -->n}}$${\frac {c_{1}n}{{\sqrt {\ln n}}}}$ , что было обнаружено А. Карацубой. По компьютерным оценкам М. Королёва $c_1=\frac{1}{\mathrm{\pi <!--\; \pi \; -->}}\underset{p}{\prod <!--\; \prod \; -->}\left(\frac{p^{3/2}}{\sqrt{p-<!--\; -\; -->1}}\ln <!--\; \; -->\left(1+\frac{1}{p}\right)\right)\approx <!--\; \approx \; -->\mathrm{0,713}8067$$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 с.