Подільність

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

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

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

Історія

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

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

$a_0+a_1\zeta +\dots +a_{n-1}{\zeta }^{n-1},$

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

Пов'язані визначення

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

  $a=bq+r,$ де $0⩽r<|b|$.

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

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

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

Позначення

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

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

Властивості

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

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

$0⋮a.$

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

$a⋮1.$

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

$a⋮0\Rightarrow a=0$,

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

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

$1⋮a\Rightarrow a=\pm 1.$

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

• Якщо $a⋮b$ та $\left|b\right|>\left|a\right|,$ то $a=0.$ Звідси ж випливає, що якщо $a⋮b$ і $a\ne 0$ то $\left|a\right|⩾\left|b\right|.$

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

• Якщо $a_1⋮b,a_2⋮b,\dots ,a_n⋮b,$ то $(a_1+a_2+\dots +a_n)⋮b.$

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

Приклади

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

350пікселів

Кількість дільників

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

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

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

При цьому середній дільник великого числа n в середньому росте як $\frac{c_{1}n}{\sqrt{\ln n}}$, що було виявлено А. Карацубою.. З комп'ютерних оцінок М. Корольова$c_1=\frac{1}{\pi }\prod _p(\frac{p^{3/2}}{\sqrt{p-1}}\ln (1+\frac{1}{p}))\approx 0,7138067$.

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

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

Див. також

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

Джерела

• Шаблон:Дрозд.Теорія алгебричних чисел