Общий делитель - NiNa.Az

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

Определение

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

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

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

Обозначения

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

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

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

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

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

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

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

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

Свойства

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

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

${\displaystyle 0\,\vdots \,a,}$

и частное (при ${\displaystyle a\neq 0}$) равно нулю.

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

${\displaystyle a\,\vdots \,1.}$

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

${\displaystyle a\,\vdots \,0\quad \Rightarrow \quad a=0}$,

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

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

${\displaystyle 1\,\vdots \,a\quad \Rightarrow \quad a=\pm 1.}$

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

См. также

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

Ссылки

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

Примечания

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

Литература

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