Делимость

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

Определение

Если для некоторого целого числа <math>a</math> и целого числа <math>b</math> существует такое целое число <math>q</math>, что <math>bq=a,</math> то говорят, что число <math>a</math> делится нацело на <math>b</math> или что <math>b</math> делит <math>a.</math>

При этом число <math>b</math> называется делителем числа <math>a</math>, делимое <math>a</math> будет кратным числа <math>b</math>, а число q называется частным от деления a на b.

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

Обозначения

• <math>a\,\vdots\, b</math> означает, что <math>a</math> делится на <math>b</math>, или что число <math>a</math> кратно числу <math>b</math>.

• <math>b\mid a</math> или <math>b\setminus a</math> означает, что <math>b</math> делит <math>a</math>, или, что то же самое: <math>b</math> — делитель <math>a</math>.

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

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

  <math>a=b\,q + r,</math> где <math>0 \leqslant r < |b|</math>.

В этом соотношении число <math>q</math> называется неполным частным, а число r — остатком от деления <math>a</math> на <math>b</math>. Как частное, так и остаток определяются однозначно.

Число a делится нацело на b тогда и только тогда, когда остаток от деления a на b равен нулю.

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

Свойства

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

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

<math>\quad0\,\vdots\,a.</math>

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

<math>\quad a\,\vdots\,1.</math>

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

<math>a\,\vdots\,0\quad\Rightarrow\quad a = 0</math>,

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

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

<math>1\,\vdots\,a\quad\Rightarrow\quad a = \pm 1.</math>

• Для любого целого числа <math>a \ne 0</math> найдётся такое целое число <math>b \ne a,</math> для которого <math>b\,\vdots\,a.</math>

• Если <math>a\,\vdots\,b</math> и <math>\left|b\right| > \left|a\right|,</math> то <math>a\,=\,0.</math> Отсюда же следует, что если <math>a\,\vdots\,b</math> и <math>a \ne 0</math> то <math>\left|a\right| \geqslant \left|b\right|.</math>

• Для того чтобы <math>a\,\vdots\,b</math> необходимо и достаточно, чтобы <math>\left|a\right| \vdots \left|b\right|.</math>

• Если <math>a_1\,\vdots\,b,\,a_2\,\vdots\,b,\,\dots,\,a_n\,\vdots\,b,</math> то <math>\left( a_1 + a_2 + \dots + a_n \right)\,\vdots\,b.</math>

• Свойство делимости является отношением нестрогого порядка и, в частности, оно:
  • рефлексивно, то есть любое целое число делится на себя же: <math>\quad a\,\vdots\,a.</math>
  • транзитивно, то есть если <math>a\,\vdots\,b</math> и <math>b\,\vdots\,c,</math> то <math>a\,\vdots\,c.</math>
  • антисимметрично, то есть если <math>a\,\vdots\,b</math> и <math>b\,\vdots\,a,</math> то либо <math>a\,=\,b,</math> либо <math>a\,=\,-b.</math>

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

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

<math>\sum_{n=1}^N\tau(n)=N\ln N+(2\,\gamma-1)N+O\left(N^\theta\right),</math>

в которой <math>\gamma</math> — постоянная Эйлера — Маскерони, а для <math>\theta</math> Дирихле получил значение <math>\frac{1}{2}.</math> Этот результат многократно улучшался, и в настоящее время наилучший известный результат <math>\theta=\frac{131}{416}</math> (получен в 2003 году Хаксли). Однако, наименьшее значение <math>\theta</math>, при котором эта формула останется верной, неизвестен (доказано, что он не меньше, чем <math>\frac{1}{4}</math>).

При этом средний делитель большого числа n в среднем растёт как <math>\frac{c_1 n}{\sqrt{\ln n}}</math>, что было обнаружено А. Карацубой.. По компьютерным оценкам М. Королёва <math>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</math>.

Обобщения

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

См. также

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

Ссылки

• [www.youtube.com/watch?v=SqJG-5qiaJ0&feature=channel_video_title Видео о делимости]

Литература

• Виноградов И. М. [math.ru/lib/book/djvu/vinogradov.djvu Основы теории чисел.] М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
• Воробьев Н. Н. [ilib.mccme.ru/plm/ann/a39.htm Признаки делимости]. — 4-е изд. — М.: Наука, 1988. — Т. 38. — 94 с. — (Популярные лекции по математике). — ISBN 5-02-013731-6.
• Делимость // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 95. — 352 с.

Отрывок, характеризующий Делимость

– Да, да, – подтверждал Пьер, умиленными и грустными глазами глядя на своего друга. Чем светлее представлялась ему судьба князя Андрея, тем мрачнее представлялась своя собственная.


Для женитьбы нужно было согласие отца, и для этого на другой день князь Андрей уехал к отцу.
Отец с наружным спокойствием, но внутренней злобой принял сообщение сына. Он не мог понять того, чтобы кто нибудь хотел изменять жизнь, вносить в нее что нибудь новое, когда жизнь для него уже кончалась. – «Дали бы только дожить так, как я хочу, а потом бы делали, что хотели», говорил себе старик. С сыном однако он употребил ту дипломацию, которую он употреблял в важных случаях. Приняв спокойный тон, он обсудил всё дело.
Во первых, женитьба была не блестящая в отношении родства, богатства и знатности. Во вторых, князь Андрей был не первой молодости и слаб здоровьем (старик особенно налегал на это), а она была очень молода. В третьих, был сын, которого жалко было отдать девчонке. В четвертых, наконец, – сказал отец, насмешливо глядя на сына, – я тебя прошу, отложи дело на год, съезди за границу, полечись, сыщи, как ты и хочешь, немца, для князя Николая, и потом, ежели уж любовь, страсть, упрямство, что хочешь, так велики, тогда женись.
– И это последнее мое слово, знай, последнее… – кончил князь таким тоном, которым показывал, что ничто не заставит его изменить свое решение.
Князь Андрей ясно видел, что старик надеялся, что чувство его или его будущей невесты не выдержит испытания года, или что он сам, старый князь, умрет к этому времени, и решил исполнить волю отца: сделать предложение и отложить свадьбу на год.
Через три недели после своего последнего вечера у Ростовых, князь Андрей вернулся в Петербург.

На другой день после своего объяснения с матерью, Наташа ждала целый день Болконского, но он не приехал. На другой, на третий день было то же самое. Пьер также не приезжал, и Наташа, не зная того, что князь Андрей уехал к отцу, не могла себе объяснить его отсутствия.
Так прошли три недели. Наташа никуда не хотела выезжать и как тень, праздная и унылая, ходила по комнатам, вечером тайно от всех плакала и не являлась по вечерам к матери. Она беспрестанно краснела и раздражалась. Ей казалось, что все знают о ее разочаровании, смеются и жалеют о ней. При всей силе внутреннего горя, это тщеславное горе усиливало ее несчастие.
Однажды она пришла к графине, хотела что то сказать ей, и вдруг заплакала. Слезы ее были слезы обиженного ребенка, который сам не знает, за что он наказан.
Графиня стала успокоивать Наташу. Наташа, вслушивавшаяся сначала в слова матери, вдруг прервала ее:
– Перестаньте, мама, я и не думаю, и не хочу думать! Так, поездил и перестал, и перестал…
Голос ее задрожал, она чуть не заплакала, но оправилась и спокойно продолжала: – И совсем я не хочу выходить замуж. И я его боюсь; я теперь совсем, совсем, успокоилась…
На другой день после этого разговора Наташа надела то старое платье, которое было ей особенно известно за доставляемую им по утрам веселость, и с утра начала тот свой прежний образ жизни, от которого она отстала после бала. Она, напившись чаю, пошла в залу, которую она особенно любила за сильный резонанс, и начала петь свои солфеджи (упражнения пения). Окончив первый урок, она остановилась на середине залы и повторила одну музыкальную фразу, особенно понравившуюся ей. Она прислушалась радостно к той (как будто неожиданной для нее) прелести, с которой эти звуки переливаясь наполнили всю пустоту залы и медленно замерли, и ей вдруг стало весело. «Что об этом думать много и так хорошо», сказала она себе и стала взад и вперед ходить по зале, ступая не простыми шагами по звонкому паркету, но на всяком шагу переступая с каблучка (на ней были новые, любимые башмаки) на носок, и так же радостно, как и к звукам своего голоса прислушиваясь к этому мерному топоту каблучка и поскрипыванью носка. Проходя мимо зеркала, она заглянула в него. – «Вот она я!» как будто говорило выражение ее лица при виде себя. – «Ну, и хорошо. И никого мне не нужно».
Лакей хотел войти, чтобы убрать что то в зале, но она не пустила его, опять затворив за ним дверь, и продолжала свою прогулку. Она возвратилась в это утро опять к своему любимому состоянию любви к себе и восхищения перед собою. – «Что за прелесть эта Наташа!» сказала она опять про себя словами какого то третьего, собирательного, мужского лица. – «Хороша, голос, молода, и никому она не мешает, оставьте только ее в покое». Но сколько бы ни оставляли ее в покое, она уже не могла быть покойна и тотчас же почувствовала это.
В передней отворилась дверь подъезда, кто то спросил: дома ли? и послышались чьи то шаги. Наташа смотрелась в зеркало, но она не видала себя. Она слушала звуки в передней. Когда она увидала себя, лицо ее было бледно. Это был он. Она это верно знала, хотя чуть слышала звук его голоса из затворенных дверей.
Наташа, бледная и испуганная, вбежала в гостиную.
– Мама, Болконский приехал! – сказала она. – Мама, это ужасно, это несносно! – Я не хочу… мучиться! Что же мне делать?…
Еще графиня не успела ответить ей, как князь Андрей с тревожным и серьезным лицом вошел в гостиную. Как только он увидал Наташу, лицо его просияло. Он поцеловал руку графини и Наташи и сел подле дивана.
– Давно уже мы не имели удовольствия… – начала было графиня, но князь Андрей перебил ее, отвечая на ее вопрос и очевидно торопясь сказать то, что ему было нужно.
– Я не был у вас всё это время, потому что был у отца: мне нужно было переговорить с ним о весьма важном деле. Я вчера ночью только вернулся, – сказал он, взглянув на Наташу. – Мне нужно переговорить с вами, графиня, – прибавил он после минутного молчания.
Графиня, тяжело вздохнув, опустила глаза.
– Я к вашим услугам, – проговорила она.
Наташа знала, что ей надо уйти, но она не могла этого сделать: что то сжимало ей горло, и она неучтиво, прямо, открытыми глазами смотрела на князя Андрея.
«Сейчас? Сию минуту!… Нет, это не может быть!» думала она.
Он опять взглянул на нее, и этот взгляд убедил ее в том, что она не ошиблась. – Да, сейчас, сию минуту решалась ее судьба.
– Поди, Наташа, я позову тебя, – сказала графиня шопотом.
Наташа испуганными, умоляющими глазами взглянула на князя Андрея и на мать, и вышла.
– Я приехал, графиня, просить руки вашей дочери, – сказал князь Андрей. Лицо графини вспыхнуло, но она ничего не сказала.