Interested Article - Делимость

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

Определение

Если для некоторого целого числа $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\,\vdots \,b$ $a\,\vdots \,b$ означает , что $a$ $a$ делится на $b$ $b$ , или что число $a$ $a$ кратно числу $b$ $b$ .

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

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

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

$a=b\,q+r,$ $a=b\,q+r,$ где $0\leqslant r<|b|$ $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

— целые числа.

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

\quad 0\,\vdots \,a.

\quad 0\,\vdots \,a.

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

\quad a\,\vdots \,1.

\quad a\,\vdots \,1.

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

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

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

,

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

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

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

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

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

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

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

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

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

В системе целых чисел выполняются только первые два из этих трёх свойств; например,

2\,\vdots -2

2\,\vdots -2

и

-2\,\vdots \,2,

-2\,\vdots \,2,

но

2\neq -2

2\neq -2

. То есть отношение делимости целых чисел является только лишь предпорядком .

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

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

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

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

Здесь $\gamma$ $\gamma$ — постоянная Эйлера — Маскерони , а для $\theta$ $\theta$ Дирихле получил значение ${\frac {1}{2}}.$ ${\frac {1}{2}}.$ Этот результат многократно улучшался, и в настоящее время наилучший известный результат $\theta ={\frac {131}{416}}$ $\theta ={\frac {131}{416}}$ (получен в 2003 году Хаксли). Однако наименьшее значение $\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}{\pi }}\prod _{p}\left({\frac {p^{3/2}}{\sqrt {p-1}}}\ln \left(1+{\frac {1}{p}}\right)\right)\approx 0{,}7138067$ $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$ .

Обобщения

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

См. также

Ссылки

Примечания

, с. 7.
А. А. Бухштаб. . — М. : Просвещение, 1966. 13 января 2012 года.
И. М. Виноградов. Аналитическая теория чисел // Математическая энциклопедия. — М.: Советская энциклопедия (рус.) . — 1977—1985.
Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
В. И Арнольд. Динамика, статистика и проективная геометрия полей Галуа. — М. : МЦНМО, 2005. — С. 70. — 72 с.

Литература

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

[_e5ef7abba4c89bda-1] , с. 7.

[2] А. А. Бухштаб. . — М. : Просвещение, 1966. 13 января 2012 года.

[3] И. М. Виноградов. Аналитическая теория чисел // Математическая энциклопедия. — М.: Советская энциклопедия (рус.) . — 1977—1985.

[4] Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .

[Arnold-5] В. И Арнольд. Динамика, статистика и проективная геометрия полей Галуа. — М. : МЦНМО, 2005. — С. 70. — 72 с.