Делимость

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

ОпределениеПравить

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

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

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

ОбозначенияПравить

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

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

  • У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
  • У каждого натурального числа, большего  , есть хотя бы один простой делитель.
  • Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
  • Вне зависимости от делимости целого числа   на целое число  , число   всегда можно разделить на   с остатком, то есть представить в виде:
      где  .
В этом соотношении число   называется неполным частным, а число   — остатком от деления   на  . Как частное, так и остаток определяются однозначно.
Число   делится нацело на   тогда и только тогда, когда остаток от деления   на   равен нулю.
  • Всякое число, делящее как  , так и  , называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя:   и  . Если других общих делителей нет, то эти числа называются взаимно простыми.
  • Два целых числа   и   называются равноделимыми на целое число  , если либо и  , и   делится на  , либо ни  , ни   не делится на него.
  • Говорят, что число   кратно числу  , если   делится на   без остатка. Если число   делится без остатка на числа   и  , то оно называется их общим кратным. Наименьшее такое натуральное   называется наименьшим общим кратным чисел   и  .

СвойстваПравить

Замечание: во всех формулах этого раздела предполагается, что   — целые числа.
  • Любое целое число является делителем нуля, и частное равно нулю:
 
  • Любое целое число делится на единицу:
 
  • На ноль делится только ноль:
 ,

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

  • Единица делится только на единицу:
 
  • Для любого целого числа   найдётся такое целое число   для которого  
  • Если   и   то   Отсюда же следует, что если   и   то  
  • Для того чтобы   необходимо и достаточно, чтобы  
  • Если   то  
  • Отношение делимости натуральных чисел является отношением нестрогого порядка и, в частности, оно:
    • рефлексивно, то есть любое целое число делится на себя же:  
    • транзитивно, то есть если   и   то  
    • антисимметрично, то есть если   и   то  
В системе целых чисел выполняются только первые два из этих трёх свойств; например,   и   но  

Число делителейПравить

Основная статья: Число делителей

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

 

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

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

ОбобщенияПравить

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

См. такжеПравить

СсылкиПравить

ПримечанияПравить

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

ЛитератураПравить