Подільність

Подільність — властивість натуральних та цілих чисел. Число ${\displaystyle a}$ ділиться на ${\displaystyle b}$, (відповідно, число ${\displaystyle b}$ є дільником ${\displaystyle a),}$ якщо частка ${\displaystyle {\frac {a}{b}}}$ — ціле число

Будь-яке натуральне число ділиться на одиницю і на себе. Якщо число не має інших дільників, то таке число називається простим, в іншому разі — складеним.

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

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

Подільність чисел, загальніших ніж цілі, було ретельно досліджено у 19 ст., починаючи з роботи Гауса про властивості гаусових цілих чисел, комплексних чисел вигляду ${\displaystyle a+bi}$, де ${\displaystyle a,b\in \mathbb {Z} }$ — це звичайні цілі числа, а ${\displaystyle i={\sqrt {-1}}}$ — це уявна одиниця. Гаус відкрив аналог алгоритму Евкліда і в такий спосіб довів однозначність факторизації гаусових цілих чисел. Чимало із спроб доведення великої теореми Ферма спиралося на однозначність факторизації алгебраїчних цілих чисел вигляду

${\displaystyle a_{0}+a_{1}\zeta +\ldots +a_{n-1}\zeta ^{n-1},}$

де ${\displaystyle \zeta }$ — це примітивний корінь з одиниці степені ${\displaystyle n,\zeta ^{n}=1}$, a ${\displaystyle a_{0},a_{1},\ldots ,a_{n-1}\in \mathbb {Z} }$ — цілі числа. Однак виявилося, що у випадку загального ${\displaystyle n}$ такі числа поводяться набагато складніше, ніж звичайні цілі, зокрема, для них не виконується однозначність факторизації на прості множники. У роботах Куммера, Кронекера і Дедекінда з теорії подільності алгебраїчних цілих чисел з'явились фундаментальні для сучасної математики поняття теорії кілець, на яких, разом з введеним Галуа поняттям групи, ґрунтується сучасна абстрактна алгебра.

• Одиниця має рівно один дільник і не є ні простою, ні складеною.
• У кожного натурального числа, більшого за одиницю, є хоча б один простий дільник.
• Власним дільником числа називається всякий його дільник, відмінний від самого числа. У простих чисел існує лише один власний дільник — одиниця.
• Незалежно від подільності цілого числа ${\displaystyle a}$ на ціле число ${\displaystyle b\neq 0}$, число a завжди можна розділити на b із залишком, тобто представити у вигляді:

  ${\displaystyle a=b\,q+r,}$ де ${\displaystyle 0\leqslant r<|b|}$.

У цьому співвідношенні число ${\displaystyle q}$ називається неповною часткою, а число r — остачею від ділення ${\displaystyle a}$ на ${\displaystyle b}$. Як частка, так і остача визначаються однозначно.

Число a ділиться без остачі на b тоді та лише тоді, коли залишок від ділення a на b дорівнює нулю.

• Всяке число, яке ділить як ${\displaystyle a}$, так і ${\displaystyle b}$, називається їх спільним дільником; максимальне з таких чисел називається найбільшим спільним дільником. У будь-якої пари цілих чисел є принаймні два загальних подільника: +1 та −1. Якщо інших спільних дільників немає, то ці числа називають взаємно простими числами.
• Два цілих числа ${\displaystyle a}$ і ${\displaystyle b}$ називають одноподільними на ціле число ${\displaystyle m}$, якщо або і ${\displaystyle a}$, і ${\displaystyle b}$ ділиться на ${\displaystyle m}$, або ні ${\displaystyle a}$, ні ${\displaystyle b}$ не діляться на нього.

• ${\displaystyle a\,\vdots \,b}$ означає, що ${\displaystyle a}$ ділиться на ${\displaystyle b}$, або що число ${\displaystyle a}$ кратне числу ${\displaystyle b}$.

• ${\displaystyle b\mid a}$ або ${\displaystyle b\setminus a}$ означає, що ${\displaystyle b}$ ділить ${\displaystyle a}$, або, що теж саме: ${\displaystyle b}$ — дільник ${\displaystyle a}$.

Зауваження: у всіх формулах цього розділу передбачається, що ${\displaystyle a,\,b,\,c}$ — цілі числа.

• Будь-яке ціле число є дільником нуля, при цьому частка дорівнює нулю:

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

• Будь-яке ціле число ділиться на одиницю:

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

• На нуль ділиться лише нуль:

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

причому частка в цьому випадку не визначена.

• Одиниця ділиться націло лише на одиницю:

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

• Для будь-якого цілого числа ${\displaystyle a\neq 0}$ знайдеться таке ціле число ${\displaystyle b\neq a,}$ для якого ${\displaystyle b\,\vdots \,a.}$

• Якщо ${\displaystyle a\,\vdots \,b}$ та ${\displaystyle \left|b\right|>\left|a\right|,}$ то ${\displaystyle a\,=\,0.}$ Звідси ж випливає, що якщо ${\displaystyle a\,\vdots \,b}$ і ${\displaystyle a\neq 0}$ то ${\displaystyle \left|a\right|\geqslant \left|b\right|.}$

• Для того щоб ${\displaystyle a\,\vdots \,b}$ необхідно і достатньо, щоб ${\displaystyle \left|a\right|\vdots \left|b\right|.}$

• Якщо ${\displaystyle a_{1}\,\vdots \,b,\,a_{2}\,\vdots \,b,\,\dots ,\,a_{n}\,\vdots \,b,}$ то ${\displaystyle \left(a_{1}+a_{2}+\dots +a_{n}\right)\,\vdots \,b.}$

• Властивість подільності є відношенням не суворого порядку і, зокрема, воно:
  • рефлексивне, тобто будь-яке ціле число ділиться само на себе: ${\displaystyle \quad a\,\vdots \,a.}$
  • транзитивне, тобто якщо ${\displaystyle a\,\vdots \,b}$ і ${\displaystyle b\,\vdots \,c,}$ то ${\displaystyle a\,\vdots \,c.}$
  • антисиметричне, тобто якщо ${\displaystyle a\,\vdots \,b}$ і ${\displaystyle b\,\vdots \,a,}$ то або ${\displaystyle a\,=\,b,}$ або ${\displaystyle a\,=\,-b.}$

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

Число додатних дільників натурального числа ${\displaystyle n}$ зазвичай позначають ${\displaystyle \tau (n)}$, є мультиплікативною функцією, для неї є вірною асимптотична формула Діріхле:

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

в якій ${\displaystyle \gamma }$ — стала Ейлера—Маскероні, а для ${\displaystyle \theta }$ Діріхле отримав значення ${\displaystyle {\frac {1}{2}}.}$ Цей результат багаторазово поліпшувався, і останнім часом найкращий відомий результат ${\displaystyle \theta ={\frac {131}{416}}}$ (отримано у 2003 р. Хакслі). Однак, найменше значення ${\displaystyle \theta }$, при якому ця формула залишиться вірною, невідоме (доведено, що воно не менше, ніж ${\displaystyle {\frac {1}{4}}}$).^[1][2][3]

При цьому середній дільник великого числа n в середньому росте як ${\displaystyle {\frac {c_{1}n}{\sqrt {\ln n}}}}$, що було виявлено А. Карацубою.^[4]. З комп'ютерних оцінок М. Корольова${\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}$.

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

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

• Дрозд Ю. А. (1997). Теорія алгебричних чисел (PDF). Київ: РВЦ “Київський університет„. с. 82. ISBN 966-594-019-8. (укр.)