Page 43 - 4570

42

З іншого боку, зустрічаються досить довгі проміжки натуральних чисел,
які не містять жодного простого. Так, зовсім нема простих серед 13 чисел із
проміжку [114; 126] і серед 33 чисел із проміжку [1328; 1360]. Також, існують
як завгодно довгі проміжки натуральних чисел, що не містять жодного
простого.

ЛЕКЦІЯ 10. ОСНОВНА ТЕОРЕМА АРИФМЕТИКИ І КОНГРУЕНЦІЇ

1. Найбільший спільний дільник і найменше спільне кратне

Означення 1.40. Число d називають найбільшим спільним дільником
чисел а і b, якщо воно задовольняє 2 умови:
a) d | a і d | b;
b) якщо c | a і c | b, тo c | d.
Найбільший спільний дільник чисел а і b позначають НСД(а, b) або (а, b).
У словосполученні «найбільший спільний дільник» слово «найбільший»
означає не найбільший за величиною, а те, що цей дільник є кратним будь-
якого іншого спільного дільника чисел а і b. Наприклад, спільними дільниками
чисел 12 і 18 будуть ±1, ±2, ±3, ±6, а найбільшими спільними дільниками цих
чисел є 6 і -6 (зауважимо, що за величиною -6 є найменшим серед спільних
дільників чисел 12 і 18).
Означення найбільшого спільного дільника двох чисел з використанням
лише поняття подільності є зручним для теоретичних міркувань. До того ж
воно легко переноситься па інші математичні структури, де можна говорити
про подільність, але де не можна змістовно визначити величину елементів.
Однак тепер зовсім не очевидно, що визначений таким чином найбільший
спільний дільник існує для довільної пари чисел а і b. Ми доведемо його
існування методом, який, попри свою прозорість, є вихідною точкою деяких
глибоких понять сучасної алгебри.
Теорема 1.16 (про існування найбільшого спільного дільника). Для, будь-
яких цілих чисел, а і b існує їх найбільший спільний дільник (а, b).
Доведення. Безпосередньо перевіряється, що 0 = (0, 0). Тому далі можна
вважати, що серед чисел а і b є ненульове. Розглянемо множину І = {mа + nb :
m, n  Z}. Вона, зокрема, містить числа а = 1а + 0b, b = 0а + 1b. і разом із
числом mа + nb містить протилежне число (-m)а + (-n)b. Тому серед елементів
множини І є натуральні числа. Позначимо через d найменше з них і доведемо,
що d є найбільшим спільним дільником чисел а і b. Справді, нехай d = m 0а +
n 0b. Припустимо, що а не ділить b. Тоді розділимо а на d з остачею: а = qd + r, 0
< r < d. І матимемо: r = а - qd = (1 - qm 0)a + (-qn 0)b  І. що суперечить вибору
числа d.
Аналогічно доводиться, що d | b. Отже, першу умову з означення
найбільшого спільного дільника число d задовольняє.
Припустимо тепер, що с | а і с | b. Тоді існують розклади а = са 0 і b = сb 0,
звідки d = m 0 ca 0 + n 0 cb 0 = c(m 0a 0 + n 0b 0). Таким чином, c | d. □