ru.wikipedia.org

Делимость — Википедия

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

Если для некоторого целого числа {\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 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 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}}}).[2][3][4]

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