Делимость

Статья на основе материалов из Википедии

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

Определение

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

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

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

Обозначения

  • `a\,\vdots\, b` означает, что `a` делится на `b` , или что число `a` кратно числу `b` .
  • `b\mid a` или `b\setminus a` означает, что `b` делит `a` , или, что то же самое `b`  — делитель `a` .

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

  • У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
  • У каждого натурального числа, большего 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]

При этом средний делитель большого числа n в среднем растёт как `\frac{c_1 n}{\sqrt{\ln n}}` , что было обнаружено А. Карацубой.[3]. По компьютерным оценкам М. Королёва `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 — http://eqworld.ipmnet.ru/ru/library/books/Buhshtab1966ru.djvu
  2. Аналитическая теория чисел
  3. В. И Арнольд Динамика, статистика и проективная геометрия полей Галуа — М. : МЦНМО, 2005 — 72 — 70

Литература

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

I am not robot