Подільність

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Подільність — фундаментальна властивість натуральних та цілих чисел. Число a ділиться на b, відповідно, число b є дільником a, якщо частка \frac{a}{b} — ціле число. Будь-яке натуральне число ділиться на одиницю і на себе. Якщо дане число не має інших дільників, то таке число називається простим, в іншому разі — складеним. Властивості простих чисел і питання подільності займали думки науковців і філософів протягом двох з половиною тисячолітть, принаймні з часів Піфагора, і ще досі не вичерпали себе. Завдяки розвитку криптографії і розповсюдженню заснованних на теорії чисел алгоритмів, пов'язані з перевіркою на простоту і факторизацією дослідження знаходяться на передовому краю математики.

Історія[ред.ред. код]

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

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

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

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

Пов'язані визначення[ред.ред. код]

  • Одиниця має рівно один дільник і не є ні простою, ні складеною.
  • У кожного натурального числа, більшого за одиницю, є хоча б один простий дільник.
  • Власним дільником числа називається всякий його дільник, відмінний від самого числа. У простих чисел існує рівно один власний дільник — одиниця.
  • Незалежно від подільності цілого числа a на ціле число b\ne 0, число a завжди можна розділити на b із залишком, тобто представити у вигляді:
    a=b\,q + r, де 0 \leqslant r < |b|.
У цьому співвідношенні число q називається неповною часткою, а число r — остачею від ділення a на b. Як чаcтка, так і залишок визначаються однозначно.
Число a ділиться без остачі на b тоді та лише тоді, коли залишок від ділення a на b дорівнює нулю.
  • Всяке число, яке ділить як a, так і b, називаєтьcя їх cпільним дільником; максимале з таких чисел називаєтьcя найбільшим спільним дільником. У будь-якої пари цілих чисел є принаймні два загальних подільника: +1 та -1. Якщо інших спільних дільників немає, то ці числа називають взаємно простими числами.
  • Два цілих числа a і b називають одноподільніними на ціле число m, якщо або і a, і b ділиться на m, або ні a, ні b не діляться на нього.

Позначення[ред.ред. код]

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

Властивості[ред.ред. код]

Зауваження: у всіх формулах цього розділу передбачається, що a,\,b,\,c — цілі числа.
  • Будь-яке ціле число є дільником нуля, при цьому чаcтка дорівнює нулю :
\quad0\,\vdots\,a.
  • Будь-яке ціле число ділиться на одиницю:
\quad a\,\vdots\,1.
  • На нуль ділиться лише нуль:
a\,\vdots\,0\quad\Rightarrow\quad a = 0,

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

  • Одиниця ділиться націло лише на одиницю:
1\,\vdots\,a\quad\Rightarrow\quad a = \pm 1.
  • Для будь-якого цілого числа a \ne 0 знайдеться таке ціле число b \ne a, для якого b\,\vdots\,a.
  • Якщо a\,\vdots\,b та \left|b\right| > \left|a\right|, то a\,=\,0. Звідси ж випливає, що якщо a\,\vdots\,b і a \ne 0 то \left|a\right| \geqslant \left|b\right|.
  • Для того щоб a\,\vdots\,b необхідно і достатньо, щоб \left|a\right| \vdots \left|b\right|.
  • Якщо a_1\,\vdots\,b,\,a_2\,\vdots\,b,\,\dots,\,a_n\,\vdots\,b, то \left( a_1 + a_2 + \dots + a_n \right)\,\vdots\,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), є мультиплікативною функцією, для неї є вірною асимптотична Формула Діріхле[ru]:

\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}).[1][2][3]

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

Узагальнення[ред.ред. код]

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. А. А. Бухштаб Теорія чисел. — М.: Просвіта, 1966.
  2. Аналітична теорія чисел
  3. Weisstein, Eric W. Dirichlet Divisor Problem(англ.) на сайті Wolfram MathWorld.
  4. В. І Арнольд Динаміка, статистика та проективна геометрія полів Галуа. — М.: МЦНМО, 2005. — С. 70.