Делимость

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

Определение

править

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

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

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

Обозначения

править
  •   означает[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 с.

Литература

править