Page 41 - 4570

40

а  0 буде власним тоді і лише тоді, коли він задовольняє нерівності 1 < |b| <
|а|.
Число, яке має власні дільники, називається складеним,. Якщо число не є
складеним і відмінне від ±1, то воно називається простим. Причина, чому
числа ±1 не відносять ні до простих, ні до складених, стане зрозумілою дещо
пізніше. Очевидно, що відмінне від ±1 число р буде простим тоді і лише тоді,
коли для будь-якого розкладу р у добуток двох множників р = ab один із них
дорівнює ±1.
Твердження. Кожне відмінне від ±1 ціле число ділиться на деяке просте
число.
Доведення. Скористаємось індукцією за модулем числа n. Для чисел 0 і ±2
твердження очевидне. Розглянемо довільне n, |n| > 2. і припустимо. що для всіх
чисел, модуль яких менший від |n|, твердження вже доведене. Якщо n – просте,
то простим дільником числа n буде воно саме. Якщо ж n – складене, то воно
має власний натуральний дільник m. Оскільки 1 < m < |n|, то, за припущенням
індукції, m має простий дільник р. Із транзитивності відношення подільності
тепер випливає, що р | n.
Коли ми говоримо про добуток m 1  m 2  ... m k k множників, то до розгляду
включено і випадок k = 1. Більше того, число 1 зручно вважати добутком
нульової кількості множників. Це спрощує формулювання багатьох тверджень.
Теорема 1.14. Кожне натуральне число розкладається в добуток простих
чисел.
Доведення. Для числа 1 твердження теореми випливає з нашої
домовленості. Розглянемо тепер довільне n > 1 і припустимо, що для всіх чисел,
менших від n, теорему вже доведено. Якщо n – просте, то шуканий розклад для
n складається з одного множника n. Якщо ж n складене, то за попереднім
твердженням n можна розкласти в добуток п = р 1m, де р 1 – просте і m < n. За
припущенням індукції для m існує розклад m = p 2p 3 … p k у добуток простих
чисел. Тоді n = p 2p 3 … p k буде шуканим розкладом для числа n.
Теорема 1.15 (Евклід). Існує нескінченно багато простих чисел.
Доведення. Доведення цієї теореми є класичним зразком доведення від
супротивного. Справді, припустимо, що множина простих чисел скінченна, і
нехай p 1, p 2, …, p k їх повний список. Розглянемо число n = p 1p 2 … p k + 1. За
доведеним твердженням n має простий дільник р. Цей дільник не може
збігатися з жодним із чисел р 1, ..., р k, бо n на ці числа не ділиться. Отже, просте
число р не трапляється в списку р 1, ..., р k, що суперечить припущенню про його
повноту. Теорему доведено.
Приклад 1.56. Знайти всі такі натуральні прості, числа р, для яких кожне
із чисел, р + 4 і р + 14 також буде простим.
Розв ’язання. Розглянемо остачі від ділення цих чисел на 3. Із рівностей р
+ 4 = 3 + (р + 1) і р + 14 = 12 + (р + 2) випливає, що числа р, р + 4 і р + 14 при
діленні на 3 дають різні остачі. Отже, одна із цих остач дорівнює 0, тобто одне
із цих чисел ділиться на 3. Але числа р + 4 і р + 14 прості і більші, ніж 3. тому
вони на 3 не діляться. Звідси 3 | р і р = 3, бо р просте. Оскільки числа 3 + 4 = 7 і
3 + 14 = 17 прості, то р = 3 справді задовольняє умову задачі.