Делимость

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

Определение

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




a


{\displaystyle a}

и целого числа




b


{\displaystyle b}

существует такое целое число




q


{\displaystyle q}

, что




b
q
=
a
,


{\displaystyle bq=a,}

то говорят, что число




a


{\displaystyle a}

делится нацело на




b


{\displaystyle b}

или что




b


{\displaystyle b}

делит




a
.


{\displaystyle a.}

При этом число




b


{\displaystyle b}

называется делителем числа




a


{\displaystyle a}

, делимое




a


{\displaystyle a}

будет кратным числа




b


{\displaystyle b}

, а число




q


{\displaystyle q}

называется частным от деления




a


{\displaystyle a}

на




b


{\displaystyle b}

.

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

Обозначения





  • a



    b


    {\displaystyle a\,\vdots \,b}

    означает, что




    a


    {\displaystyle a}

    делится на




    b


    {\displaystyle b}

    , или что число




    a


    {\displaystyle a}

    кратно числу




    b


    {\displaystyle b}

    .





  • b

    a


    {\displaystyle b\mid a}

    означает, что




    b


    {\displaystyle b}

    делит




    a


    {\displaystyle a}

    , или, что то же самое:




    b


    {\displaystyle b}

     — делитель




    a


    {\displaystyle a}

    .

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

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



    1


    {\displaystyle 1}

    , есть хотя бы один простой делитель.

  • Собственным делителем числа называется всякий его делитель, отличный от самого числа. У простых чисел существует ровно один собственный делитель — единица.
  • Вне зависимости от делимости целого числа



    a


    {\displaystyle a}

    на целое число




    b




    {\displaystyle b\neq 0}

    , число




    a


    {\displaystyle a}

    всегда можно разделить на




    b


    {\displaystyle b}

    с остатком, то есть представить в виде:




    a
    =
    b

    q
    +
    r
    ,


    {\displaystyle a=b\,q+r,}

    где






    r
    <

    |

    b

    |



    {\displaystyle 0\leqslant r<|b|}

    .

В этом соотношении число




q


{\displaystyle q}

называется неполным частным, а число




r


{\displaystyle r}

 — остатком от деления




a


{\displaystyle a}

на




b


{\displaystyle b}

. Как частное, так и остаток определяются однозначно.

Число




a


{\displaystyle a}

делится нацело на




b


{\displaystyle b}

тогда и только тогда, когда остаток от деления




a


{\displaystyle a}

на




b


{\displaystyle b}

равен нулю.

  • Всякое число, делящее как



    a


    {\displaystyle a}

    , так и




    b


    {\displaystyle b}

    , называется их общим делителем; максимальное из таких чисел называется наибольшим общим делителем. У всякой пары целых чисел есть по крайней мере два общих делителя:




    +
    1


    {\displaystyle +1}

    и





    1


    {\displaystyle -1}

    . Если других общих делителей нет, то эти числа называются взаимно простыми.

  • Два целых числа



    a


    {\displaystyle a}

    и




    b


    {\displaystyle b}

    называются равноделимыми на целое число




    m


    {\displaystyle m}

    , если либо и




    a


    {\displaystyle a}

    , и




    b


    {\displaystyle b}

    делится на




    m


    {\displaystyle m}

    , либо ни




    a


    {\displaystyle a}

    , ни




    b


    {\displaystyle b}

    не делится на него.

  • Говорят, что число



    a


    {\displaystyle a}

    кратно числу




    b


    {\displaystyle b}

    , если




    a


    {\displaystyle a}

    делится на




    b


    {\displaystyle b}

    без остатка. Если число




    c


    {\displaystyle c}

    делится без остатка на числа




    a


    {\displaystyle a}

    и




    b


    {\displaystyle b}

    , то оно называется их общим кратным. Наименьшее такое натуральное




    c


    {\displaystyle c}

    называется наименьшим общим кратным чисел




    a


    {\displaystyle a}

    и




    b


    {\displaystyle b}

    .

Свойства

Замечание: во всех формулах этого раздела предполагается, что




a
,

b
,

c


{\displaystyle a,\,b,\,c}

 — целые числа.

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









a
.


{\displaystyle \quad 0\,\vdots \,a.}

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





a



1.


{\displaystyle \quad a\,\vdots \,1.}

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




a







a
=



{\displaystyle a\,\vdots \,0\quad \Rightarrow \quad a=0}

,

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

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




1



a



a
=
±
1.


{\displaystyle 1\,\vdots \,a\quad \Rightarrow \quad a=\pm 1.}

  • Для любого целого числа



    a




    {\displaystyle a\neq 0}

    найдётся такое целое число




    b

    a
    ,


    {\displaystyle b\neq a,}

    для которого




    b



    a
    .


    {\displaystyle b\,\vdots \,a.}

  • Если



    a



    b


    {\displaystyle a\,\vdots \,b}

    и





    |
    b
    |

    >

    |
    a
    |

    ,


    {\displaystyle \left|b\right|>\left|a\right|,}

    то




    a

    =

    0.


    {\displaystyle a\,=\,0.}

    Отсюда же следует, что если




    a



    b


    {\displaystyle a\,\vdots \,b}

    и




    a




    {\displaystyle a\neq 0}

    то





    |
    a
    |



    |
    b
    |

    .


    {\displaystyle \left|a\right|\geqslant \left|b\right|.}

  • Для того чтобы



    a



    b


    {\displaystyle a\,\vdots \,b}

    необходимо и достаточно, чтобы





    |
    a
    |



    |
    b
    |

    .


    {\displaystyle \left|a\right|\vdots \left|b\right|.}

  • Если




    a

    1





    b
    ,


    a

    2





    b
    ,


    ,


    a

    n





    b
    ,


    {\displaystyle a_{1}\,\vdots \,b,\,a_{2}\,\vdots \,b,\,\dots ,\,a_{n}\,\vdots \,b,}

    то





    (


    a

    1


    +

    a

    2


    +

    +

    a

    n



    )




    b
    .


    {\displaystyle \left(a_{1}+a_{2}+\dots +a_{n}\right)\,\vdots \,b.}

  • Отношение делимости натуральных чисел является отношением нестрогого порядка и, в частности, оно:
    • рефлексивно, то есть любое целое число делится на себя же:




      a



      a
      .


      {\displaystyle \quad a\,\vdots \,a.}

    • транзитивно, то есть если



      a



      b


      {\displaystyle a\,\vdots \,b}

      и




      b



      c
      ,


      {\displaystyle b\,\vdots \,c,}

      то




      a



      c
      .


      {\displaystyle a\,\vdots \,c.}

    • антисимметрично, то есть если



      a



      b


      {\displaystyle a\,\vdots \,b}

      и




      b



      a
      ,


      {\displaystyle b\,\vdots \,a,}

      то




      a

      =

      b
      .


      {\displaystyle a\,=\,b.}

В системе целых чисел выполняются только первые два из этих трёх свойств; например,




2




2


{\displaystyle 2\,\vdots \,-2}

и





2



2
,


{\displaystyle -2\,\vdots \,2,}

но




2


2.


{\displaystyle 2\neq -2.}

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

Число положительных делителей натурального числа




n
,


{\displaystyle n,}

обычно обозначаемое




τ
(
n
)
,


{\displaystyle \tau (n),}

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







n
=
1


N


τ
(
n
)
=
N
ln

N
+
(
2

γ

1
)
N
+
O

(

N

θ


)

.


{\displaystyle \sum _{n=1}^{N}\tau (n)=N\ln N+(2\,\gamma -1)N+O\left(N^{\theta }\right).}

Здесь




γ


{\displaystyle \gamma }

 — постоянная Эйлера — Маскерони, а для




θ


{\displaystyle \theta }

Дирихле получил значение






1
2


.


{\displaystyle {\frac {1}{2}}.}

Этот результат многократно улучшался, и в настоящее время наилучший известный результат




θ
=


131
416




{\displaystyle \theta ={\frac {131}{416}}}

(получен в 2003 году Хаксли). Однако, наименьшее значение




θ


{\displaystyle \theta }

, при котором эта формула останется верной, неизвестен (доказано, что он не меньше, чем






1
4




{\displaystyle {\frac {1}{4}}}

).

При этом средний делитель большого числа n в среднем растёт как








c

1


n


ln

n





{\displaystyle {\frac {c_{1}n}{\sqrt {\ln n}}}}

, что было обнаружено А. Карацубой. По компьютерным оценкам М. Королёва





c

1


=


1
π





p



(




p

3

/

2



p

1



ln


(

1
+


1
p



)


)


0,713
8067


{\displaystyle 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}

.

Обобщения

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

См. также

  • Кратность
  • Деление (математика)
  • Деление с остатком
  • Признаки делимости
  • Модульная арифметика
  • Конгруэнтность (алгебра)
  • Сравнение по модулю
  • Кольцо (математика)
  • Факторизация

Ссылки

  • Видео о делимости

Примечания

Литература

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


Поделиться ссылкой:

Смотреть:
СУ-85А