Пункт 6. Прості числа і "основна" теорема арифметики.
Визначення. Число р Î N , р ¹ 1, називається простим, якщо р має лише два додатних дільники: 1 і р. Інші натуральні числа (крім 1) прийнято називати складеними. Число 1 має особливий статус за домовленістю, – воно ні просте, ні складене.
Відзначимо деякі нескладні спостереження, зв'язані з простими числами.
Спостереження 1. Найменший дільник будь-якого числа а Î N , відмінний від 1, є число просте.
Доказ. Нехай с | а , с ¹ 1 і с - найменше з цією властивістю. Якщо існує с1 таке, що с1 | с, то с1 £ с и с1 | а , отже, с1 = с чи с1 = 1.
Спостереження 2. Найменший відмінний від 1 дільник складеного числа а Î N не перевершує Ö a .
Доказ. с | а , с ¹ 1, с - найменше, отже
а = са 1 , а 1 | а , а 1 ³ с , значить аа 1 ³ с2 а 1 , а ³ с2 і с £ Ö a .
Наступне спостереження, віддаючи данину поваги його автору - Евкліду, назвемо теоремою.
Теорема (Евклід). Простих чисел нескінченно багато.
Доказ. Від противного. Ну нехай р 1 , р 2 ,..., р n - усі прості, які тільки є. Розглянемо число а = р 1 р 2 ... р n + 1. Його найменший відмінний від 1 дільник с , будучи простим, не може збігатися з жодним з р 1 , р 2 ,..., р n , тому що інакше с | 1.
Для складання таблиці простих чисел древній грек Ератосфен придумав процедуру, що одержала назву "решето Ератосфена":
2,
3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 ,
13, 14 , 15 , 16 , 17,...
Йдемо по натуральному ряду зліва направо. Підкреслюємо перше непідкреслене і невикреслене число, а з подальшого ряду викреслюємо кратні тільки що підкресленому. І так багато разів. Легко зрозуміти, що підкреслені числа - прості. Якщо згадати спостереження 2, то стає зрозуміло, що коли викреслено всі кратні до простих, менші за р, то ті, що залишилися невикресленими і менші за р 2 - прості. Це значить, що складання таблиці всіх простих чисел менших за N закінчено відразу, як тільки викреслені всі кратні до простих, менших Ö a .
Для чисел, що зростають закономірно, наприклад для квадратів або степенів двійки, було б, звичайно, безглуздо розшукувати екземпляр, що перевершує усі відомі. Для простих же чисел, навпаки, потрібні величезні зусилля, щоб саме це і зробити. Наприклад, у 1876 році француз Люка довів, що число 2127 -1 просте, і 75 років воно залишалося найбільшим з відомих простих чисел:
2 127 -1 = 170141183460469231731687303715884105727.
В даний час складені таблиці всіх простих чисел, що не перевершують 50 мільйонів, далі відомі тільки окремі їхні представники. Читачів завжди залучає гігантизм, тому вкажу тут два найбільших відомих на сьогоднішній момент прості числа: 2 44497 - 1 і 2 86243 - 1. Останнє число записане поки в книгу рекордів Гіннеса, у ньому 25962 десяткових знака. Знайдено воно було, звичайно, у рекламних цілях - демонстрація фірмою IBM можливостей чергового суперкомп'ютера, якому для перевірки цього числа на простоту за допомогою спеціальних витончених тестів (придатних тільки для чисел виду 2 n- 1) знадобився тиждень роботи і купа грошей.
Найважливішою і загальновідомою у цьому пункті є наступна теорема (можна сказати, що вона затверджує факторіальність кільця Z). Ця теорема зветься "Основною теореми арифметики".
Теорема. Усяке ціле число, відмінне від -1, 0 і 1, єдиним чином (з точністю до порядку співмножників) розкладається за допомогою добутку простих чисел.
Доказ. Будемо доводити твердження теореми тільки для натуральних чисел, тому що знак мінус перед числом вміють ставити всі що вміють ставити знак мінус.
Нехай а > 1, р 1 - його найменший простий дільник. Виходить,
а = р 1 а 1 . Якщо, далі, а 1 > 1, то нехай р 2 - його найменший простий дільник і а 1 = р 2 а 2 , тобто а = р 1 р 2 а 2 , і так далі, поки а n не стане рівним одиниці. Це обов'язково відбудеться, тому що а > а 1 > а 2 ..., а натуральні числа із звичайним порядком задовольняють умові обриву спадаючих ланцюгів. Маємо, таким чином,
a = p 1 p 2 ... p n , і можливість розкладу доведена.
Покажемо одиничність. Ну нехай a = q 1 q 2 ... q n - інший розклад, тобто p 1 p 2 ...p n = q 1 q 2 ...q s . В останній рівності права частина ділиться на q 1 , отже, ліва частина ділиться на q 1 . Покажемо, що якщо добуток p 1 p 2 ...p n ділиться на q 1 , то один із співмножників рk мусить ділитися на q 1 .
Дійсно, якщо q 1 | p 1 , то все доведено. Нехай q 1 не ділиться на p 1 . Оскільки q 1 - просте число, то ( q 1 , p 1 ) = 1. Значить знайдуться такі
u , v Î Z , що up 1 + vq 1 = 1. Помножимо останню рівність на p 2 ...p n , одержимо: p 2 ... p n = p 1 ( p 2 ... p n ) u + q 1 ( p 2 ... p n ) v . Обидва доданки справа діляться на q 1 , отже, p 2 ...p n діляться на q 1 .
Тепер нехай, наприклад, q 1 | p 1 . Значить q 1 = p 1 , тому що p 1 - просте. З рівності p 1 p 2 ...p n = q 1 q 2 ...q s , скорочуючи одержимо рівність p 2 ...p n = q 2 ...q s . Далі бачимо, що n =s, і кожен співмножник лівої частини рівності p 1 p 2 ...p n = q 1 q 2 ...q n обов'язково присутній у правій і навпаки.
Відзначимо без доказу два досить очевидних наслідки з цієї теореми.
Наслідок 1. Усяке раціональне число однозначно представляється у вигляді
p1a1 p2a2 ... pkak
де a 1 , a 2 ,..., a k ÏÐÎ Z .
Наслідок 2. Якщо
a = p1a1 p2a2 ... pnan , b = p1b1 p2b2 ... pnbn
цілі числа, те найбільший спільний дільник a і b дорівнює
p1g1 p2g2 ... pngn
а найменше спільне кратне a і b дорівнює
p1d1 p2d2 ... pndn
де g i = min { a i , b i }, a d i = max { a i , b i }.
Для справедливості обговорюваної теореми просто необхідна адитивна структура кільця цілих чисел. Поясню необхідність наявності додавання поганим прикладом.
Поганий приклад. Нехай S = {4 k + 1 | k Î Z } - множина цілих чисел. Легко перевірити, що S замкнена щодо множення:
(4 k 1 + 1)·(4 k 2 + 1) = 16 k 1 k 2 + 4 k 2 + 4 k 1 + 1 = 4·(4 k 1 k 2 + k 1 + k 2 ) + 1 Î S ,
однак ця множина не замкнена щодо додавання. "Квазіпрості" числа з S - далі нерозкладні в добуток чисел з S : 5, 9, 13, 17, 21, 49,... Індуктивним міркуванням, легко переконатися, що всяке число з S розкладене в добуток "квазіпростих". Однак одиничність такого розкладу відсутня: 441 = 21·21 = 9·49, при цьому 9 не ділиться на 21, і 49 не ділиться на 21. От який поганий приклад.