Перегляд вихідного коду сторінки Подільність

'''Подільність'''&nbsp;— властивість [[натуральні числа|натуральних]] та [[цілі числа|цілих]] чисел. Число <math>a</math> '''ділиться''' на <math>b</math>,
(відповідно, число <math>b</math> є '''[[дільник]]ом''' <math>a),</math> якщо [[частка (математика)|частка]] <math>\frac{a}{b}</math>&nbsp;— ціле число

Будь-яке натуральне число ділиться на [[1 (число)|одиницю]] і на себе. Якщо число не має інших дільників, то таке число називається [[просте число|простим]], в іншому разі&nbsp;— [[Складене число|складеним]].

Властивості простих чисел і питання подільності займали думки науковців принаймні з часів [[Піфагор]]а, і досі не вичерпали себе. Завдяки розвитку [[криптографія|криптографії]] і розповсюдженню заснованих на [[Теорія чисел|теорії чисел]] алгоритмів, пов'язані з [[перевірка на простоту|перевіркою на простоту]] і [[факторизація|факторизацією]] дослідження перебувають на передовому краю математики.

== Історія ==
Питання подільності натуральних чисел розглядалися уже в античні часи. [[Евклід]]у належить один з найвідоміших результатів математики, твердження, що не існує найбільшого простого числа, тобто множина простих чисел&nbsp;— нескінченна. Він також навів найперший в історії [[алгоритм]], а саме [[алгоритм Евкліда]] знаходження [[найбільший спільний дільник|найбільшого спільного дільника]] двох натуральних чисел. Цікаво відзначити, що це&nbsp;— не тільки найдавніший, а й один з найефективніших алгоритмів в математиці, який майже не був вдосконалений за більш ніж дві тисячі років, що минули по тому. Але набагато раніше за Евкліда, [[Піфагор]] і [[Піфагореїзм|піфагорійці]] розробили теорію [[досконале число|досконалих]] і [[дружнє число|дружніх]] чисел, які відігравали важливу роль у їх філософській системі.

Подільність чисел, загальніших ніж цілі, було ретельно досліджено у 19 ст., починаючи з роботи [[Гаус Карл Фрідріх|Гауса]] про властивості [[Гаусові числа|гаусових цілих чисел]], [[комплексні числа|комплексних чисел]] вигляду <math>a+bi</math>, де <math>a,b\in\mathbb{Z}</math>&nbsp;— це звичайні цілі числа, а <math>i=\sqrt{-1}</math>&nbsp;— це [[уявна одиниця]]. Гаус відкрив аналог [[Алгоритм Евкліда|алгоритму Евкліда]] і в такий спосіб довів однозначність факторизації гаусових цілих чисел. Чимало із спроб доведення [[велика теорема Ферма|великої теореми Ферма]] спиралося на однозначність факторизації [[алгебраїчні числа|алгебраїчних цілих чисел]] вигляду
: <math>a_0+a_1\zeta+\ldots+a_{n-1}\zeta^{n-1},</math>
де <math>\zeta</math>&nbsp;— це [[примітивний корінь з одиниці]] степені <math>n, \zeta^n=1</math>, a <math>a_0,a_1,\ldots,a_{n-1}\in\mathbb{Z}</math>&nbsp;— цілі числа. Однак виявилося, що у випадку загального <math>n</math> такі числа поводяться набагато складніше, ніж звичайні цілі, зокрема, для них не виконується однозначність факторизації на [[Простий множник|прості множники]]. У роботах [[Ернст Едуард Куммер|Куммера]], [[Кронекер Леопольд|Кронекера]] і [[Дедекінд Юліус Вільгельм Ріхард|Дедекінда]] з теорії подільності алгебраїчних цілих чисел з'явились фундаментальні для сучасної математики поняття [[кільце (в алгебрі)|теорії кілець]], на яких, разом з введеним [[Галуа Еварист|Галуа]] поняттям [[група (математика)|групи]], ґрунтується сучасна [[абстрактна алгебра]].

== Пов'язані визначення ==
* Одиниця має рівно один дільник і не є ні простою, ні складеною.
* У кожного натурального числа, більшого за одиницю, є хоча б один простий дільник.
* Власним дільником числа називається всякий його дільник, відмінний від самого числа. У простих чисел існує лише один власний дільник&nbsp;— одиниця.
* Незалежно від подільності цілого числа <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''&nbsp;— [[Ділення з остачею|''остачею'']] від ділення <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\,\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>&nbsp;— дільник <math>a</math>.

== Властивості ==
: ''Зауваження:'' у всіх формулах цього розділу передбачається, що <math>a,\,b,\,c</math>&nbsp;— цілі числа.

* Будь-яке ціле число є дільником [[0 (число)|нуля]], при цьому частка дорівнює нулю:
: <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>

== Приклади ==
* 7 є дільник 42 оскільки <math>7 \times 6 = 42</math>, тому ми можемо сказати, <math>7 \mid 42</math>. Крім того, можна сказати, що 42 '''ділиться''' на 7, 7 '''ділить''' 42.
* Нетривіальними дільниками 6 є 2, −2, 3, й −3.
* Додатними дільниками 42 є 1, 2, 3, 6, 7, 14, 21, 42.
* <math>5 \mid 0</math>, оскільки <math>5 \times 0 = 0</math>.
* [[Множина|Множиною]] всіх додатних дільників 60 є, <math>A = \{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 \}</math>, [[частково впорядкована множина]], якій відповідає [[діаграма Гассе]]:

[[Файл:Lattice of the divisibility of 60; factors.svg|центр|350пікселів]]

== Кількість дільників ==
{{main|Функція дільників}}

Число додатних дільників натурального числа <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>&nbsp;— [[стала Ейлера—Маскероні]], а для <math>\theta</math> Діріхле отримав значення <math>\frac{1}{2}.</math> Цей результат багаторазово поліпшувався, і останнім часом найкращий відомий результат <math>\theta=\frac{131}{416}</math> (отримано у 2003&nbsp;р. Хакслі). Однак, найменше значення <math>\theta</math>, при якому ця формула залишиться вірною, невідоме (доведено, що воно не менше, ніж <math>\frac{1}{4}</math>).<ref>{{книга |автор=А. А. Бухштаб |назва=Теорія чисел |місце=М. |видавництво=Просвіта |рік=1966 |посилання=http://eqworld.ipmnet.ru/ru/library/books/Buhshtab1966ru.djvu}}</ref><ref>[http://dic.academic.ru/dic.nsf/enc_mathematics/190/Аналітична_теорія_чисел Аналітична теорія чисел]{{Недоступне посилання|date=жовтня 2019 |bot=InternetArchiveBot }}</ref><ref>{{MathWorld|DirichletDivisorProblem|Dirichlet Divisor Problem}}</ref>

При цьому середній дільник великого числа n в середньому росте як <math>\frac{c_1 n}{\sqrt{\ln n}}</math>, що було виявлено А. Карацубою.<ref name="Arnold">{{книга|автор=В. І. Арнольд|назва=Динаміка, статистика та проективна геометрія полів Галуа|місце=М.|видавництво=МЦНМО|рік=2005|сторінки=72|сторінки=70}}</ref>. З комп'ютерних оцінок М. Корольова<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>.

== Узагальнення ==

Поняття подільності узагальнюється на довільні [[кільце (алгебра)|кільця]], наприклад кільце [[многочлен]]ів.

== Див. також ==
* [[Ознака подільності чисел]]
* [[Таблиця дільників]]
* [[Ділення]]
* [[Ділення з остачею]]
* [[Модульна арифметика]]
* [[Кільце (алгебра)]]
* [[Факторизація]]

== Примітки ==
{{примітки}}

== Джерела ==	
* {{Дрозд.Теорія алгебричних чисел}}

{{Числа за подільністю}}

[[Категорія:Теорія чисел]]
[[Категорія:Арифметика]]