Делимость

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

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

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

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

Обозначения[править | править вики-текст]

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

Связанные определения[править | править вики-текст]

  • У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
  • У каждого натурального числа, большего 1, есть хотя бы один простой делитель.
  • Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
  • Вне зависимости от делимости целого числа a на целое число b\ne 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,\,c — целые числа.
  • Любое целое число является делителем нуля, и частное равно нулю :
\quad0\,\vdots\,a.
  • Любое целое число делится на единицу:
\quad a\,\vdots\,1.
  • На ноль делится только ноль:
a\,\vdots\,0\quad\Rightarrow\quad a = 0,

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

  • Единица делится только на единицу:
1\,\vdots\,a\quad\Rightarrow\quad a = \pm 1.
  • Для любого целого числа a \ne 0 найдётся такое целое число b \ne a, для которого b\,\vdots\,a.
  • Если a\,\vdots\,b и \left|b\right| > \left|a\right|, то a\,=\,0. Отсюда же следует, что если a\,\vdots\,b и a \ne 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.

Число делителей[править | править вики-текст]

Число положительных делителей натурального числа 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}).[1][2][3]

При этом средний делитель большого числа n в среднем растёт как \frac{c_1 n}{\sqrt{\ln n}}, что было обнаружено А. Карацубой.[4]. По компьютерным оценкам М. Королёва 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. А. А. Бухштаб Теория чисел. — М.: Просвещение, 1966.
  2. Аналитическая теория чисел
  3. Weisstein, Eric W. Dirichlet Divisor Problem (англ.) на сайте Wolfram MathWorld.
  4. В. И Арнольд Динамика, статистика и проективная геометрия полей Галуа. — М.: МЦНМО, 2005. — С. 70. — 72 с.

Литература[править | править вики-текст]