Делимость

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

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

Определение

[править | править код]

Если для некоторого целого числа и целого числа существует такое целое число , что то говорят, что число делится нацело на или что делит

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

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

Обозначения

[править | править код]
  • означает[1], что делится на , или что число кратно числу .
  • означает, что делит , или, что то же самое:  — делитель .

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

[править | править код]
  • У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
  • У каждого натурального числа, большего , есть хотя бы один простой делитель.
  • Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
  • Используется также понятие тривиальных делителей: это само число и единица. Таким образом, простое число может быть определено как число, не имеющее никаких делителей, помимо тривиальных.
  • Вне зависимости от делимости целого числа на целое число , число всегда можно разделить на с остатком, то есть представить в виде:
    где .
В этом соотношении число называется неполным частным, а число  — остатком от деления на . Как частное, так и остаток определяются однозначно.
Число делится нацело на тогда и только тогда, когда остаток от деления на равен нулю.
  • Всякое число, делящее как , так и , называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя: и . Если других общих делителей нет, то эти числа называются взаимно простыми.
  • Два целых числа и называются равноделимыми на целое число , если либо и , и делится на , либо ни , ни не делится на него.
  • Говорят, что число кратно числу , если делится на без остатка. Если число делится без остатка на числа и , то оно называется их общим кратным. Наименьшее такое натуральное называется наименьшим общим кратным чисел и .
Замечание: во всех формулах этого раздела предполагается, что  — целые числа.
  • Любое целое число является делителем нуля:
и частное (при ) равно нулю.
  • Любое целое число делится на единицу:
  • На ноль делится только ноль:
,
причём частное в этом случае не определено.
  • Единица делится только на единицу:
  • Для любого целого числа найдётся такое целое число для которого
  • Если и то Отсюда же следует, что если и то
  • Для того чтобы необходимо и достаточно, чтобы
  • Если то
  • Отношение делимости натуральных чисел является отношением нестрогого порядка и, в частности, оно:
    • рефлексивно, то есть любое целое число делится на себя же:
    • транзитивно, то есть если и то
    • антисимметрично, то есть если и то
В системе целых чисел выполняются только первые два из этих трёх свойств; например, и но . То есть отношение делимости целых чисел является только лишь предпорядком.

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

[править | править код]

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

Здесь  — постоянная Эйлера — Маскерони, а для Дирихле получил значение Этот результат многократно улучшался, и в настоящее время наилучший известный результат (получен в 2003 году Хаксли). Однако наименьшее значение , при котором эта формула останется верной, неизвестно (доказано, что оно не меньше, чем ).[2][3][4]

При этом средний делитель большого числа n в среднем растёт как , что было обнаружено А. Карацубой[5]. По компьютерным оценкам М. Королёва .

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

Примечания

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

Литература

[править | править код]