Processing math: 100%

Делимость

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

Определение


 Если для некоторого целого числа a и целого числа b существует такоецелое число q, что bq=a, то говорят, что число a делитсянацело на b или что b делит a.
 При этом число b называется делителем числа a,делимое a будет кратным числа b, а число qназывается частным от деления a на b.
 Хотя свойство делимости определено на всём множестве целых чисел,обычно рассматривается лишь делимость натуральных чисел. Вчастности, функция количества делителей натурального числа подсчитываетлишь его положительные делители.

Обозначения



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


  • ba или ba означает, что b делит a, или, что то же самое: b — делитель a.

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



  • У каждого натурального числа, большего единицы, имеются по крайней мере два натуральных делителя: единица и само это число. При этом натуральные числа, имеющие ровно два делителя, называются простыми, а имеющие больше двух делителей — составными. Единица имеет ровно один делитель и не является ни простым, ни составным.
  • У каждого натурального числа, большего 1, есть хотя бы один простой делитель.
  • Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
  • Вне зависимости от делимости целого числа a на целое число b0, число a всегда можно разделить на b с остатком, то есть представить в виде:
    a=bq+r, где 0r<|b|.


 В этом соотношении число q называется неполным частным, а числоr — остатком от деления a на b. Как частное, так иостаток определяются однозначно.
 Число a делится нацело на b тогда и только тогда, когдаостаток от деления a на b равен нулю.

  • Всякое число, делящее как a, так и b, называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя: +1 и −1. Если других общих делителей нет, то эти числа называются взаимно простыми.
  • Два целых числа a и b называются равноделимыми на целое число m, если либо и a, и b делится на m, либо ни a, ни b не делится на него.

Свойства



Замечание: во всех формулах этого раздела предполагается, чтоa,b,c — целые числа.

  • Любое целое число является делителем нуля, и частное равно нулю :


0a.

  • Любое целое число делится на единицу:


a1.

  • На ноль делится только ноль:


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

  • Единица делится только на единицу:


1aa=±1.

  • Для любого целого числа a0 найдётся такое целое число ba, для которого ba.


  • Если ab и |b|>|a|, то a=0. Отсюда же следует, что если ab и a0 то |a||b|.


  • Для того чтобы ab необходимо и достаточно, чтобы |a||b|.


  • Если a1b,a2b,,anb, то (a1+a2++an)b.


  • Свойство делимости является отношением нестрогого порядка и, в частности, оно:
    • рефлексивно, то есть любое целое число делится на себя же: aa.
    • транзитивно, то есть если ab и bc, то ac.
    • антисимметрично, то есть если ab и ba, то либо a=b, либо a=b.

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


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

Nn=1τ(n)=NlnN+(2γ1)N+O(Nθ),
 в которой γ — постоянная Эйлера — Маскерони, а для θДирихле получил значение 12. Этот результат многократноулучшался, и в настоящее время наилучший известный результатθ=131416 (получен в 2003 году Хаксли). Однако,наименьшее значение θ, при котором эта формула останется верной,неизвестен (доказано, что он не меньше, чем 14).
 При этом средний делитель большого числа n в среднем растёт какc1nlnn, что было обнаружено А. Карацубой.. Покомпьютерным оценкам М. Королёваc1=1πp(p3/2p1ln(1+1p))0,7138067.

Обобщения


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