Page 46 - 4570

45

де ще можна говорити про розклад у добуток простих елементів, але
однозначності розкладу вже немає. Свого часу відкриття таких структур стало
для математиків великою несподіванкою. Уперше явно сформулював і довів
основну теорему арифметики у 1801 р. Ґаус.
Щоб показати нетривіальність цієї теореми, розглянемо множину 2Z
парних чисел. Як і Z, ця множина замкнена відносно додавання і множення, і в
ній можна виділити прості елементи (назвемо їх парно простими числами), які
не розкладаються в добуток двох парних чисел. Очевидно, що парно-простими
будуть усі числа вигляду 2m. де m – непарне, і тільки такі числа. З основної
теореми арифметики випливає, що кожне парне число n можна записати у
k
вигляді n = 2 m. де k  1 і m – непарне. Тому кожне парне число легко
k
розкладається в добуток парно-простих: 2 m = 22  22m. Але тепер розклад
перестає бути однозначним. Наприклад, 840 можна розкласти в добуток парно
простих чисел п'ятьма суттєво різними способами: 840 = 22210 = 2670 =
21042 = 21430 = 61014.
У розкладі натурального числа n у добуток простих усі множники можна
взяти додатними. Якщо ще впорядкувати ці множники за зростанням, то число
n можна записати у вигляді

1 

n  p  p  p ,
m
2
1 2 m
де p 1, p 2, …, p m – прості числа і p 1 < p 2 < …< p m. Такий розклад числа n
називається канонічним. Основна теорема арифметики гарантує однозначність
канонічного розкладу.
3. Конгруенції

Зафіксуємо натуральне число n  1. Будемо говорити, що цілі числа а і b
конгруентні (або порівняльні) за модулем числа n (і писатимемо а = b (mod
n)), якщо різниця а - b ділиться на n. Наприклад, 27 і -7 порівняльні за модулем
числа 17, бо 27 - (-7) = 34 = 217. Довільні два непарних числа конгруентні за
модулем 2, бо їх різниця є парним числом. Якщо у двох натуральних чисел одна
і та ж остання цифра, то вони конгруентні за модулем 10.
Вирази 27 = -7 (mod 17), 347 = 217 (mod 10), а = b (mod n) та їм подібні
називаються конгруенціями.
Теорема 1.18 (критерій конгруентності). a = b (mod n) тоді й лише тоді,
коли а і b при діленні на n дають однакові остачі.
Доведення. Розділимо а і b на n з остачею: а = q 1n + r 1, b = q 2n + r 2. Тоді а -
b = (q 1 - q 2)n + (r 1 - r 2). Перший доданок у правій частині ділиться на n. Тому
подільність а - b на n рівносильна подільності на n другого доданку r 1 - r 2. Але n
> r 1  r 1 - r 2  -r 2 > -n. Єдине число з проміжку (-n, n), яке ділиться на n, це 0.
Отже, подільність а - b на n рівносильна умові r 1 - r 2 = 0, тобто r 1 = r 2.
Наслідок 1. Якщо остача від ділення а на n дорівнює r, то а  r (mod n).
Із цього наслідку стає зрозумілим позначення a mod n дня остачі від
ділення а на n.
Наслідок 2. Для. фіксованого n відношення конгруентності а  b (mod n)
на множині Z цілих чисел є відношенням, еквівалентності.