Текст
517.1
ВІВ
Теория чисел — старейший раздел математики.
В течение многих тисячелетий поражает красота ее
идей, универсальность методов, неисчерпаемссть
нових задач и проблем.
Знайомство с теорпей чисел — прекрасная школа
для тех, кто мечтает стать математиком, физиком,
кибернетиком мли зкономистом, для всех, кто ко-
чет постичь закони логики.
Зта книга повествует о загадочньїх свойствах
простих чисел, изучавшихся Евклидом, Зратосфе-
ном, Диофантом, Ферма, Зйлером, Гауссом, Чебише-
вим, Виноградовим, Липником и другими вьідаю-
щимися математиками всех Бремен. Рассказивается
о делимости чисел и конгруенциях. Формулируются
еще не решеннне проблеми теории чисел, рассма-
тривается одна из самих неприступних математи-
ческих теорем — большая теорема Ферма.
Предназпачается учащимся старших классов.
Рукопис рецензували: зав. кафедрою теорії
ймовірностей Київського державного університету
кандидат фізико-математичних наук М. Й. Я Д р е-
пко та методист кабінету математики Ужгород-
ського ІУВ Ю. Ю. Б а рничк а.
„ 70803—298
В М210(04)-7в 32Б~78
В наш час, у вік небувалих досягнень науки і техніки,
математичні методи е провідними в різних найважливіших
галузях знань: в економіці, медицині, біології, космології,
теорії управління.
Проте вже дуже давно людина відчула красу строгих
логічних міркувань, зацікавилась гармонією числових
співвідношень. Адже ще до нашої ери властивості натураль-
них чисел 1, 2, 3, 4,... були вивчені досить глибоко. Ці-
каво, що чим досконаліше люди вивчали властивості чисел,
тим складніші проблеми поставали перед ними. Намагаю-
чись розв’язати ці проблеми, вчені часто створювали нові
математичні методи, а іноді цілі розділи. Тут доречно зга-
дати висловлювання відомого математика XIX століття
Л. Кронекера: «Бог створив натуральні числа, все інше —
справа людських рук». Цей дотепний жарт досить точно
визначає той надійний фундамент, на якому будується
сучасна математика.
Розглянемо перші п натуральних чисел: 1, 2, 3, .... п.
Очевидно, що коли п не дуже велике, легко обчислити їх
суму 8п — 1 + 2 + 3 + ... + п і добуток 1 • 2 • 3 ... п.
Проте результат цієї простої задачі досить цікавий.
Запропонуйте, наприклад, комусь із своїх знайомих
таку задачу-жарт.
На землю поставлено порожній кошик, відміряно від
нього 200 м по прямій і через кожний метр покладено по
яблуку. За який приблизно час можна зібрати всі яблука
в кошик, якщо за один раз можна переносити лише одне
яблуко, а кошик не дозволяється рухати з місця.
Отже, за кожним яблуком треба йти спеціально. І лише
після того, як воно буде віднесено до кошика, можна йти
за наступним яблуком.
Ваш знайомий, безперечно, запевнить Вас, що цю ро<-
боту можна виконати протягом якоїсь години, не більше.
Ну, що ж, хай спробує! Йому доведеться подолати від-
стань, що дорівнює
4
2(1 + 2 4- 3 -|- ••• 4~ 199 4" 200) = 2 • Згоо в
-2 200 •<”+'> = 40200 м.
На це не вистачить навіть цілої доби.
Шукану відстань ми знайшли за формулою:
5„ = 1+2 4-3+-.. +« = "<2+0,
що являє собою окремий випадок суми
5„ = а + (а + 4) + (а + 2<І) -1- • • • + (а + (п — 1) ф =
2а+(п-1)а
— 2
Розглянемо п членів арифметичної прогресії. Уявіть
собі, що на стадіоні проводяться легкоатлетичні змагання.
Оголошується фінальний забіг чоловіків на 110 м з бар’є-
рами. Кожному з восьми учасників забігу доведеться подо-
лати по десять бар’єрів, які буде розставлено за такими
правилами: відстань від лінії старту до першого бар’єра
Г3,72 м, а від кожного бар’єра до наступного по 9,14 м.
Працівник стадіону починає готувати бігові доріжки.
Припустимо, що всі бар’єри складено біля лінії старту і,
крім того, працівник стадіону не може підняти більш як
один бар’єр. Скільки часу потрібно, щоб підготувати до-
ріжки до змагання?
Спробуємо підлічити. Щоб розставити бар’єри лише
на одній біговій доріжці, треба взяти перший бар’єр і, від-
нісши його на 13,72 м, повернутися до лінії старту, тобто
знову пройти відстань 13,72 м. Другий бар’єр слід віднести
на відстань (13,72 + 9,14) м від старту і повернутися за
третім бар’єром. Отже, щоб підготувати лише одну до-
ріжку, працівник стадіону повинен подолати
13,72 + (13,72+9,14) + (13,72+2 - 9,14) + • • • + (13,72+
+ 9 • 9,14) = - ‘ ІЗ-72 + ?,9’14 . ю = 548,5 м з бар’єрами
в руках і таку саму відстань без бар’єрів. А щоб підготу-
9
и(п+£)
вати для забігу всі вісім доріжок, він повинен пройти
8.548,5.2 = 2- 4388 м.
Скільки часу потрібно, щоб виконати таку роботу? Оче-
видно, 4388 м без вантажу можна подолати за 1 год, а
з вантажем — не менш як за 1,5 год. Отже, на підготовку
стадіону потрібно 2,5 год.
Звичайно, це лише жарт. Насправді на всю підготовку
до старту, як правило, витрачається не більш як 5—8 хв.
Наведені приклади яскраво показали, як несподівано
швидко зростає сума чисел. Але ще швидше росте добуток
послідовних натуральних чисел. Для його позначення кори-
стуються таким математичним символом
1 2. З ... п = пі
Він називається факторіалом. Тут за символ
узято саме знак оклику, щоб підкреслити ту дивну швид-
кість, з якою зростає цей добуток. Насправді:
1! = 1
2! 2
З! = 6
41 ~ 24
5! = 120
10! = 3 628 800
1001 = 93 326 215 443 944 152 681 699 238 856 266 700 490
715 968 264 381 621 468 592 963 895 217 599 993
229 915 608 941 463 976 156 518 286 253 697 920 827
223 758 251 185 210 916 864 000 000 000 000 000
000 000 000.
Однак ще швидше зростає число, якщо піднести його
до степеня. Напевне, всім відома дивна історія про вина-
городу, яку зажадав для себе винахідник шахів. Наведемо
Інший, також добре відомий і дуже дивний приклад.
7
ті = іі!
=££64 ^Ї6^Ї4631
£5Ж)&№9бгі,г5
Ш99992Ж1991.5608
Т94ЩШ 701665
‘ ' '^^08^
‘>91в 86400
?
от
Візьмемо аркуш паперу завтовшки, наприклад, 0,1 мм.
Складемо його пополам, потім ще раз — пополам і т. д.
Звичайно, виконати таку операцію з аркушем можна не
більш як 6—8 разів. Але якщо б нам вдалося зробити це,
скажімо, 40 разів, якої товщини досяг би складений аркуш?
Як відомо, кожне чергове складання збільшує попе-
редню товщину аркуша вдвічі. Отже, після повторення
цієї операції 40 разів товщина аркуша буде в 240 разів
більша, ніж 0,1 мм. Це становить 109 951 162 777,6 мм,
тобто близько ПО тис. км. Для наочності нагадаємо, що це
навіть трохи більше, ніж третина відстані від Землі до
Місяця.
У наведеному прикладі ми мали справу вже не із зви-
чайними для нас числами, а із справжнім числовим гіган-
том. Проте існують ще фантастичніш! числові велетні.
Спробуємо з’ясувати, яке найбільше число можна зо-
бразити трьома цифрами. Візьмемо для цього найбільшу
цифру 9. Якщо утворити з трьох дев’яток числа 999 або
99®, то такі числа нікого не здивують. Але число 9" вра-
жає нашу уяву. Адже воно складається з 369 693100 цифр.
Якщо спробувати записати це число звичайними цифрами,
як ми пишемо в своїх зошитах, то його довжина станови-
тиме дві відстані від Києва до Москви.
Безумовно, що оперувати велетенськими числами до-
сить незручно. Тому в астрономії, де такі числа зустріча-
ються на кожному кроці, за одиницю вимірювання великих
відстаней прийнято світловий рік. Це є відстань, яку про-
мінь світла проходить за один рік. Нагадаємо, що швид-
кість світла дорівнює 300 000 км/с. Так, найближча неру-
хома зірка віддалена од Землі на 4 світлових роки. (Спро-
буйте знайти цю відстань у кілометрах).
Але часто доводиться оперувати не лише числовими
велетнями, а й надзвичайно малими числами. Ще раз звер-
немося до астрономії. Земля, як відомо, обертається не
тільки навколо Сонця,- але й разом з усією Сонячною си-
стемою— навколо центра нашої Галактики. Один такий
9
оберт Земля робить приблизно за 200 мільйонів років. Легко
підрахувати, що за життя одного покоління людей наша
Земля робить лише зооооод частину оберту навколо центра
Галактики, тобто проходить кутову відстань 0,00012°
Ми розглянули кілька прикладів. Щоразу розв’язання
було досить простим, хоч результати й не зовсім сподівані.
Проте більшість задач, що стосуються чисел, розв’язати
дуже важко. Найцікавішими і, мабуть, найскладнішими
є задачі, пов’язані з поняттям простого числа.
Порівняємо, наприклад, такі дві задачі.
1. Чи є число 1 458 023 567 964 023 десятим степенем
натурального числа?
2. Чи кожне парне число є сумою двох простих чисел?
На перший погляд перша задача здається досить важ-
кою, а друга — легкою. Насправді ж усе навпаки. Навіть
учень V—VII класів, може легко розв’язати першу задачу.
Що ж стосується другої задачі, то вона добре відома всім
математикам, бо є частиною знаменитої «проблеми Гольд-
баха>' і вже 225 років хвилює учених. У 30-х роках на-
шого століття радянським математикам Л. Шнірельману
і І. Виноградову вдалося наблизитись до її розв’язання.
У своїх міркуваннях вони спираються на дуже глибокі
аналітичні методи сучасної математики.
Зовнішня простота умови взагалі характерна для най-
складніших задач теорії чисел. Саме це й надало теорії
чисел надзвичайної привабливості, зробило її найулюбле-
нішою наукою видатних математиків.
Вважається, що теорія чисел стала систематичною і са-
мостійною наукою, починаючи з праць і відкрить П. Ферма
(1601—1665). Однак найбільші й найцікавіші досягнення
в цій галузі з’явилися трохи пізніше і належать Леонарду
Ейлеру (1707—1783). Ознайомлюватись з елементами теорії
чисел ми почнемо з вивчення простих чисел.
Ю
§ 1. ПРОСТІ І СКЛАДЕШ ЧИСЛА
Запропонуйте комусь задумати якесь трицифрове
число. Тепер нехай Ваш знайомий припише до нього
справа таке саме число. Знайдене шестицифрове число
запропонуйте йому поділити на 7.
— А якщо не розділиться? — запитає знайомий.
— Розділиться! — запевните Ви.
І дійсно розділилося. Але Ви ще раз здивуєте свого
знайомого, запропонувавши йому поділити знайдену
частку на 11.
І знову поділилося без остачі. Але і це не все. Тепер
Ви пропонуєте нову частку поділити на 13. Ваш зна-
йомий, швидко виконавши цю операцію, здивовано по-
глядає на Вас.
— Цього разу не просто поділилося,— кажете Ви
голосом чарівника,— але й в результаті знайдено заду-
мане число.
— Саме так,— здивовано шепоче Ваш знайомий.
Ідея цього фокуса дуже проста: приписуючи справа
до деякого трицнфрового числа таке саме число, ми не-
наче множимо це число на 1001, наприклад:
537537-537000+537 = 537 (1000+1) =537-1001
Але 1001 =7-11-0. Отже, цей математичний фокус
грунтується на знаходженні розкладу цілого числа на
прості множники. Саме з цієї теми і починаємо наше зна-
йомство з простими числами.
Розглянемо довільне натуральне число п. Числа, на які
ділиться л, називають його дільниками. Будь-яке
натуральне число ділиться на 1 і на себе. Крім того, всі
натуральні числа можна поділити на два класи:
1. Числа, які не діляться на жодне число, крім одиниці
й самого себе.
2. Числа, які, крім одиниці й самого себе, мають ще й
інші дільники (такі дільники називатимемо власними
дільниками цих чисел).
12
До першого класу належать, наприклад, числа: б, 41,
269, а до другого 14, 387, 1065.
Такі два класи натуральних чисел знали ще задовго
до нашої ери. Вже тоді вони дістали назви п р о с т и х
і, відповідно, складених чисел.
Одиницю домовились не відносити ні до простих, ні до
складених чисел.
Назвемо кілька послідовних простих чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Зауважимо відразу, що 2 — єдине парне просте число.
Всі інші прості числа — непарні.
Крім того, якщо пересуватись управо вздовж натураль-
ного ряду, то прості числа траплятимуться в ньому все
рідше і рідше.
Може постати запитання: якщо складених чисел значно
більше, ніж простих, то чому вивчати натуральні числа
починають з розділу про прості числа? Та й взагалі, чому
простим числам приділяється така велика увага в різних
математичних дослідженнях? Щоб відповісти на ці запи-
тання, наведемо деякі відомості з теорії чисел.
Число а називається дільником числа п, якщо
існує таке ціле число Ь, що п = а • Ь. Очевидно, число Ь
також буде дільником п. Отже, кожне складене число можна
зобразити у вигляді добутку його власних дільників.
Нехай п = а • Ь.
Якщо при цьому а і Ь — складені числа, то і їх, у свою
чергу, також можна розкласти на добуток власних дільни-
ків: а = р • д; Ь = к • І.
Тоді п = р • <7 • к • І. Розкладати можна на множники
доти, поки всі знайдені множники не будуть простими чис-
лами.
Отже, довільне складене число п можна розкласти на
добуток простих чисел, кожне з яких буде власним дільни-
ком п.
Наприклад, 200 = 4:50 = (2 . 2) . (5 • 10) == 2 -2 • 2- 5 -5.
13
Описану операцію називають розкладом числа п
на прості множники:
я = Рі Ра Рз ••• Рт,
Рі(і = 1, 2, 3, т) — прості числа.
Ось чому дуже важливо докладно ознайомитися з прос-
тими числами. Знаючи властивості окремих співмножни-
ків Рі, рй, .... р,п числа п, можна розв’язати багато цікавих
задач, що стосуються самого числа п.
і 2. НЕСКІНЧЕННІСТЬ МНОЖИНИ ПРОСТИХ ЧИСЕЛ
Зрозуміло, що зразу ж після першого ознайомлення
з простими числами постає питання про їх кількість. Скіщ
ченна чи нескінченна множина простих чисел?
Теорема. Множина простих чисел — нескінченна.
Доведемо це. Вірніше, ми доведемо рівносильне твер-
дження, що не існує найбільшого простого числа. Для
цього скористаємося методом Евкліда. Незважаючи на те,
що з часів Евкліда минуло вже два з чвертю тисячоліття,
запропонований ним метод доведення І тепер захоплює
математиків своєю дивною легкістю і витонченістю.
Нехай відомі прості числа 2, 3, 5, 7, 11, ..., р. Дове-
демо, що існує просте число, більше за р. Для цього побу-
дуємо таке число:
М = 2 • 3 • 5 7 11 ... р Ч- 1.
М є сумою двох доданків. Перший доданок — це велике
парне число, що утворилося від добутку всіх простих
чисел, починаючи з 2 і до р. А другий доданок — це оди-
ниця.
У зв’язку з тим, що М — непарне число, може статися
два випадки. Перший — М просте число. Але М > р.
Отже, в цьому випадку ми маємо просте число, більше за р.
Другий випадок — М складне число. Тому воно має
15
прості дільники. Нехай р* — один з них. З’ясуємо, яким
може бути просте число р*.
Перший доданок 2 • 3 • 5 • 7 • 11... р числа М ділиться
на 2, а другий, тобто 1, на 2 не ділиться. Отже, 2 не може
бути дільником числа М. Так само перший доданок ді-
литься на 3, па 5, на 7, ..... на р, а другий доданок не ді-
литься на жодне з цих чисел. Отже, ні 3, ні 5, ні 7, ... ні р
не можуть бути дільниками М. (Тепер зрозуміло, чому
за другий доданок взято саме одиницю).
Таким чином, р* не може дорівнювати ні 2, ні 3, ні 5,
..., ні р. Перебрано всі прості числа до р включно. Отже,
залишається, що р* > р.
Ми довели, що для довільного простого числа р існує
просте число, більше за р. Ряд простих чисел — нескін
ченний.
До такого самого висновку пізніше прийшли й інші
дослідники в галузі теорії чисел. Згадаємо, наприклад,
російського математика П. Л. Чебишова (1821—1894). Він
довів постулат французького математика Бертрана (1822—
1900): для довільного натурального числа п > 3 між п
і 2п — 2 існує хоча б одне просте число.
§ 3. ЗНАХОДЖЕННЯ ПРОСТИХ ЧИСЕЛ
Щоб з’ясувати, чи є деяке натуральне число п простим
або складеним, треба, звичайно, спробувати знайти його
власні дільники. Якщо ж їх не буде, то число п просте.
Розглянемо, наприклад, числа 731 і 2389. Користуючись
ознаками подільності або виконуючи ділення безпосередньо,
переконуємося, що число 731 не ділиться ні на 2, ні на З,
ні на 5, ні на 7, ні на 11, ні на 13. Але воно ділиться на 17.
Отже, число 731 складене.
Встановити, яким е число 2389, значно важче. Безпосе-
редньо поділивши його на всі прості, менші від нього числа,
можна побачити, що це число не має жодного простого
16
дільника, тобто воно просте. Але чи не занадто багато
операцій ділення ми виконали? Чи не можна якось про-
стіше встановити, що це за число? Відповіддю на ці пи-
тання буде така невелика теорема.
Теорема. Якщо натуральне число п складене, то
воно має хоча б один простий дільник, не більший від
У~п.
Доведення. Розглянемо довільне складене число п.
Воно повинно мати хоча б два власних дільники, тобто
п - а • Ь. Очевидно, що або 6 ]/п (інакше
їх добуток був би більшим від п).
Якщо а або Ь виявиться складеним числом, то його
можна розкласти на прості множники, кожний з яких
завжди менший від У~п і водночас є власним дільником
числа п. Теорему доведено.
Отже, натуральне число п буде простим, якщо воно не
ділитиметься на жодне просте число, яке менше або дорів.
нюе У п. ____
Повернемося до числа 2389. У 2389 < 49 (бо 492 =
==- 2401). Оскільки 2389 не ділиться на жодне просте число,
менше від 49, то воно просте.
Тут одразу виникає нова задача: як знайти всі прості
числа, що не перевищують деякого заданого натурального
числа ДО? Цю задачу найлегше розв’язати, застосувавши
метод, що називається «решето Ератосфена».
Випишемо всі натуральні числа від 2 до ДО. У цій послі-
довності викреслимо кожне друге число після 2, тобто
числа 4, 6, 8, 10, 12, ... . Отже, ми відкинемо всі парні
числа. Потім викреслимо кожне третє число після 3 (врахо-
вуючи й числа, викреслені раніше). Так ми відкинемо
числа 6, 9, 12, 15. тобто всі числа, що діляться на 3.
Закінчивши другий етап викреслювань, зробимо анало-
гічну операцію для числа 5, тобто викреслимо кожне п’яте
число після нього. Число 4 ми пропустили, бо воно скла-
дене І, отже, вже викреслене. З цієї ж причини пропус-
17
каемо число 6 І переходимо до наступного етапу: викрес-
люємо кожне сьоме число після 7 і т. д. Таким чином ми
викреслимо з написаного ряду всі складені числа. А неви-
креслиннми залишаться всі прості числа, що не переви-
щують N.
Цей метод знаходження простих чисел можна дещо
спростити. По-перше, досить виписувати лише непарні
числа, що не перевищують У, залишаючи на початку ряду
число 2 (єдине парне просте число), і робити зазначені вище
викреслювання, але вже починаючи з трійки. По-друге,
як тільки дійдемо до першого простого числа, більшого
від І^ЛГ, викреслювання можна більше не робити. Всі
числа, що залишилися не викресленими, аж до самого N.
будуть простими. Це випливає з доведеної вище теореми.
Спробуємо, наприклад, знайти за допомогою решета
Ератосфена всі прості числа, що не перевищують 100.
Внаслідок викреслювань дістанемо:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 81, 87, 41, 43, 47
58, 59, 61, 67, 71, 73, 79, 83, 89, 97.
$ 4. РОЗПОДІЛ ПРОСТИХ ЧИСЕЛ.
ПРОСТІ ЧИСЛА-БЛИЗНЯТА
Дуже цікавим є питання про розподіл простих чисел
в натуральному ряді. Як визначити кількість простих чи-
сел, що не перевищують н? Виявляється, що це одна з най-
складніших задач у теорії чисел.
Численні спроби багатьох математиків дати точну фор-
мулу кількості простих чисел серед перших п чисел нату-
рального ряду виявилися марними. І тоді вчені спрямували
свої зусилля на знаходження наближеної формули.
Уже давно існують великі таблиці простих чисел (аж
до 10 мільйонів). Досить лише нашвидку проглянути їх,
щоб переконатися: прості числа розподілені серед нату-
ральних дуже неодноманітно. Так, в інтервалі від 1 до
19
100, у першій сотні, е 25 простих чисел, у другій сотні
їх 21, у третій 16, у восьмій — 14 і т. д. Але не слід думати,
що кількість простих чисел у кожній наступній сотні змен-
шується. Так, у дев’ятій сотні їх 15, більше, ніж у восьмій
і шостій сотнях, к. Ф. Гаусе встановив, що 26379-та сотня
не має жодного простого числа, у той час як 27050-та сотня
містить 17 простих чисел, уобто більше, ніж третя.
Позначимо через п(х) кількість простих чисел, що не
перевищують дійсного числа х > 1. Відомо, що л(1) =®0,
л(2) = 1, л(3) = 2, л(5) = 3, л(10) = 4, л(50) = 45,
л(100) = 25, л(1000) = 168, лОО4) = 1229, л(ІО’) =»
- 5 761 455.
Простих чисел нескінченно багато, тому із збільшенням
х необмежено зростатимуть значення л(х).
Відношення природно назвати «щільністю»
розподілу простих чисел. Так,
якщо х= 1000, то = 0,168;
якщо х =• 1 000000, то 0,078498.
Відомі формули, за якими можна наближено обчислити
значення цього відношення.
Наприклад, для х > 50
Уперше «середню щільність» простих чисел на відрізку
[1; х] дослідив Л. Ейлер.
Блискуча ідея відносно наближеного обчислення
належить Гауссу. Вивчаючи таблиці простих чисел, він
помітив, що
я (ж)____1_
X ~ Іпх
21
Тут 1п х — натуральний логарифм числа х, тобто лога-
рифм-за основою е(е»*2,71 ...).
Точність запропонованого Гауссом виразу для щіль-
ності розподілу простих чисел зростає із збільшенням х.
А коли х->со, відношення —прямує до одиниці.
В такому випадку говорять, що «асимптотично
1
дорівнює»
Проте сам Гаусе довести цього не зміг. Глибоке теоре-
тичне обгрунтування формули л(х) ~ дав Чебншов,
а остаточно її довели значно пізніше французькі матема-
тики Адамар і Валле Пуссен за допомогою глибоких та
складних методів сучасної математики.
Отже, хаотичність розподілу простих чисел у натураль-
ному ряді зникає, якщо розглядати його «у середньому».
Відкриття простого закону, за яким відбувається цей роз-
поділ, слід вважати одним з найвидатніших в усій мате-
матиці .
Говорячи про розподіл простих чисел, корисно заува-
жити, що з теореми Чебишова, пов’язаної з постулатом
Бертрана (див. § 2), випливає: для довільного натураль-
ного числа п > 3 існують хоча б три простих числа ри
Рк Рз, таких, що
П < рі < 2п < Рг < 4п < р3 < 8и.
Коли ж замість п візьмемо 10а’1, то дістанемо:
10а"1 < Р1 < 2 • 10а"1 < Рі < 4 • 10а’1 < Рз < 8 • 10*-*.
Отже, для доцільного натурального числа к обов’яз-
ково існують хоча б три простих числа, що мають по к цифр
кожне. Справді, нам добре відомі чотири одноцифрових
простих числа: 2, 3, 5, 7. Двоцифрових простих чисел
22
е 21, трицифровях — 143. Існує хоча б три простих числа,
що мають по сто цифр. Нещодавні їх було знайдено:
81 • 2*** 4- 1, 63 • 2386 4- 1, 35 • 2®м 4- 1.
Проте досі не відоме жодне просте число, яке б мало,
наприклад, тисячу цифр.
Звернемо увагу ще й на такий факт. Пересуваючись
досить далеко від початку натурального ряду, можна
знайти будь-які довгі інтервали послідовних натуральних
чисел, серед яких не буде жодного простого числа. Побу-
дуємо, наприклад, такий інтервал завдовжки у 1000 послі-
довних натуральних чисел. Скористаємося методом, запро-
понованим Евклідом для доведення нескінченності мно-
жини простих чисел.
Побудуємо число М так:
М = 2 • З • 4 • 5 • 6 ... 1000 • 1001
(візьмемо добуток усіх послідовних натуральних чисел
до 1001). Зрозуміло, що М ділиться на всі послідовні нату-
ральні числа від 2 до 1001 включно. Тепер випишемо 1000
послідовних натуральних чисел:
М 4- 2, ЛІ 4- З, М 4- 4, ..., М 4- 1000, М 4- 1001.
Усі ці числа будуть складеними. Справді, перше з них
ділиться на 2 (бо воно є сумою двох доданків, кожний
з яких ділиться на 2), друге — на 3 (з тих самих мірку-
вань) і т. д. Останнє, тисячне по порядку число ділиться
на 1001.
Зауважимо, що тут за М можна взяти й число значно
менше від 1001, а саме: добуток усіх простих чисел від 2
до 997.
Тим більш дийним здається, що у множині простих
чисел існують так звані «числа-близнята». Близня-
тами називаються два простих числа, які відрізняються
лише па дві одиниці, тобто є послідовними непарними чис-
лами. Наприклад, 5 і 7, 11 і 13, 41 і 43, 101 і 103. Близнята
23
трапляються і серед дуже великих чисел: 109 619 і 109 621
або 1 000 061 087 і 1 000 061 089.
Існує гіпотеза, що пари простих чисел-близнят станов-
лять нескінченну множину. Але нікому й до цих пір ще
не вдавалося довести чи спростувати цю гіпотезу.
Інакше кажучи, досі не доведено і не спростовано твер-
дження, що рівняння х — у — 2, де х і у — прості числа,
має безліч розв’язків.
Отже, ми ознайомилися з іще однією дивною власти-
вістю простих чисел: з одного боку, при достатньо вели-
кому п. можна як завгодно довго перебирати послідовні
натуральні числа п, п+ 1, п + 2, ... і не зустріти жодного
простого числа, а з іншого,— навіть серед дуже великих
натуральних чисел можна зустріти пару простих чисел,
що відрізнятимуться одне від одного лише на дві одиниці.
§ 5. ЧИСЛА ФЕРМА І ЧИСЛА МЕРСЕННА.
ПСЕВДОПРОСТІ ЧИСЛА
Довгими і марними були спроби багатьох математиків
знайти формулу простих чисел. Часто їм здавалося, що
успіху досягнуто. Проте з часом виявлялося, що знайдені
формули неправильні. Одну з помилкових формул вивів
навіть видатний П. Ферма. Він вважав, що всі числа виду
Г4 = 2?т1, де £ = 0, 1, 2, З,
будуть простими. Однак у 1732 році Л. Ейлер встановив,
що вже коли к. — 5, число Рк = 2г® 4- 1 = 232 4- 1 =
= 4 294-867 297 складене, бо воно ділиться на 641.
Пізніше багато математиків цікавилося числами Рк.
їх почали називати числами Ферма. Нині відомо
вже 46 складених чисел Рк. Складеними, наприклад, є
Г7, Ра, Р13, Раі, Р6Ь, Р1Ь0, РІЬІ, РІ9І6. Серед них є такі,
для яких повністю знайдено всі їхні прості дільники (на-
25
приклад, для Рь та Г«); для яких знайдено лише один
простий дільник (наприклад, для числа ГіМ8), а є й такі,
для яких ще не знайдено жодного простого дільника, хоча
відомо, що вонй існують (наприклад, для Г7, Г8, Р13).
Таким чином, було розв’язано ще одну загадку, пов’я-
зану з числами Ферма.
Щоб читачі уявили собі грандіозність подібних розра-
хунків, зауважимо, що число Р33 =» 22’в+ 1 містить більше,
ніж 20 мільярдів цифр; рядок, який міститиме це число,
буде значно довший за екватор. Один з простих дільників
Р33 дорівнює 5 23» + 1 = 2 748 779 069 441.
Слинимося на найбільшому з відомих нам складених
чисел Ферма, тобто Р1МІ. Воно має фльш як 1О‘И цифр!
Лише кілька років тому було знайдено один простий діль-
ник для цього числа, а саме:
р - 5 • 2ім7 + 1.
Звичайно, багато читачів зацікавляться, а як саме було
знайдено цеД дільник? Існує теорема, за якою натуральний
дільник числа Рк повинен мати вигляд 2"+2 • к 4- 1 (де
к — 0г 1, 2, Виходячи | цього, для числа р3 слід шу-
кати влаісиі дільники у вигляді 27 • к 4- 1 — 128 • к 4- 1.
Якщо к = 0, мремо число І, яке не є власним дільником
Р6. Якщо к 1, 2* 3, 4, дістаємо числа, які взагалі не є
ділрникдмд р3, а якщо к = 5, маємо число 128 • 5 -Ь 1 =
— 641, відносно якого безпосереднім діленням уожна легко
переконатися, що воно є дільником числа Р3. Так, без
значних труднощів, ми побачили, що число р6 має власні
дільники.
Так. само було знайдено дільник числа Г1М8. Але зрозу-
міло, що числа Г1848 ділили на числа виду к 21947 4- і
за допомогою спеціально складеного алгоритму і, сучасних
електронно-обчислювальних машин.
Уже давно висунуто гіпотезу, за якою всі числа не-
скінченної послідовності
27
2 + 1, 22 + 1, 22Ї + 1, 222ї + 1, 222ЇЇ + 1,
прості. Але в 1953 році за допомогою наведеного вище ме-
тоду було знайдено дільник числа Р1в (він дорівнює 218Х
X 3150 + 1). Отже, п’ятий член цієї послідовності (Рц «
22
= 22 +1) число складене. Тим самим гіпотезу було спро-
стовано.
Мабуть, читачі вже звернули увагу на те, як сміливо
оперують математики такими величезними числами. Це
можливо тому, що йдеться не про довільні великі непарні
числа, а лише про числа, які на одну одиницю відрізня-
ються від степеня двійки. Математикам вже давно вдалося
виявити багато цікавих і навіть несподіваних властивостей
таких чисел, знайти ряд прийомів для знаходження їх
дільників.
Розглянемо, наприклад, такий спосіб розкладу чисел
на множники:
2е + 1 = (І2 + 22) - (22 + З2);
210 + 1 = (З2 + 42) • (4а + 52);
г^-2 +1 = ’((2Л — І)2 + (2л)а) • ((2")2 + (2Л + І)2).
Правильність цієї формули легко перевірити, якщо без-
посередньо зробити всі необхідні перетворення у правій
частині.
Ми дістали оригінальний спосіб розкладу на множники
чисел типу 24л+2 + 1.
Звичайно, дехто здивується: навіщо нам потрібний цей
спосіб розкладу, коли й так добре відомо, що всі числа
типу 24л+2 + 1 складені, бо кожне з них ділиться на 5?
Нагадаємо, що коли п, — непарне число, то (ал + Ь")
обов’язково ділиться на (а + Ь). Внаслідок цього 24л+2+
+ 1 — 42л+1 + 1 ділиться на 4 + 1 = 5.
Але незважаючи на це, запропонована вище формула
розкладу чисел типу 24л+2 + 1 на множники дуже корисна.
29
Візьмемо конкретний приклад. Нехай п *=* 8. Тоді,
24.8+2 4. 1 х= 234 + 1 = 17 179 869 185 = 5 • 3435973837.
А тепер спробуйте відповісти на запитання: чи остаточ-
ний цей розклад? Чи може число 3 435 973 837 е складе-
ним?
Відповісти на це запитання можна, скористувавшись
запропонованою вище формулою:
24-8+2 _1_ 1 = ((2е — І)2 + (28)2) ((28)2 + (2е + І)2) -
» (255* + 2562) ♦ (2562 + 2572) = (65025 + 65536) X
Х(65536 4- 66049) = 130561 • 131585 = 5 • 26317Х
X 130561.
Отже, число 3 435 973 837 складене. Воно дорівнює
добутку 26 317 130 561.
Розповідаючи про числа Ферма, слід підкреслити роль,
яку вони відіграли при розв’язуванні однієї з найцікаві-
ших проблем геометрії. Йдеться про можливість побудови
правильних многокутників за допомогою циркуля й лі-
нійки. Розв’язок цієї задачі, знайдений Гауссом. такий:
правильний многокутник може бути побудований за допо-
могою циркуля й лінійки ТОДІ І тільки тоді, коли кіль-
кість його сторін дорівнює добутку 2 у будь-якому нату-
ральному степені (включаючи й нульовий степінь) і різних
простих чисел Гп •= 22” 4- 1. Таким чином, кількість сторін
правильного многокутника має дорівнювати:
N - 2к • Рі • Рі ...рк
(тут к чи 0, 1,2, 3, ..., а рі, ріг .... р, — різні прості
числа Ферма).
Наприклад, коли к =* 0, а р ° » 8, то N = 5, а
якщо р — Рг я 17, то N = 17. Отже, за Допомогою цир-
куля й лінійки можна побудувати Правильні: 5-кутник,
10-кутник, 17-кутник, правильний 85-кутник, 340-кутник
і т. д.
зо
Тепер ознайомимося з однією важливою групою чисел—
ч и.с лами М е р с е н н а. (Мерсенн —французький уче-
ний XVII століття). Так називають числа типу Мя =*
=-2п — 1 (тут п— довільне натуральне число).
Спочатку нагадаємо одну дуже важливу формулу
(а* — Ьк) = (а — Ь) • (ак~к 4- а*-2 • Ь 4-
4- • • • 4- а • Ьк-* 4- Ьк~к).
Цю формулу можна довести звичайним розкриттям дужок,
множенням і зведенням подібних членів у правій частині.
З неї випливає, що 2" — 1 = 2п~і 4- 2п~2 4- 4-
4- 22 4- 2х 4- 1, тобто число Мерсенна Мп можна визна-
чити також як суму п перших членів геометричної прогре-
сії 1, 2, 22, 23, 2*, . З цієї формули випливає також і те,
що коли п — складене число (п = к • /), то
2П — 1 = (2*)* — 1 - (2і — 1). (2'<*-і) +
4.... 4- 2»» 4- 2* 4- 1),
тобто 2" — 1 ділиться на 2і — 1.
Таким чином, ми дістали важливий результат: коли а
складене число, то й відповідне число Мерсенна Мп
також буде складеним,
рипишемо кілька перших чисел Мерсенна; М1 1,
З, М8 == 7, = 15, Мь = 31, Мв = 63, М, =
На перший погляд здається, що коли п •— просте число,
то'ж.М» також буде простим. Проте це не так. Вже якщо
п ==341, маємо
2й — 1 = 2047 = 23 89.
О^же, які з чисел Мерсенна прості? Поки що таких
відомя дише 23. Простими- є числа Мп, коли п = 2, З, Б,
7, 13, Ж19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281,
3212, 42&3, 4423, 9689, 9941, 11213. Одинадцять найбільших
простих' чисел Мерсенна було знайдено зовсім недавно за
допомогою електроннообчислювальних машин. Число
Лі8==
=127
зі
Л4]1213 ~ 211213 — 1 має 3376 цифр і є, мабуть, найбільшим
з відомих нині простих чисел.
Довгий час вважали, що число Л4в7 просте. Проте ви-
явилося, що
2®7 — 1 = 193 707 721 761 838 257 287.
Задача знаходження простих чисел Мерсенна стала
значно простішою, коли було доведено таку теорему:
якщо п — просте число, то всі натуральні дільники числа
Л1„ повинні мати вигляд 2 • »• к + 1 (тут А = 0, 1, 2,
З,
Насправді, як ми вже знаємо, власними дільниками Л4и
є числа 23 і 89. Легко бачити, що
23 = 2-11.1 + 1 (й=1),
89 = 2 • 11 • 4 + 1 (к = 4).
Перевіримо, що й знайдені дільники числа Мв7 також
задовольняють наведену теорему:
193 707 721 = 2 - 67 • 1 445 580 + 1,
761 838 257 287 = 2 67 5 685 360 129 + 1.
Зрозуміло, що за цією ж теоремою дільники числа А41Л1
повинні мати вигляд 202 к + 1. На жаль, досі не .знай-
дено жодного простого дільника числа А1101 (мабуть, у цьому
випадку число к дуже велике), хоч іншим шляхом доведено,
що число А4101 складене.
Числа Мерсенна мають велике значення у теорії чисел.
Це пояснюється тим, що за їх допомогою можна знаходити
так звані досконалі числа. Але з цим дуже цікавим типом
чисел ми ознайомимося в § 9 цього розділу.
Вже давно математикам відома теорема, за якою для
довільного простого числа р число 2р — 2 ділиться на р.
Постає запитання: чи правильна обернена теорема, тобто
чи можна на основі того, що число 2п — 2 ділиться на п,
стверджувати, що п — просте число? Візьміть кілька чи-
сел І спробуйте самостійно перевірити це. Щоразу ви діста-
32
ватимете позитивну відповідь на поставлене запитання.
Мабуть, шляхом таких перевірок, тобто емпірично матема-
тики Стародавнього Сходу ще 25 століть тому довели, що
коли п >1 і 2" — 2 ділиться на п, то число п. просте.
Ця теорема справджується для всіх натуральних чисел
аж до 300. Проте вона виявилася неправильною. Знайдено
числа, які не задовольняють цієї теореми. Так, наприклад,
2»«— 2 ділиться на 341, але 341 не є простим, бо 341 =
-11 31. Нині відомо вже багато натуральних чисел, які
є складеними, хоча для них виконується умова згаданої
теореми. Такі числа дістали назву псевдопростих
чисел.
Тривалий час вважалося, що псевдопростими можуть
бути лише непарні числа. І лише у 1950 році було знайденб
перше парне псевдопросте число. Воно дорівнює 161 038.
Знаходження цього числа було дуже важкою справою.
Однак перевірити те, що число 2181038 — 2 ділиться на
161 038, можна швидко й без труднощів. Зробимо це.
2івіоз8_2==2 (2Ш037— 1). Зазначимо, що 161037 =
= З2 29 617.
Отже, число (2161037— 1) ділиться на 2е— 1 та на 229— 1.
Але 29 — 1 = 7 • 73 та 229 — 1 = 1103 486 737. Таким
чином, число 2191037— 1 ділиться І на 73, і на ПОЗ. Зна-
чить, відносно самого числа 2191038— 2 маємо, що воно
ділиться на 2, на 73 та на ПОЗ. Але це три різних простих
числа, тому число 2181038 — 2 ділиться й на їх добуток 2 х
х 73 1103 = 161 038.
При ознайомленні із згаданою теоремою може постати
запитання: чи існують теореми, які є критерієм для пере-
вірки того, чи є дане натуральне число простим.
Подібних теорем існує досить багато. Ось одна з най-
відоміших.
Теорема Вільсона. Натуральне число п > 1 просте
тоді й тільки тоді, коли число (п— 1)! + 1 ділиться на п.
До речі, вперше довів цю теорему англійський математик
Варінг.
2 8-8
33
$ 6. ПРОСТІ ЧИСЛА В АРИФМЕТИЧНИХ
ПРОГРЕСІЯХ
У § 2 ми ознайомилися з доведенням Евкліда, що в на-
туральному ряді чисел 1, 2, 3, 4,5 ... міститься нескінченна
множина простих чисел. Тепер розглянемо кілька інших
нескінченних послідовностей натуральних чисел. Напри-
клад:
1, 4, 7, 10, 13, 16, 19, ...
З, 7, 11, 15, 19, 23, 27
5, 11, 17, 23, 29, 35, 41 ...
Кожна з цих послідовностей е арифметичною прогре-
сією. Постає запитання: скільки простих чисел міститься
в кожній з них? Спостереження наштовхують на думку,
що в кожній з наведених послідовностей простих чисел не-
скінченно багато. І це насправді так. Перевіримо, напри-
клад, цей факт для другої послідовності.
Теорема. Простих чисел типу 4л 4- З існує нескін-
ченно багато.
Спочатку зробимо два зауваження.
1. Всі прості числа (крім 2) непарні, тому вони обов'яз-
ково мають бути числами типу 4л 4- З або 4л 4- 1.
2. Добуток двох чисел типу 4л 4- 1 також є числр того
самого типу, бо (4к 4- 1) (4/ 4- 1) = 16£/ 4- 4к 4- 4/ 4-
4- і = 4(4£/ 4. £ 4- /) 4- і = 4г 4- і.
Звідси можна зробити висновок, що кожне складене
число типу 4л 4- 3 повинне мати хоча б один простий множ-
ник цього ж типу.
Доводитимемо теорему аналогічно до того, як було дове-
дено нескінченність множини простих чисел (див. теорему
У § 2).
Припустимо, що р3, ..., рт — всі відомі нам
прості числа типу 4л 4- 3. Покажемо, що обов’язково
34
існують і інші прості числа цього ж типу. Розглянемо
4ислб Л4:
М = 4 (Рі . р2 • р3 ... рт) — 1 = 4 (рх • рг • р, ...
... рт - 1) + 3.
Число М непарне і е числом типу 4п + 3. Якщо ви-
явиться, що М просте, то матимемо нове просте число типу
4п + 3. Якщо ж М буде складеним числом, то воно по-
винно мати прості множники. Згадуючи друге зауваження,
робимо висновок, що хоча б один з простих множників
має бути числом типу 4/г 4- 3. Позначимо цей простий
множник через р*. У зв’язку з тим, що М — це різниця
двох чисел, перше з яких ділиться на на ра,..., на
а друге (тобто 1) не ділиться на жодне з цих чисел, то само
М не ділиться ні на рІ9 ні на р2, ні нар3..., ні на рт. Отже,
р* не може дорівнювати жодному з цих чисел. Таким чи-
ном, р* — якесь нове просте число типу 4/г + 3. Теорему
доведено.
Аналогічно можна довести існування нескінченної мно-
жини простих чисел типу 4п + 1, би + 1, би + 5 тощо.
Ми поступово приходимо до твердження, що в довіль-
ній арифметичній прогресії а, а+ (і, а 4- 2й, ... , а +
4- п(і9 ... (де а і не мають спільних дільників) мі-
ститься нескінченна множина простих чисел. Строге дове-
дення цього твердження вимагало від математиків вели-
чезних зусиль. Першим довів його за допомогою складних
методів математичного аналізу та теорії функцій відомий
математик XIX століття Л. Діріхле (1805—1859 рр.).
У цьому параграфі ми зробимо кілька зауважень щодо
зв’язку-простих чисел з многочленами.
Вище вже йшлося про те, що численні спроби знайти
елементарну формулу, яка при всіх значеннях п давала б
прості числа, виявилися марними. Однак існують цікаві
вирази, що дають досить багато простих чисел.
Наприклад, п2 — п + 41. При будь-якому значенні п
від 1 до 40 цей вираз даватиме просте число.
2*
35
Можна навести ще й такий квадратний тричлен від-
носно п:
IIі - 79п + 1601.
Тут діставатимемо прості числа при всіх значеннях від 1
до 79.
Таких прикладів можна навести чимало. Але вже давно
строго і досить елементарно доведено, що не існує такого
многочлена з цілими коефіцієнтами /(х) =
+ • • • + ак^х + йк, який для кожного натураль-
н го значення х давав би просте число /(л).
Це твердження понад двісті років тому довів Л. Ейлер.
$ 7. ОСНОВНА ТЕОРЕМА АРИФМЕТИКИ
У § 1 уже зазначалося, що прості числа відіграють
велику роль у математиці. І пояснюється це тим, що до-
вільне складене число завжди можна розглядати як добу-
ток простих множників. Так, 4140 = 2 • 2 • 3 • 3 • 5 • 23.
Взагалі, п = рг • р2 • р3 ... рт.
Цей факт безпосередньо виходить із самого означення
простого та складеного чисел.
А чи єдиний такий розклад на прості множники?
Мабуть, дехто здивується, почувши таке запитання.
Адже позитивна відповідь на нього здається цілком оче-
видною. Але чи насправді все так просто? Уявіть, що уда-
лося розкласти на два простих множники таке велике число,
як, наприклад, 18727.
18 727 = 61 • 307.
Чи можна лише на основі інтуїції стверджувати, що
в числа 18 727 нема ніяких інших простих множників?
Як бачимо, це твердження потребує строгого математич-
ного доведення.
Отже, ми прийшли до необхідності доводити основну
теорему арифметики. Але насамперед спинимося на кіль-
кох допоміжних твердженнях.
37
Число Л називається спільним дільником натуральних
чисел а і Ь, якщо кожне з цих чисел ділиться на і.
Введемо ще одне поняття. Два натуральних числа нази-
ваються взаємно-простими, якщо вони не мають ніяких
спільних дільників, крім 1.
Надалі нам будуть потрібні такі допоміжні теореми:
Теорема 1. Якщо просте число рк ділиться на просте
ЧИСЛО р2, то обов’язково рі = р2.
Теорема 2. Кожне натуральне число п або ділиться
на дане просте число р, або взаємно-просте з ним.
Теорема 3. Якщо добуток цілих чисел а • Ь ділиться
на просте число р, то або а, або В ділиться на р, або
вони обидва діляться на р.
Висновок з теореми 3. Якщо добуток цілих чисел
а • Ь • с ... к • І ділиться на просте число р, то хоча б
один із співмножників обов’язково ділиться на р.
Ці три твердження і висновок доводяться зовсім легко.
Тому надаємо можливість зробити це самим читачам.
А тепер повернемося до основної теореми.
Основна теорема арифметики. Ксжне натуральне
число, крім одинйці, можна розкласти на добуток простих
множників єдиним способом.
Доводитимемо цю теорему методом від супротивного.
Припустимо, що для якогось натурального числа п. твер-
дження теореми не виконується, а отже, для цього п існу-
ють два різних розклади на прості множники
я =• Рі Рг ••• Рк = Яі • Яг • Яз ••• Ят- (0
Вважатимемо, що в лівій і правій частинах рівності
(1) співмножники розташовані у порядку зростання, тобго:
Рі = тіп (Рі, р2, ря, .... рк),
Яі = тіп (Яі. Яг, Яз Я*)-
Виберемо менше з чисел р1 та Нехай ним буде рх.
Тоді міркуємо так: Рі — множник лівої частини рівності (І).
39
Тому ліва частина ділиться на рг Але в такому разі
на нього повинна ділитися й права частина рівності. Отже,
добуток
Яі • Я2 ••• Я™
ділиться на просте число рх. За висновком з теореми З
маємо, що хоча б один із співмножників повинен ділитися
на рг. Нагадаємо, що всі числа
<7і> Яз< Яз< •••» Ят
прості. Тому за теоремою 1 одне з них повинно просто до-
рівнювати числу рг. Зрозуміло, що таким має бути най-
менше з них, тобто дг. Отже, рх = рх.
Зауважимо, що коли б меншим серед чисел рх та рх ви-
явилося ди то міркували б аналогічно, але в цьому випадку
переходили б, навпаки, від правої частини рівності (1) до
її лівої частини.
Скоротимо обидві частини рівності (1) на однакові числа
Рі — Яг Залишиться
Ра • Рз ••• Рк — Яз ' Яз ••• Ят‘
Аналогічно покажемо, що
Рг ~ Яз
Рз = Яз
Таким чином, припустивши існування для деякого нату-
рального числа п двох різних розкладів на прості множ-
ники, бачимо, що всі співмножники у лівій частині рівності
(1) збігаються з усіма співмножниками у правій частині
цієї рівності. Прийшли до суперечності з припущенням.
Теорему доведено.
40
§ 8. ВЛАСТИВОСТІ ДІЛЬНИКІВ
НАТУРАЛЬНОГО ЧИСЛА
Знаходити прості дільники даного натурального числа—
досить громіздка операція. З нею ви ознайомилися ще в
молодших класах. Звичайно тоді розкладалися лише неве-
ликі числа.
Наприклад:
738
369
123
41
1
2
З
З
41
738 = 2 • З • З 41
Спробуйте розкласти числа 27 217 або 75 851 (27 217 =
= 17 • 1601, 75 851 = 101 • 751).
Складність цієї задачі цілком очевидна.
Щоб спростити подібні задачі, математики вже давно
склали великі таблиці простих чисел та таблиці розкладів
на множники для складених чисел. У 19С 9 році з’явилася
таблиця Лемера, що доходила до 10 мільйонів. Пізніше
цю таблицю було ще більше розширено. Для великих
складених чисел у ній дається лише один — найменший
простий дільник. І цього цілком достатньо. Поділивши
складене число на його найменший простий дільник, діста-
немо нове число. За таблицею можна визначити, чи це
число просте, чи воно далі розкладається на множники.
Для другого випадку в таблиці подано найменший простий
дільник здобутого числа. Поділимо його на цей простий
дільник і т. д. Отже, за допомогою таблиці можна досить
швидко відшукати всі прості дільники навіть великих
натуральних чисел.
Дуже часто трапляється, що кілька із знайдених прос-
тих дільників деякого натурального числа рівні. Тоді
в розкладі цього числа множники, що повторюються, запи-
41
суємо у відповідних степенях. Наприклад, 243 = 3< Зх
X 3 • З = З4, або 6860 = 2 - 2 - 5 - 7 • 7 • 7 = 22 - 5х
X 73.
Взагалі,
« = Рі* • РІ‘ • Рз Рак. (2)
Ця остаточна формула розкладу натурального числа
на прості множники називається канонічним роз-
кладом числа. Тут к — кількість різних простих
дільників числа п. Для розкладеного вище числа 6 860
маємо: к = 3, р2 = 2, ах = 2, р2 = 5, а2 = 1, р3 — 7,
ос3 = 3.
Дуже важливо чітко розмежовувати поняття простого
дільника та дільника взагалі. Якщо знову звернемося до
числа 6 860, то легко бачити, що воно має лише три простих
дільники: 2, 5 та 7. А от дільників взагалі у цього числа—
24. Випишемо їх:
1, 2, 22, 5, 7, 72, 73, 2 • 5,- 22 • 5, 2 • 7, 22 • 7, 2 • 72, 2 - 73,
22 • 72, 22 • 73, 5 -7, 5 - 72, 5 - 73, 2-5-7, 22 - 5 - 7,
2 - 5 - 72, 22’- 5 • 72, 2 • 5 • 73, 22 • 5 • 73.
Як бачимо, всі ці дільники являють собою різні комбі-
нації чисел 2, 5 та 7 у степенях, що не перевищують відпо-
відно 2, 1 та 3.
Для кожного, хто знайомий з елементами комбінато-
рики, не становитиме великих труднощів довести таку тео-
рему.
Теорема. Кількість усіх можливих дільників даного
натурального числа п = р[‘ • р? • • • Р** дорівнює:
г(л) = (аі + 1)(«2+1)...(аЛ+1).
Суму всіх дільників даного числа п можна легко
обчислити з добутку:
(1 + рі + р? + • • • + рї‘) • (1 + Рг +
+ Рї + • • • + Рї’) • • • (1 + Рк + Рк + * ’ * + Рл*)-
43
Застосувавши тут формулу для суми членів геометрич-
ної прогресії, легко дістанемо таку теорему.
Теорема. Сума всіх дільників числа п я» М
X р1‘... ракк дорівнює
8(Л)«=
Р?+'-»
Рї —І
р'Ґ -,і
Рг — 1 ’ ” Рл —І *
Наприклад, для числа 3960 = 23 • 3а • 5 • 11
г (3960) - (3 1) - (2 -І- 1) • (1 + 1) • (1 + 1) = 48,
З3—1 5?—1 11?—1 _
3—1 ' 5—1 • Ц — 1 =
5(3960) = -^
= 15 • 13 • 6 - 12 = 14040.
Тут ми оперували всіма можливими натуральними діль-
никами даного числа, причому до дільників відносили саме
число. Але іноді доцільно розглядати лише і с т и н ц і
дільники даного числа, тобто всі його дільники, крім
самого числа. Сума істинних дільників натурального числа
дорівнює з(п) — п.
На закінчення зробимо два невеликих зауваження.
1. Якщо число р просте, то для нього формула (2) буде
такою:
Р = р.
Наприклад, візьмемо просте число 457. Тоді його роз-
клад на прості множники буде: 457 = 457, тобто к = 1,
Рі — 457, = 1.
2. Напишемо канонічний розклад для числа а — пг".
а = пг = р™1 • р™‘ ...Ркк.
Ми бачимо, що в канонічному розкладі числа, яке
е г-м степенем натурального числа, всі показники степеня
у простих множників повинні бути кратними г. Враховуючи
единість розкладу на прості множники, легко бачити, що
44
правильне й обернене твердження: якщо у канонічному
розкладі числа Ь = рі* • р92‘ - • р** всі показники
Р»......рА діляться на г, то число Ь є г-м степенем
натурального числа.
§ ». ДОСКОНАЛІ ЧИСЛА
Спробуємо безпосередньо підрахувати суму істинних
дільників кількох невеликих парних чисел.
п — 4 5 («) — п — 14-2 = 3
л = 6 з(п) — «=14-24-3 = 6
Сума істинних дільників дорівнює самому числу.
Продовжимо наші підрахунки.
п = 10 8 («) — «=14-24-5=8
«= 20 8(«)—«=14-24-44-54- 10 = 22
п = 28 8 («) — « = 1 4-24-44- 74- 14 = 28
Знову дістанемо, що з(«) — « = «.
Що ж це за числа, які мають таку чудову властивість?
Ці числа були відомі ще у Піфагорійській школі Старо-
давньої Греції. Знав їх і Евклід. Уже тоді вони дістали
назву досконалих чисел.
Таким чином, досконалими називаються числа,
для яких 8(«) = 2«, тобто числа, що дорівнюють сумі
своїх істинних дільників. Три найменші досконалі числа
6, 28, 496 були відомі ще до нашої ери.
Евклід першим довів, що коли 2"— 1 — просте число,
то число #=2П~І «(2"—1) досконале. Можна досить
швидко перевірити це. Підрахуємо суму дільників числа N
(при цьому, щоб скоротити запис, позначимо 2" — 1 = р).
8(М) =14-2 4-2а4-..-4-2я-а4-2л~14-р4-2р4-
4- 2ар 4- • • • 4- 2п-ар 4- г-’-їр = (1 4- р) • (1 4- 2 4-
45
+ 22 + • • • + 2”~2 + 2'1-1) = (1,+ р) • =
= (1+р).(2"-1),
але за нашим позначенням 1 + р = 2п.
Отже, 5 (А/) = 2" • (2" — 1) — 2 • (2"-1 • (2п — 1)) = 2Ц.
Якщо згадати числа Мерсенна, з якими ми ознайоми-
лися у § 5, то можна сформулювати таку теорему:
Теорема. Якщо Мп — просте число, то число N =*
= 2"-1 • Мп — досконале.
З часів Евкліда минуло близько двох тисячоліть, перше
ніж Ейлеру вдалося довести, що не існує ніяких інших
парних досконалих чисел, крім тих, які були знайдені
Евклідом. Отже, питання про знаходження парних доско-
налих чисел повністю зводиться до знаходження простих
чисел Мерсенна. Якщо, враховуючи це, знову повернутися
до § 5, то можна зробити .висновок, що нині відомо 23 пар-
них досконалих числа. Ось кілька з них:
коли п = 2, то М3 — З N =. 2і • 3 = 6;
коли п == 3, то М3 » 7 N = 2а • 7 = 28;
коли п = 5, то Л48 = 31 N = 24 • 31 = 496;
коли п <= 7, то = 127 М = 2е • 127 = 8128.
Наведемо для прикладу одне величезне досконале
число.
Візьмемо п » 107 (адже число М107, просте). Тоді N =
= 210в • Мі07 = 131 164 036 458 596 648 337 239 753 460
458 722 910 223 472 318 386 943 117 783 728 128.
Найбільшим з відомих нині досконалих Чисел е число
211212 . (211213 _ 1).
Оскільки ми досі не знаємо, скільки існує простих
чисел Мерсенна, то, зрозуміло, що не відомо й те, скільки
існує парних досконалих чисел.
Ще складнішим виявляється Питання про те, чи існують
непарні досконалі числа. Вже давно висунуто гіпотезу,
47
згідно з якою таких чисел нема взагалі. В усякому разі
встановлено, що коли непарні досконалі числа існують,
то вони мають бути надзвичайно великими.
Читачам, мабуть, буде цікаво ознайомитися ще з однією
Властивістю чисел, пов’язаною із сумою дільників.
Розглянемо два натуральних числа а і Ь. Може трапи-
тися так, що сума істинних дільників кожного з цих чисел
дорівнює другому числу, тобто
5(а) — а = Ь,
8(Ь) — Ь = а.
В цьому випадку числа а і Ь називаються д р у ж -
н і м и. Такими, наприклад, є числа 280 та 284 або 16416
та 17 296.
Значних успіхів у вивченні дружніх чисел досягнув
Ейлер. Він знайшов 65 пар таких чисел.
§ 10. ДЕЯКІ ПРОБЛЕМИ, ПОВ’ЯЗАНІ
З ПРОСТИМИ ЧИСЛАМИ
Ознайомлюючись з простими числами, ми вже зустрі-
чалися з кількома цікавими проблемами, що не розв’язані
ще й досі. Нагадаємо деякі з них.
1. Не відомо, скільки існує пар простих чисел-близ-
нят, тобто простих чисел, які є послідовними непарними
числами.
2. Ще не знайдено жодного простого числа Ферма
Рп = 22” 4- 1, коли п > 5.
3. Не відомо, скільки існує простих чисел Мерсенна,
тобто простих чисел типу Мп — 1, а отже, не відомо,
скільки існує парних досконалих чисел.
4. Досі не знайдено відповідь на питання про те, чи
існують непарні досконалі числа.
Перелік подібних проблем, які вже багато століть хви-
люють- математиків, можна значно продовжити. Особливо
48
багато проблем пов’язано з питаннями про те, у якому
вигляді можуть бути представлені прості числа. Деякі
з цих проблем ученим вдалося розв’язати, а деякі й досі
залишаються недоступними.
Наприклад, уже доведено такі твердження.
1. Серед простих чисел тільки число 2 й прості числа
типу 4к + 1 можна подати як суму двох квадратів нату-
ральних чисел, причому це зображення єдине.
Так, 2 = І2 4~ і2,
17 = 42 + І2,
41 = 52 + 42.
Але 23 х2 4- У2, бо 23 =- 4 • 5 + 3, тобто є числом типу
46 4- 3.
2. Жодне просте число, крім числа 2, не є сумою
двох кубів натуральних чисел.
3. Недавно (у 1962 році) було доведено, що існує
нескінченно багато простих чисел типу х2 4- У2 4-1. де х
та у — цілі числа.
Однак і досі не відомо, чи існує нескінченно багато
простих чисел, які є сумою кубів трьох цілих чисел.
Багато цікавих гіпотез у теорії чисел висунули відомі
англійські математики Г. Харді та Дж. Літлвуд. Ось дві
з них:
кожне досить велике натуральне число, яке не є
квадратом, можна подати як суму квадрата цілого
і простого чисел;
кожне досить велике натуральне число є сумою двох
квадратів цілих чисел і простого числа.
Другу з цих гіпотез розв’язав у 1959 році відомий
радянський математик Ю. В. Лінник, а перша залиша-
ється не розв’язаною й досі.
Досить цікавою, але теж поки не розв’язаною, є гіпо-
теза німецького математика А. Шінцеля, за якою для кож-
ного дійсного числа х^ 177 Існує хоча б одне просте
49
число р, що міститься між х та х + V х. Сам А. Шін-
цель перевірив цю гіпотезу для всіх чисел х, таких, що
117 < 2 • 107.
Тепер зосередимо увагу на трьох ще не розв’язаних
проблемах, які на перший погляд здаються досить елемен-
тарними.
1. Скільки існує простих чисел, усі цифри яких оди-
ниці?
Поки що відомо лише кілька таких чисел, наприклад,
11, 11111 та 11 111 111 111 111 111 111 111 (число, що скла-
дається !з 23 одиниць).
2. Скінченна чи нескінченна множина простих чисел,
перша й остання цифра яких дорівнюють одиниці, а всі
інші цифри —нулі? Таким, наприклад, є число 101.
3. Скільки існує простих чисел, серед цифр яких немає
жодного нуля?
Однією з найвідоміших проблем теорії чисел є проблема
Ґольдбаха. Історія виникнення її така.
Христіян Гольдбах (1690—1764 рр.) — математик, член
Петербурзької Академії наук, тривалий час листувався
з Леопардом Ейлером. У своєму листі від 7 червня 1742 року
він зауважив: «мабуть, кожне число, більше за одиницю,
є сумою трьох простих чисел». ЗО червня 1742 року Ейлер
відповів йому: «Те, що кожне парне число є сумою двох
простих чисел, я вважаю Цілком правильною теоремою,
хоча й не можу довести її». Це твердження і ввійшло в істо-
рію під назвою «проблема Гольдбаха».
Кожний, хто захоче перевірити -цю гіпотезу на прикла-
дах, переконається в емпірічній очевидності її.
Насправді, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 7 +
+ 3, 12 = 7 + 5, .... 40 = 37 + 3, ..., 100 = 97 + 3,
1000 = 809 + 191 тощо.
Якщо ж серйозно підійти до задачі, то вона надзвичайно
важка. Труднощі пояснюються тим, що поняття простого
і парного чисел визначаються у термінах множення, аі
в умові йдеться про операцію додавання.
51
Довгий час проблема Гольдбаха була зовсім недоступ-
ною. Та нарешті в 1930 році з’явилася блискуча праця
молодого радянського математика Л. Шнірельмана (1905—
1938 рр-), у якій було доведено, що кожне натуральне
число можна подати у вигляді суми не більш як 800 ОДО
простих чисел. Хоч цей результат здається мізерним, по-
рівняно із самою проблемою Гольдбаха, проте він був кро-
ком уперед. Трохи пізніше кількість доданків було змен-
шено до 67.
У 1937 році видатний радянський математик І. М. Вино-
градов, користуючись складними аналітичними методами,
довів, що кожне досить велике непарне число є сумою
трьох простих чисел.. Навіть існує таке число А/, почина-
ючи з якого, справджується це твердження. Воно дуже
велике: N — З’1’. Що ж стосується непарних чисел, мен-
ших за У, то можливість подання їх у вигляді суми трьох
простих чисел можна перевірити безпосередньо за допо-
могою скінченного числа простих арифметичних операцій.
Зрозуміло, що виконання цієї надзвичайно громіздкої
роботи під силу найновішим електроннообчислювальним
машинам.
Користуючись методами Шнірельмана та Виноградова,
математики розв’язали багато задач, до яких раніше не
можна було навіть і підступитися.
Слід згадати, зокрема, результат угорського математика
Реньї, пов’язаний з проблемою Гольдбаха. Він довів, що
кожне досить велике парне число можна подати як суму
двох чисел, одне з яких є простим, а друге має обме-
жену кількість простих множників.
Перед математиками стоїть дуже багато цікавих задач,
пов’язаних з простими числами. Кількість їх не зменшує-
ться, а навпаки, систематично зростає.
Саме це систематичне зростання кількості цікавих про-
блем, пов’язаних з простими числами, є тим потужним
магнітом, який уже багато століть притягає молодих мате-
матиків.
52
ПОДІЛЬНІСТЬ
ЧИСЕЛ
§ 1. ОПЕРАЦІЯ ДІЛЕННЯ
Візьміть два довільних цілих числа. Знайдіть їх суму
або добуток. В обох.випадках ви знову дістанете ціле число.
Але при діленні це трапляється не часто. Істотно, що з цієї
причини операція ділення для цілих чисел найскладніша
з основних арифметичних дій.
У попередньому розділі ми вже зустрічалися з поняттям
«натуральне число а ділиться на натуральне число Ь», тобто
існує натуральне число <7, таке, що
а = Ь • д. (1)
У цьому випадку д називається часткою від ді-
лення а на Ь. Зрозуміло, що при цьому число Ь і всі його
дільники будуть дільниками числа а.
А тепер нехай число а не ділиться на Ь. Погодьтеся,
що для довільних цілих чисел а і Ь цей випадок буде зустрі-
чатися значно частіше. Те, що а не ділиться на Ь, розумі-
тимемо так: існуй ціле число д, таке, що
Ь • д < а < Ь • (<7 + 1). (2)
Усі добре знають, що в цьому випадку йдеться про ді-
лення з остачею. Виконуючи ділення безпосередньо
у «стовпчик», остачу завжди легко знайти.
Наприклад, а — 149, Ь = 35.
149 | 35 35 • 4 < 149 <35-5.
140 4 Остача дорівнює 9.
~9 149 = 35 • 4 + 9.
Взагалі, коли а не ділиться на Ь, то ці числа можна
подати у вигляді:
а Ь • д + г. (3)
Тут д — так звана неповна частка, а г —
остача від ділення а на Ь. При цьому г ~ а — Ь - д.
54
З лівої та правої частин співвідношення (2) легко ба-
чити, що
0 < а — Ь • д,
а — Ь • (д + 1) < 0
тобто 0 < а — Ь • д <Ь.
Ми дістали важливу нерівність: 0 < г < Ь.
Відразу зазначимо, що під цю загальну схему підхрдить
і той випадок, коли а ділиться на Ь. З рівності (1) бачимо,
що в цьому випадку г = 0,— неповна частка е просто
часткою від ділення а на Ь.
Звідси можна сформулювати таку основну теорему.
Теорема. Для довільних двох натуральних чисел а
і & можна знайти такі цілі числа ц та г, що а =• Ь • д +
+ г, причому
0 < г с Ь. (4)
Отже, д та г визначаються однозначно.
Здобутий результат можна добре пояснити на числовій
осі. Між її точками та множиною дійсних чисел встанов-
лено взаємно однозначну відповідність, тобто кожному
дійсному числу відповідає єдина'точка числової осі і, нав-
паки, кожній точці на осі відповідає єдине дійсне число.
Отже, зафіксуємо на осі точку, що відповідає натураль-
ному числу а. Починаючи з нуля, відкладатимемо відрізки
по Ь одиниць. Нехай до точки з координатою а нам удалося
укласти д таких відрізків, а наступний (д + 1)-й відрізок
уже перейшов за точку а.
Довжину відрізка, обмеженого точками з координатами
д Ь та а, позначимо через г.
Отже, а = Ь • д + г та 0 г < &.
Зазначимо, що коли а < Ь, то д = 0 і г - а.
Далі нам доведеться застосувати кілька очевидних
фактів.
1. Кожне натуральне число ділиться на одиницю й на
само себе.
55
2. Якщо а ділиться на Ь, аЬ ділиться на с, то й а ді-
литься на с.
3. Якщо натуральні числа а^, аг, .... ап діляться на Ь,
а кг, ...» кп — довільні цілі числа, то й сума кі'й1 +
+ к2 • аг + ••• + кп • ап ділиться на Ь. Аналогічно й для
різниці.
§ 2. НАЙБІЛЬШИЙ СПІЛЬНИЙ ДІЛЬНИК
ТА НАЙМЕНШЕ СПІЛЬНЕ КРАТНЕ
Для двох довільних натуральних чисел а і Ь завжди
можна знайти їхні спільні дільники (числа,
на які діляться і а, і Ь) та спільні кратні (числа, що діляться
на а й на Ь).
Так, для чисел 24 та 66 спільними дільниками будуть:
1, 2, 3, 6, а спільними кратними — 264, 528,
1320, 2640, 528000...
Цілком зрозуміло, що кількість спільних дільників
для двох чисел завжди обмежена, у той час, як кількість
усіх спільних кратних для них нескінченна.
Серед усіх спільних дільників та спільних кратних двох
чисел а і Ь математиків найбільше цікавлять найменше
спільне кратне та найбільший спільний дільник.
Надалі ми будемо користуватися такими позначеннями:
К(а, Ь) — найменше спільне кратне чисел а і Ь\ О (а, Ь)
або просто (а, Ь) — найбільший спільний дільник чисел
а і Ь.
У тих випадках, коли цілком зрозуміло, прощо йдеться,
писатимемо просто К і £).
Відомо, що для довільних натуральних чисел а і Ь (а>
>Ь) одним із їхніх спільних дільників завжди буде 1,
а одним із спільних кратних — добуток а Ь.
Звідси легко зробити висновок, що
1 < П(а, Ь) Ь,
а С К.(а, Ь)^а Ь.
56
Ви, мабуть, добре пам’ятаєте, як знаходять А і £>, роз-
кладаючи числа а і & на прості множники. Але, як ми вже
бачили, операція розкладу чисел на прості множники до-
сить громіздка. Ось чому доцільно розглянути інший не-
складний і дуже цікавий метод знаходження К. і £>. Про
нього йдеться у наступному параграфі. А зараз ми спини-
мося на деяких важливих властивостях найбільшого спіль-
ного дільника та найменшого спільного кратного.
Насамперед звернемо увагу на те, що ці поняття можна
легко узагальнити й на випадок п чисел, тобто ввести
Л(а1, а2, ..., а„) та К(аг, а.,, ..., ап). Щоб знайти найбіль-
ший спільний дільник кількох чисел, можна спочатку
знайти його для якихось двох з даних чисел, потім знайти
найбільший спільний дільник знайденого і якогось тре-
тього числа, далі знайти найбільший спільний дільник знай-
деного удруге числа і якогось четвертого із даних чисел
і т. д. Тобто для знаходження О(аг, а», ..., ап) можна ко-
ристуватися такою властивістю: Л(а, &, с) = І) ((а, Ь), с).
Аналогічно визначається і найменше спільне кратне
кількох чисел.
Теорема 1. Найменше спільне кратне К двох даних
натуральних чисел а \ Ь є дільником будь-якого іншого
спільного кратного цих чисел.
Доведення. Нехай Кі — довільне спільне кратне
чисел а і Ь, що відрізняється від К- Тоді Кл > К (адже
К — найменше спільне кратне). Покажемо, що ділиться
на К. Доведення проводитимемо методом від супротивного.
Нехай /(і не ділиться на К. У цьому випадку маємо
(див. теорему на стор. 55): Кі = К д 4- г (0 < г < А).
Звідси г = Кі — К • ц-
Обидва числа Кі і К діляться і на а, І на Ь, бо це їх
спільні кратні. Тоді й г ділитиметься на а та на Ь, тобто г
є спільним кратним чисел а і Ь. Але ж г < К.
Маємо суперечність, бо дістали спільне кратне чисел а
і Ь, менше за їх найменше спільне кратне. Отже, припу-
щення про те, що Лі не ділиться на /(, було неправильним.
57
Теорему доведено. Наприклад, для чисел 25 і 40 ми
знайшли два спільних кратних 400 і 1000. У зв’язку з тим,
що 1000 не ділиться на 400, робимо висновок, що 400 не б
найменшим спільним кратним цих чисел, бо число 400 не
задовольняє цієї теореми.
Справді (25, 40) — 200.
Зауважимо, що доведена теорема справджується І для п
чисел.
Теорема 2. Найбільший спільний дільник двох даних
натуральних чисел а і Ь ділиться на будь-який інший
спільний дільник цих чисел.
Доведення. Нехай Лх, Л2, .... Л„ — усі спільні
дільники чисел а і Ь. Зрозуміло, що й а, і Ь е спільними
кратними чисел Лх, Л2, ..., Ля.
Знайдемо Я (Лх, Л2, .... Ля). За теоремою 1 К (Лх, Л2,
..., Ля) є дільником і числа а, і числа Ь. Таким чином,
К (Пг, ..., Ля) — також спільний дільник даних чисел
а і Ь й до того ж найбільший, тобто К (Лх, Л«, .... Ля) —
= Л(а, Ь).
Отже, Л (а, Ь) — найменше спільне кратне всіх діль-
ників чисел а і Ь (тобто це число ділиться на будь-який
із спільних дільників а і Ь). Теорему доведено.
Дуже важливою є така формула:
К • Л = а Ь. (1)
Доводиться вона дуже просто. Тому надаємо можли-
вість читачам самостійно зробити це.
З цієї формули випливає, наприклад, що коли числа
а 1 Ь взаємно-прості, то К(а, Ь) — а • Ь, бо для таких чисел
як відомо, Л = 1.
Наведена формула важлива ще й тому, що завдяки їй,
знаючи Л (а, Ь), можна безпосереднім діленням знайти
К (а, Ь):
58
§ 3. АЛГОРИТМ ЕВКЛІДА
Тепер ознайомимося з практичним методом знаходження
найбільшого спільного дільника двох чисел, так званим
алгоритмом Евкліда.
Нехай а і Ь дані натуральні числа (а > Ь).
Оскільки а = Ьд + г, то г — а — Ь . д. Легко бачити,
що кожний спільний 'дільник чисел а і Ь буде також діль-
ником і числа г. Отже, множина всіх спільних дільників
чисел а і Ь збігається з множиною всі» спільних дільників
чисел Ь та г.
Таким чином, маємо:
Р(а, Ь) « В(Ь, г). (2)
Значить, знаходження Р(а, Ь) звелося до знаходження
О(Ь, г). А це значно легше, бо маємо справу з меншими
числами (Ь < а та г < Ь).
Наприклад, а = 2604, Ь — 756. Треба знайти Р(а, Ь).
Безпосереднім діленням знаходимо, що д = 3, а г —
= 336, тобто 2604 = 756 • 3 4- 336. Звідси з рівності (2)
маємо, що Р (2604, 756) = Р (756, 336). Нашу основну
задачу замінено аналогічною, але з меншими числами.
Зрозуміло, що цей процес можна продовжити
756 = 336 • 2 + 84.
Тоді Р (756, 336) = В (336 • 84).
Оскільки 336 = 84 • 4, то Р (336, 84)« Р (84,0) = 84.
Таким чином, Р (2604, 756) = Р (756, 336) = Р (336,-
84) = Р (84, 0) = 84. Задачу розв’язано.
Тут ми скористались очевидним фактом, що Р (а, 0) = а.
У загальному вигляді послідовність знаходження
Р(а, Ь) (тобто алгоритм Евкліда) така:
а=Ь- ді + гі,
гг-д2 + г2,
О = "І" 'з. /о\
59
Г«_8 = гп_! • дп + г„,
гл_і = гп • дп+і-
Тут у кожному рядку ми виконуємо ділення, тобто зна-
ходимо неповну частку й остачу.
Остання відмінна від нуля остача і буде найбільшим
спільним дільником чисел а і Ь:
О (а, Ь) => гл.
У декого може постати запитання: а чи не виявиться
ця послідовність операцій нескінченною так, що ми ніколи
не прийдемо до нульової остачі?
Щоб відповісти на це запитання, нагадаємо, що остача
має бути меншою, ніж дільник. Таким чином, < 6, г2 <
< гя < гг........
Бачимо, що остачі утворюють спадну послідовність до-
датних чисел.
Зрозуміло, що, виконавши скінченну кількість опера-
цій, обов’язково дістанемо нульову остачу.
Те, що О (а, Ь) = гп, стає зрозумілим з таких мірку-
вань. Оскільки взагалі Р (а, &) = Р (&, г), то з алгоритму
Евкліда маємо Р(а, Ь) = Ь(Ь, гх), О(Ь, гх) = Р (гх, г2),
О(Л, г2) = Р(г2, г8) і т. д.
Остаточно: Р (а, Ь) = Р (6, гх)« Р (гь г2) = Р (г2, г3) =
= . . . = Р (гя_і, Гп) ~ В (гп> 0) = Гп-
За допомогою алгоритму Евкліда досить легко можна
знайти найбільший спільний дільник навіть для великих
чисел.
Наприклад, знайдемо Р (76 602, 31 926).
76 602 = 31 926 • 2 4- 12 750,
31 926 = 12 750 • 2 + 6 426,
12 750 = 6 426 • 1 + 6 324,
6 426 = 6 324 • 1 + 102,
6 324 = 102 • 62 4- 0.
Таким чином, Р (76 602, 31 926) 102.
60
А тепер, користуючись рівністю (1), ми легко знайдемо
найменше спільне кратне цих чисел:
^ = = 76602 31 92(І =“ 7Б1 • 31 926 = 23975426.
§ 4. ПРО ОДНУ ВАЖЛИВУ ВЛАСТИВІСТЬ
£) (а, Ь)
З алгоритму Евкліда можна безпосередньо вивести одну
важливу властивість найбільшого спільного дільника двох
чисел.
Теорема. Для довільних натуральних чисел а і Ь
можна знайти такі цілі (додатні або від’ємні) числа к
та І, що
О (а, Ь) = к • а 4- І • Ь.
Для доведення ще раз нагадаємо алгоритм знаходження
Р (а, Ь).
а=Ьді + /і,
Ь - Ш + га,
Гі = г2<7з + г3,
^л-2 = ^п— 1 * Яп 4" гп>
І'п—1 = ’ Яп+1'
З першого рядка бачимо, що і\ = а — Ь • дг
Звідси легко знайти цілі числа кг та 11г такі, що г} =
»= кі • а + 4 • Ь. Тут кх — 1, 4 = —дх.
З другого рядка маємо: г2 — Ь — д2 • г\.
Підставимо сюди вираз, який задає г±. Тоді:
га =« 6 — <7а • (£і • а 4- 4 • 6) = & — <7г • Аі • а —
— дг . 4 • Ь = (—д2 кЛ а + (1 —д2 • Іг) • Ь.
У зв’язку з тим, що (—д2 • кг) та (1 — д2 • /а) — цілі
числа, то, позначивши їх відповідно через к2 і /2, дістанемо:
га = к2 • а 4- /а • Ь.
«1
Зробивши аналогічні перетворення для г9, знайдемо
пару цілих чисел к3 та 19, таких, що г9 =* а 4- /» • Ь.
І далі,
гі & к9 • а 4- /4 « Ь,
Гп—1 = * Я 4* ^Пі-І '
гл = Лп • о 4” 4» ‘
Остання рівність і доводить нашу теорему.
Розглянемо приклад: а = 108, Ь = 84.
Спочатку обчислимо Р (108, 84):
108 = 84 • 1 + 24,
84 = 24 • З 4- 12,
24 = 12 • 2.
Отже, Р (108, 84) - 12.
Тепер знайдемо цілі числа к і /, такі, що 12 = 108 • Л4»
4- І • 84.
З першого рядка алгоритму маємо: 24=108—ї х
X 84, з другого: 12 = 84 — 3 • 24. Таким чином, 12 =
= 84 — 3 • (108 — 1 . 84) = 1 • 84 — 3 • 108 4- 3 • 84 =
= (—3) • 108 4- 4 • 84, тобто к = — З, І = 4.
Сформулюємо наслідок із щойно доведеної теореми.
Якщо числа а і Ь взаємно-прості, то можна знайти такі цілі
числа к та І (додатні або від’ємні), що к • а 4- І • Ь = 1.
Цей наслідок цілком очевидний, бо для взаємно-прос-
тих чисел найбільший спільний дільник дорівнює 1.
Знову звернемося до числового прикладу.
Візьмемо два взаємно-простих числа а = 94 і Ь = 75.
Тоді
94 = 75 • 1 4- 19,
75 = 19 • 3 4- 18,
19 = 18 • 1 4- 1,
18 = 1 • 18.
С2
З першої рівності маємо: 19 = 94 — 1 -75; з друг*#
18 = 75—3. 19 = 75 — 3(94—1 . 75) = (—3) • 94 + 4 • 75;
з третьої: І = 19 — 1 • 18 = (94 —1 • 75) —1 . ((—3) • 94 +
+ 4 • 75) = 1 -94 — 1 .75 + 3.94—4.75 = 4.94 — 5.75.
Отже, 1 = 4 • 94 + (—5) • 75.
§ 5. ЛАНЦЮГОВІ ДРОБИ
Тепер, користуючись алгоритмом Евкліда, ознайоми-
мося з поняттям ланцюгового дробу. Для цього знову запи-
шемо алгоритм у дещо зміненому вигляді, а саме: обидві
частини першої рівності поділимо на Ь, другої — на г\,
а обидві частини третьої рівності — на га і т. д. Дістанемо:
£ = <7і + .
= +
га 43 г, ’
Тут ми вже маємо звичайні дроби, чисельники й знамен-
ники яких є натуральними числами.
Перше із знайдених співвідношень можна записати
у такому вигляді:
Проте з другого співвідношення маємо: + у-.
Зіставляючи ці дві рівності, дістанемо:
63
А з третього співвідношення маємо:
г2
Міркуючи так само і далі, дістанемо:
а „ ( 1
у “ 7і Н-----------------
Чі 4--------
<7з4
<71 +-----1
<75 +
1
1
1
4п+і
19
75’
18
19*
1
18 *
Права частина цього виразу і є найпростіший лан-
цюговий дріб. Його іноді також називають непе-
рервним дробом. Скорочено цей дріб позначають так:
у = (<7і> • • • > <7/1+11-
Повернувшись до вже розібраного прикладу (а = 94,
Ь = 75), можна записати:
94=14
75
19“ д
19 1 -і
Ї8= 14
“=18.
64
То^ й= 1 + І = 1 +-Ч-8= 1 +—Ч—
19 3 + Г9 +ГГГ
1 + Ї5
Таким чином, у^ = [1, 3, 1, 18].
Отже, ми ознайомилися із скінченними ланцюговими
дробами. Але існують і нескінченні ланцюгові дроби.
Розглянемо, наприклад число /15.
]/І5==3 + -; а > 1.
Звідси
, 1 /15 + 3
/15-3 6
о 6 /15 4-3
Р /Ї5 —З 1
. _1 _ /Ї54~3
7 /15 — 3
2
р
£
7
2
6
6
Далі все повторюється. Дістанемо нескінченний періо-
дичний ланцюговий дріб:
/15 =3 4-----------------
6 4-
Таким чином,
/15 = (3, (1, 6)).
З 8-6
69
§ в. ДЮФАКТОВІ РІВНЯННЯ
Мабуть, ви нерідко мали справу зрівняннями, розв’язки
яких треба було шукати в цілих числах. При цьому дуже
часто буває доцільним зосередити увагу на знаходженні
дільників лівої та правої частин рівняння. Адже саме ді-
лення є найбільш цікавим, коли йдеться про цілі числа.
Наприклад, знайдемо цілі розв’язки рівняння:
Узявши до уваги, що х 0 та у ф 0, зробимо деякі
перетворення: 4х + 4у = ху або ху — 4х — 4у = 0.
Спробуємо розкласти ліву частину на множники. Для
цього додамо до обох частин рівняння число 16. Діста-
немо:
ху — 4х — 4у + 16 = 16.
Звідси
(х -4) (у- 4) = 16.
Таким чином, добуток двох цілих чисел дорівнює 16.
Якими ж при цьому можуть бути співмножники? Це
легко з’ясувати.
Цілими дільниками числа 16 є: ±1, ±2, ±4, ±8,
±16.
Отже, всі цілі розв’язки цього рівняння можна знайти,
розв’язавши такі системи рівнянь:
п р— 4= 1-
‘) Ь-4= 16;
21 Iх 4 = 2,
\у — 4 = 8-,
о\ / х 4 = 4,
•5) І у — 4 = 4;
4)
5)
6)
х — 4 = 8,
і/-4 = 2;
х — 4= 16,
У — 4= 1;
(х — 4= — 1,
(У —4 = -16;
*/2 3і
67
7)
х — 4 = —2,
У-4 = -8;
9)
х — 4= _ 8,
у-4 = -2;
Ю)
х — 4= —16,
У — 4= —1.
Так ми знайдемо десять пар цілих значень для х і у.
Зауважимо, що розв’язок системи 8) х = 0, у = 0 не за-
довольняє наше рівняння.
Таким чином, рівняння -- Н---= -^ має дев ять цілих
розв’язків: (5, 20); (6, 12); (8, 8); (12, 6); (20, 5); (3, —12);
(2, —4); (—4, 2); (.—12, 3).
Подібні рівняння відіграють у математиці значну роль.
При цьому дуже цікавим і важливим є питання про кіль-
кість розв’язків кожного окремого рівняння. Адже ми
щойно бачили, що встановити кількість цілих розв’язків
за зовнішнім виглядом рівняння дуже важко.
Це питання математики вивчають здавна. Перші най-
глибші праці належать видатному давньогрецькому мате-
матику Діофанту й відносяться до III—IV століть нашої
ери. А один дуже важливий клас рівнянь навіть носить
його ім’я.
Діофантове рівняння — це алгебраїчне рів-
няння з цілочисловими коефіцієнтами від двох чи більше
змінних, причому знаходять * лише цілі або раціональні
його розв’язки.. Кількість змінних у діофантовому рівнянні
більша, ніж число рівнянь.
Найпростіше з них — лінійне з двома змінними:
а х + Ь у => с.
(1)
Тут а, Ь, с — дані цілі числа.
Множина розв’язків цього рівняння або порожня, або
нескінченна. Щоб розв’язати його, скористаємося власти-
востями найбільшого спільного дільника двох чисел.
Нехай О (а, Ь) = Л.
69
Ліва частина рівняння ділиться на б/, бо на ділиться
кожний з доданків. Тоді на (і повинна ділитися й права час-
тина. Отже, це рівняння може мати розв’язки лише в тому
випадку, коли с ділиться на й.
Припустимо, що ця умова виконується, тобто с = (І д.
У § 4 цього розділу було доведено теорему, за якою для
довільних цілих чисел^й і Ь можна знайти такі цілі числа
к та /, що а • к + Ь 1 = ^1 подано алгоритм знаходження
цих чисел.
Звідси легко бачити, що пара цілих чисел к д та І X
X д буде одним з розв’язків діофантового рівняння, бо
а(к д) + Ь(1 д) = д(а к + Ь І) = д й = с.
Отже, х0 = к д, у0 = І д. Назвемо цей розв’язок
частинним.
Тепер шукатимемо якийсь інший розв’язок рівняння
(1). Позначимо його через (хх, ух).
Знайдемо різницю двох рівностей
_______а • Хі + Ь • у і = с
_______а - х0 + Ь- у0 = с
а (хх — х0) + Ь їм. — Уо) = °-
Таким чином, пара цілих чисел х* = хг — х0 та у* ==
= Уі — Уо повинна бути розв’язком однорідного рівняння
ах + Ьу = 0 (однорідним називається рівняння, права
частина якого дорівнює нулю).
Щоб знайти розв’язки однорідного рівняння, поділимо
обидві його частини на (і й позначимо ~ = /Пі, ~ = т2.
Дістанемо рівняння: іщх = — т2у.
Легко бачити, що пг1 та т2— цілі, взаємно-прості числа.
Отже, останнє рівняння матиме розв’язки, якщо х буде
кратний числу пг2, а у — числу Тому розв’язками цього
рівняння будуть цілі числа:
х = к • т2, у = —к • /Пі (тут к — довільне ціле число).
70
Ми дістали:
, Ь , а
Хі - х0 = , уг—у^—к--^.
Таким чином, загальний цілий розв’язок рівняння (1):
х = Хо + к • > У = У о —
Тут (х0, у0) — частинний розв’язок, який можна знайти,
користуючись алгоритмом Евкліда, а к — довільне ціле
число.
Наприклад, розв’яжемо рівняння 108х + 84у = 60.
У § 4 пара чисел 108 та 84 вже розглядалася. Було
знайдено, що О (108, 84) = 12, а також 12 = (—3) 108 +
+ 4 84.
Права частина рівняння, тобто число 60, кратна най-
більшому спільному дільникові чисел 108 та 84 (бо 60 =
= 12 5). Отже, запропоноване рівняння має безліч ці-
лих розв’язків. Спочатку знайдемо частинний розв’язок:
х0 = (—3) 5 = —15, у0 = 4 5 = 20.
Тепер легко обчислити загальний розв’язок нашого
діофантового рівняння:
х= —15 + £ -^=76—15,
у = 20 — к-= 20 — $к
(тут к — довільне ціле число).
§ 7. ВЛАСТИВОСТІ ОСТАЧ
Перед тим, як переходити до ознайомлення з деякими
властивостями остач, зауважимо, що іноді доцільно ко-
ристуватися від’ємними остачами. Звідки ж з’являються
вони?
71
ікііііІгІїііШМіНіїіиІПіІііІііІіІііііМ^і
Мабуть, ще з молодших класів усі добре пам’ятають,
що ділити два цілих числа можна і з надлишком, і з недо-
стачею. Так, 27 = 4- 6 + 3 = 4 7 — 1. У першому
випадку маємо остачу 3, а у другому (—1).
Справді, значно доцільніше говорити, що число 49
у результаті ділення на 10 дає остачу — 1, ніж говорити
про громіздку остачу 9.
У загальному випадку маємо:
а = Ь 7 + г = Ь ((? + 1) — г*.
Тут г — додатна остача, а — г* — від’ємна. Легко ба-
чити, що г = Ь — г*.
Таким чином, від від’ємної остачі легко перейти до
додатної, якщо до неї додати число, що дорівнює дільни-
кові, і навпаки.
Розглянемо кілька цілком очевидних властивостей остач.
Якщо число а± внаслідок ділення на число Ь дає остачу
а число а2 остачу г2, то:
аг + а2 дасть остачу і\ + га,
ах — а2 дасть остачу гх — г2,
аг а2 дасть остачу гх г2
при діленні на те ж саме число Ь.
Якщо ж, користуючись останньою властивістю, число
множити само на себе, то відповідно змінюватиметься й
остача. Отже, можна назвати ще одну властивість:
число ах дасть у результаті ділення на Ь остачу г£.
Цю властивість особливо зручно використовувати тоді,
коли дане число при діленні на якесь інше число дає остачу
1 (або—1). У такому разі будь-який натуральний степінь да-
ного числа при діленні на те саме число даватиме в остачі 1.
Вміння користуватися властивостями остач значною
мірою допомагає розв’язувати багато числових задач.
Наприклад: знайдемо остачу від ділення числа 2100 на 7.
Легко бачити, що 2100 = 2" 2 = (23)33 2 = 833 2.
Число 8 у результаті ділення на 7 дає остачу 1. Тоді й
4 8-6
73
833 також даватиме остачу 1 при діленні на 7. Число 2 вна-
слідок ділення на 7 дає остачу 2, бо 2 = 7 0 + 2. Отже,
добуток цих чисел, тобто само число 2100, при діленні на
7 дасть добуток остач 1 2 = 2.
Як бачимо, задачу вдалося розв’язати без будь-яких
труднощів.
Розглянемо довільне натуральне число п. При діленні
на 5 воно може давати остачі: 0, 1,2, 3, 4. Тоді число п2
даватиме остачі відповідно: 0, 1, 4, 4, 1 (тут у двох остан-
ніх випадках ми усно відняли від остач, які дістали, число,
кратне дільникові, тобто звели остачі до основного вигляду).
А число п4 даватиме такі остачі: 0, 1, 1, 1, 1.
Дістали цікавий результат. Якщо число п не ділиться
на 5, то я4 при діленні на 5 дає остачу 1, тобто коли
п =+ 5й, то число (п* — 1) ділиться на 5.
Цей результат невипадковий. Його ми пояснимо в на-
ступному параграфі. А тепер покажемо, що коли и 11,
то число (п10 — 1) ділиться на 11.
Знайдені остачі виписуватимемо у стовпчик.
п, п2 п4 п8 и10 = п2 • па
1111 1
2 4 5 3 1
3 9 4 5 1
4 5 3 9 1
5 3 9 4 1
6 3 9 4 1
7 5 3 9 1
8 9 4 5 1
9 4 5 3 1
10 1 1 1 1
Отже, при довільному п число п10 або ділиться на 11,
або при діленні на 11 дає остачу 1.
Тепер легко переконатися, що, наприклад, число
1 458 023 567 964 023 не може бути десятим степенем нату-
рального числа, бо при діленні на 11 воно дає остачу 5.
74
§ 8. КОНГРУЕНЦІЇ.
МАЛА ТЕОРЕМА ФЕРМА
У попередньому параграфі ми оперували не самими чис-
лами, а їх остачами відділення на якесь дане число. І іноді
це дуже зручно, якщо два числа а і Ь, які при діленні на
деяке число т мають рівні остачі, ототожнюватимуться.
Такі два числа називають порівнянними (конгруентними)
за модулем т.
Цьому поняттю у теорії чисел приділяється велика
увага. Так ми прийшли до нового типу відношень між
числами конгруенцій. Уперше їх увів Гаусе.
Два числа а і Ь називаються конгруентним^
за модулем т, якщо при діленні на т вони дають
однакові остачі.
Це записується так:
а = 6(тосі т).
Можна дати й інше означення.
Числа а і Ь називаються конгруентними за модулем т,
якщо їх різниця ділиться на т.
Легко бачити, що ці два означення еквівалентні.
Наведемо кілька прикладів:
26 = 1 (тосі 5),
40 = 68 (тосі 7),
—23 7 (той 10),
14 = 10 (тосі 4).
Зручні конгруенції тим, що для них зберігаються влас-
тивості звичайних числових різностей.
Так, дві конгруенції за одним і тим самим модулем
можна почленно додавати, віднімати, множити. Далі до
обох частин тієї чи іншої конгруенції можна додавати (або
віднімати) довільне ціле число; ліву й праву частини кон-
груенції можна множити на одне й те саме натуральне
число, підносити до натурального степеня. Ділити обидві
75
частини конгруенції можна лише на те натуральне число,
яке буде взаємно-простим з модулем т.
Важливо зазначити ще й такі властивості:
кожне ціле число конгруентне саме собі за будь-яким
модулем;
якщо а = &(той т) і Ь = с(той т), то а $ с(той т).
Конгруенції зручні ще й тим, що застосування їх зав-
жди значно скорочує запис того чи іншого факту про поділь-
ність чисел. Наприклад, результати, здобуті у поперед-
ньому параграфі, можна записати за допомогою конгруен-
цій так:
якщо п 54, то п* = 1 (тосі 5);
якщо п Ф 11 Аг, то п10 = 1 (тосі 11).
Останні співвідношення є окремими випадками однієї
важливої теореми.
Мала теорема Ферма. Якщо натуральне число а
не ділиться на просте число р, то ар-1 = 1 (той р).
Доведення. Насамперед нагадаємо, що коли число
не кратне р, то при діленні на р воно може давати (р— 1)
різних остач, а саме: 1, 2, 3, ..., (р — 1).
Розглянемо числа: а, 2а, За, ..., (р — 1)а.
З умови теореми легко зробити висновок, що жодне
з цих чисел не ділиться на р. Крім того, серед них немає
ніяких двох чисел, які були б конгруентними за модулем
р (бо інакше їх різниця ділилася б на р). Отже, всі ці числа
при діленні на р даватимуть різні ненульові остачі. Але
їх усього р— 1. Таким чином, знаходячи остачі від ді-
лення чисел а, 2а, ..., (р — 1)а на р, ми перебрали у де-
якому порядку числа 1, 2, 3, .... (р — 1).
Отже,
а • 2а За ... (р — 1)а = 1 • 2 • 3 ... (р — 1)Х (той р).
Звідси
1-2-3 (р—1). ар~х = 1 • 2-3 ...(р— 1) X
X (тойр).
77
У зв’язку з тим, що число 1 2 • 3 ... (р — 1) (тосі р)
взаємно-просте з модулем р, обидві частини конгруенції
можна скоротити на нього. Тоді дістанемо:
а”'1 = 1 (тодр).
Теорему доведено.
На закінчення зауважимо, що мала теорема Ферма
була значно узагальнена Еклером. В математичній літе-
ратурі вона зустрічається в узагальненому вигляді під
назвою теорема Ферма—Ейлера.
§ 9. ОЗНАКИ ПОДІЛЬНОСТІ
Властивості остач та конгруенцій стануть у пригоді при
виведенні ознак подільності.
Розглянемо довільне (п + 1)-цифрове число
№ ________1 ...
Отже, число N має вигляд:
N = Оо + «і 10 + а2102 +----1- ал_! • 10"-1 + ап • 10".
Нас цікавить питання: як знаходити остачі від ділення
N на деякі невеликі числа, не виконуючи ділення безпо-
середньо.
Для цього скористаємося тим, що остача від ділення
суми чисел на якийсь дільник дорівнює сумі остач, які
дістають від ділення на це саме число кожного з доданків.
1. Подільність на 2.
Легко бачити, що 10 = 0 (той 2).
А тому й 10* = 0 (тосі 2).
Звідси випливає, що всі доданки, починаючи з другого,
у результаті ділення на 2 даватимуть нульову остачу.
Таким чином,
N = а0(птосІ 2).
78
Отже, остача від ділення числа ЛГна 2 дорівнює остачі,
яку дістанемо при діленні на 2 останньої цифри числа N.
Ця ознака подільності на 2 всім добре відома.
2. Подільність на 3.
Зауважимо, що 10 =1 (тосі 3).
А тому й 10* = 1 (тосІЗ).
Звідси легко бачити, що
йі • 10 = Яі(тосі 3),
а2 • Ю2 = а2 (тосі 3),
а,, • 16" = ап (тосІЗ).
Таким чином, N = а0 + + аг + ••• + ап (тосі 3).
Отже, остача від ділення числа У на 3 дорівнює остачі
від ділення на 3 суми цифр числа N.
Неважко переконатися, що аналогічне правило справ-
джується й для знаходження остачі від ділення числа N
на 9.
3. Подільність на 11.
Насамперед зазначимо таке:
10 = — 1 (тосі 11)
102 = 1 (тосі 11)
103 = —1 (тосі 11)
Звідси знаходимо, що
N = а0 — Оі + аг — а3 + ... + (—1)" ап (тосі 11).
Отже, остача від ділення числа N на 11 дорівнює:
г = (а0 + аг + + ...) — (йі + а3 + а6 +...),
тобто різниці між сумами цифр, які стоять на непарних
і парних місцях у числі ЛГ, якщо лічити справа наліво.
Наприклад, N = 36 028 461 265.
Тоді г = (5 + 2 + 6 + 8 + 0 + 3) — (6+1+4 +
+ 2 + 6) = 24 — 19 = 5.
79
Або: N = 2 667 543.
Тоді г = (3 + 5 + 6 + 2) — (4 + 7 + 5) = 16 — 16 =»
«= 0, тобто число 2 567 543 ділиться на 11.
Таким чином, ознака подільності на 11 така: число
ділиться на 11 тоді і тільки тоді, коли на 11 ділиться сума
його цифр, узята із знаками, що строго чергуються.
4. Подільність на 7.
Ознака подільності на 7 складніша для запам’ятову-
вання.
Спочатку обчислимо деякі остачі:
10 == 3 (тод 7),
102 = 2 (тод 7),
103 = — 1 (тосі 7),
104 = — 3 (тод 7),
105 = —2 (тосі 7),
10е = 1 (тосі 7).
І далі всі остачі повторюються у тій самій послідовності.
Отже, остача від ділення числа N на 7 дорівнює:
г = а0 + За2 + 2аг — а3 — За4 — 2аь + ав + За, +
+ 2Од ------------------------- ...
Наприклад, N = 18 523 609 235.
Тоді г = 5Ч-9 + 4 — 9 — 0—12 + 3 + 6+10 —
— 8 — 3 = 37 — 32 = 5.
Зауважимо, що немає потреби повністю визначати г за
наведеними вище формулами. Як тільки ми дістанемо число,
більше за дільник, його можна замінити іншим числом —
меншим за нього, віднявши від знайденого числа дільник
(тобто одне число буде замінено іншим, конгруентним, але
меншим за величиною).
Набувши певної практики, можна користуватися цими
ознаками подільності без особливих труднощів.
80
§ 1. ПІФАГОРОВІ ТА ГЕРОНОВІ ЧИСЛА
Усім добре відома одна з найдавніших теорем матема-
тики — теорема Піфагора:
квадрат, побудований на гіпотенузі прямокутного
трикутника, рівновеликий сумі квадратів, побудованих на
його катетах.
Отже, числові значення сторін прямокутного трикут-
ника зв’язані таким співвідношенням:
х2 + у2 = г2. (1)
Ще стародавні математики розглядали питання про
існування прямокутних трикутників, сторонами яких
були б цілі числа. Інакше кажучи, було поставлено задачу
відшукання цілих додатних розв’язків рівняння (1). Трійки
цілих чисел, що задовольняють це рівняння, навчилися
знаходити дуже давно. Вони дістали назву п і ф а г о р о-
вих чисел. Найвідомішою такою трійкою чисел є З,
4, 5 (справді: З2 + 42 = 5а).
Легко бачити, що коли множити знайдені числа на
будь-який натуральний множник, ми щоразу діставатимемо
нову трійку піфагорових чисел, бо (ЗА)2 + (4А)2 = (5А)2.
Тому відразу домовимося розділяти трійки піфагорових
чис$д на основні та похідні.
Трійка піфагорових чисел х, у, г називається основ-
ною, якщо всі ці числа попарно взаємно-прості, тобто
ніякі два з них не мають жодного спільного множника.
Зазначимо, що коли б якісь два числа з трійки х, у, г
мали спільний множник а, то із співвідношення (1) обов’яз-
ково випливало б те, що третє число кратне а.
Кожна трійка піфагорових чисел, знайдена з основної
множенням усіх чисел на деякий натуральний множник,
називається похідною.
Наприклад, основною піфагоровою трійкою є числа 5,
12, 13. А похідними трійками будуть числа: 10, 24, 26;
25, 60, 65; 500, 1200, 1300,
82
Із самого означення похідних трійок піфагорових чисел
безпосередньо випливає, що рівняння (1) має безліч цілих
розв’язків.
Є багато способів знаходження піфагорових чисел. На-
ведемо один з них.
Напишемо ряд з квадратів натуральних чисел. А нижче
напишемо різниці, які діставатимемо внаслідок віднімання
квадратів, що стоять у першому рядку через один.
/ 4 9 16 25 36 49 64 61 100 121... 225 256 269 324
6 12 16 20 24 28 32 36 40 44... 60 64 68 72
Легко бачити, що коли різниця, яка стоїть у другому
рядку, сама є квадратом натурального числа, то маємо
піфагорову трійку. Наприклад, різницю 16 (тобто 42) ді-
стали внаслідок віднімання чисел 25 та 9. Таким чином,
їй відповідає піфагорова трійка 3, 4, 5. Аналогічно різ-
ниці 36 відповідає піфагорова трійка 6, 8, 10, а різниці
64 — трійка 8, 15, 17.
У зв’язку з тим, що у другому рядку стоять послідовні
натуральні числа, кратні 4, неважко підрахувати, що на-
ступними двома квадратами будуть різниці 100 та 144
(100 = 676 — 576 = 262 — 242, а 144 = 1369 — 1225 =
= 372 — 352).
Отже, ми знайшли ще дві піфагорові трійки: 10, 24, 26 та
12, 35, 37.
Цим способом можна знаходити все нові й нові піфаго-
рові трійки, причому серед них буде нескінченно багато
основних трійок.
Але чи всі основні піфагорові трійки можна знайти
таким способом? Безумовно, ні. Адже наведений вище спо-
сіб дає змогу знаходити лише ті піфагорові трійки, у яких
83
два найбільших числа відрізняються рівно на 2 одиниці.
Однак існує чимало основних та похідних трійок і іншого
типу, наприклад: 9, 40, 41; 33, 56, 65; 161, 240, 289; 900,
4000, 4100,
Отже, постає запитання: як знайти всі основні трійки
піфагорових чисел?
Розв’язання цієї задачі дається у наступному пара-
графі. А зараз ознайомимося з героновими трикутниками
та трійками чисел.
Цілком природно прямокутний трикутник, сторони
якогд вимірюються цілими числами, назвати п і ф а г о-
ровим трикутником. Зрозуміло, що в такого
трикутника і площа виражатиметься цілим числом. Задача
знаходження таких трикутників повністю зводиться до
відшукання основних трійок піфагорових чисел. Але ще
до нашої ери вчені зацікавилися проблемою поширення
цієї задачі на трикутники взагалі (а не тільки прямокутні).
Отже, було поставлено задачу знаходження трикутників,
у яких сторони вимірювалися б цілими числами і водночас,
щоб площі їх також виражалися цілими числами. Вияви-
лося, що таких трикутників існує нескінченно багато. Вони
дістали назву геронових трикутників. А три
цілих числа, що дорівнюють довжинам сторін таких трикут-
ників, називаються героновими трійками чисел.
З цього випливає, що піфагорові трійки чисел — частин-
ний випадок геронових трійок чисел, бо кожний прямокут-
ник є частинним випадком трикутника взагалі.
Дістати героновий трикутник неважко.
Візьмемо дві піфагорові трійки чисел, що мають по
одному рівному числу (рівними мають бути не найбільші
числа). Наприклад, 9, 12, 15 та 5, 12, 13. Зрозуміло, що
відповідні піфагорові трикутники матимуть по одному рів-
ному катету. Прикладемо ці прямокутні трикутники один
до одного рівними катетами.
Дістанемо трикутник, площа якого виражається цілим
числом, оскільки є сумою двох цілих чисел. Отже, побудо-
84
ваний трикутник € героновим. А відповідна трійка героно*
вих чисел буде такою: 14, 15, 13.
Аналогічними міркуваннями неважко знайти загальне
правило для відшукання геронових трійок чисел.
Нехай уи гг та х2, У2» г2 — Дві піфагорові трійки
чисел (вважатимемо, що в обох випадках останнє число
є найбільшим). З них можна утворити нові похідні піфа-
горові трійки:
У2, Уі Уг> у2 та х2 у2 уи г2 ух
або
х2, Уі *2, х2 та х2 х19 у2 х19 г2 хг.
Таким чином, ми дістали дві пари піфагорових трійок,
у кожній з яких є по одному рівному числу. А тому пари
відповідних прямокутних трикутників матимуть по одному
рівному катету. Звідси, як і вище, можна побудувати два
геронових трикутники. Тоді відповідні їм дві трійки геро-
нових чисел будуть:
(*1 Уі + х2 уг), ?! у2, 2г Уі та (ух . Х2 + у2 X!),
?! Х2, ?2 ХР
Розглянемо числовий приклад. Для цього візьмемо дві
довільні піфагорові трійки: 6, 8, 10 та 8, 15, 17. Утворимо
з них такі похідні трійки:
90, 120, 150 та 64, 120, 136,
48, 64, 80 та 48, 90, 102.
Звідси легко знайти дві геронові трійки чисел:
154, 150, 136 та 154, 80, 102.
§ 2. ЗНАХОДЖЕННЯ ОСНОВНИХ ПІФАГОРОВИХ
ТРІЙОК
Перед тим, як розв’язувати задачу про знаходження
основних піфагорових трійок, доведемо таку допоміжну
теорему:
85
Теорема. Якщо добуток двох взаємно-простих цілих
чисел є квадратом натурального числа, то й кожне з цих
чисел має бути точним квадратом.
Доведення. Нехай а Ь = с\ де а і Ь — взаємно-
прості числа.
Нагадаємо, що коли деяке натуральне число є повним
квадратом, то в його канонічному розкладі всі прості множ-
ники мають парні показники степеня (див. § 8 розділу
«Прості числа»).
гх і 2а. 2а2 2аз гп
Отже, а-Ь = Рі -р2 • рк . Тут усі р( —
прості числа, а а,—натуральні числа (і = 1, 2, 3, , и).
Через те що числа а і Ь не мають спільних множників,
жодне з чисел р{ не може одночасно входити в канонічний
розклад і числа а, і числа Ь. Таким чином, кожний з прос-
тих множників рс повністю, тобто у степені 2а,, входить
до розкладу лише одного з чисел: або до а, або до Ь. А ін-
ших простих множників у чисел а і Ь не може бути вза-
галі.
Отже, в канонічний розклад і числа а, і числа Ь всі
прості множники входять лише у парних степенях, тобто
обидва ці числа є точними квадратами.
Теорему доведено.
Повернемося до нашої задачі. Яку умову повинні задо-
вольняти натуральні числа х, у, 2, щоб утворювати основну
піфагорову трійку, тобто бути розв’язком рівняння х2 +
+ У2 = г2?
Очевидно, ніякі два з них не можуть одночасно бути
парними числами, інакше вони матимуть спільний діль-
ник 2. Крім того, всі три числа х, р, 2 водночас не можуть
фути непарними, бо в цьому випадку сума двох непарних
чисел х2 та у2, тобто ліва частина рівності, буде парним
числом, а права частина рівності, тобто число з2,— непар-
ним. Але парне число не може дорівнювати непарному,
тому рівність х2 + у2 = г2 в цьому випадку не виконува-
лася б.
Отже, одне з чисел х, у, 2 має бути парним, а два ін-
86
ших — непарними. Переконаємося, що парними можуть
бути лише х або у, тобто найбільше з чисел г обов’язково
повинно бути непарним.
Нагадаємо, що квадрат непарного числа при діленні
на 4 дає остачу 1, бо (2£ + І)2 = 4£2 + 4£ + 1. Таким
чином, якби х та у були б непарними числами, аг — пар-
ним числом, то ліва частина рівності (1), тобто сума х2 +
+ у2, при діленні на 4 давала б остачу 2, а права, тобто г2,
ділилася б на 4 без остачі. Отже, в цьому випадку рівність
х2 4- у2 = з2 не виконувалася б.
Ми прийшли до висновку, що числа х, у, 2 можуть утво-
рювати основну піфагорову трійку ТОДІ, КОЛИ ЧИСЛО 2 буде
непарним, а одне з чисел х чи у — парним. Вважатимемо,
що число х непарне, а у — парне (для дальших міркувань
це не має принципового значення).
Запишемо рівняння (1) у такому вигляді:
у2 = 22 — х2,
У2 = (2 + х) (2 — х).
Числа з + * та з — х — парні, бо вони являють собою
відповідно різницю й суму двох непарних чисел. Тоді,
розділивши кожне з чисел у, 2 + X, 2 — х на 2, знову ді-
станемо цілі числа. Врахувавши це, останню рівність
можна записати так:
ІУ \2 __ * + х і — х
\2/ “ 2 ’ 2 ‘
Цілі числа та взаємно-прості. Доведемо це
методом від супротивного. Нехай вони мають спільний
множник р, тобто == р • к, а = р • /и. Неважко
обчислити, що: з = р«(& + т), а х = р • (к— т). Вияви-
лося, що числа 2 та х мають спільний множник р. Але
це суперечить умові. Отже, наше припущення про наяв-
87
2 4- х г — х *
ність у чисел —та —спільного множника було
неправильним.
Таким чином, з рівності (2) випливає, що добуток двох
взаємно-простих чисел дорівнює квадрату натурального
<іисла. Згадавши доведену вище допоміжну теорему, ро-
бимо Висновок, що кожний із співмножників саме квадра-
том натурального числа, тобто:
4-х 2 2-Х 2
Т" = и та — =
де и та V — взаємно-прості натуральні числа, бо взаємно-
простими є числа и2 та Vі.
Звідси
А тоді
г = и2 4- Vі
х = и2 — V2
у = 2 и V.
(3)
(4)
Оскільки числа г та х непарні, то числа и та V мають
бутй різної парності (одне—парне, а друге — непарне).
Таким чином, ми прийшли до висновку, що три взаємно-
прості числа х, у, з, що задовольняють рівняння (1), можна
виразити за допомогою співвідношень (3) та (4) через два
взаємно-простих числа різної парності — и та у.
Легко переконатися у правильності й оберненого твер-
дження: якщо и та V — взаємно-прості числа різної парно-
сті, то для них виконується рівність (и2 — V2)2 4- (2«ї>)2 =
= (и2 4- V2)2. Розкривши дужки в обох частинах, можна
без будь-яких труднощів перевірити цю тотожність.
Отже, співвідношення (3) та (4) дають повний розв’язок
нашої задачі.
На закінчення за допомогою знайдених формул обчис-
лимо кілька основних трійок піфагорових чисел:
и = 3, V — 2, ТОДІ х = Зя — 2а = 5, «/ = 2-3-2= 12, 2 = 3а + 22 = 13;
и = 6, о = 5, тоді х = 62 — 52 = 11,
у = 2 • 6 • 5 = 60, г = б2 4- 52 = 61;
«= 17, о= 10, тоді х = 172 — 102 = 189, у = 2 • 17 • 10 = 340, 2 - 172 + 102 = 389;
и = 58, V — 45, тоді х = 582 — 452 = 1389,
у = 2 • 58 • 45 = 5220,
г = 582 + 45а = 5389.
Наявність нескінченної множини піфагорових трійок
дає можливість ставити задачі про відшукання таких трі-
йок піфагорових чисел, які б задовольняли ще ті чи інші
додаткові умови. Найвідомішою з таких задач є задача
Ферма: знайти такі піфагорові трійки чисел х, у, г, щоб
числа х 4- у та г самі були квадратами натуральних чисел.
Ця задача виявилася дуже важкою. Але її розв’язано.
Було доведено, що існує нескінченно багато таких піфаго-
рових трійок, але всі вони складаються з дуже великих
чисел. Ось найменше з них:
х = 4 565 486 027 761,
у = 1 061 652 293 520,
г = 4 687 298 610 289.
Тут х + у = (2 372 159)2, а г = (2 165 017)2.
$ 3. ВЕЛИКА ТЕОРЕМА ФЕРМА
У зв’язку з вивченням піфагорових чисел цілком іс-
тотно постає питання про можливість дальшого узагаль-
нення задачі: чи можна знайти такі цілі додатні числа.
89
які б задовольняли рівняння х3 + у3 = г3 або рівняння
х4 + у* = г4, або взагалі рівняння
хп + уп = гп,
де п — натуральне число, більше 2?
Спроби знайти хоча б один розв’язок якогось із цих
рівнянь не дали бажаних результатів. Досі не відома
жодна трійка натуральних чисел, яка б задовольняла
будь-яке з наведених рівнянь навіть з як завгодно великим
показником степеня.
Тому вже давно виникло припущення про те, що рів-
няння хп + Уп = де натуральне п > 2, не має роз-
в’язків у цілих числах. Причому історія його виникнення
надзвичайно цікава.
П’єр Ферма мав звичку робити помітки на полях кни-
жок, які читав, але при цьому не записував багатьох ви-
словлених ним теорем. Особливо багато таких поміток уче-
ний лишив на полях книжки «Арифметика» Діофанта. Саме
з цих поміток згодом дізналися про багато відкрить Ферма
в галузі теорії чисел. Усі висловлені ним припущення,
за винятком одного, пізніше були або доведені, або спрос-
товані математиками.
Читаючи у книжці Діофанта дослідження рівняння
*2 + У2 = А Ферма поояд на полях написав: «... проте
неможливо подати куб у вигляді суми двох кубів, чет-
вертий степінь —у вигляді суми двох четвертих степенів
та й взагалі будь-який степінь, більший за 2,— як суму
двох таких степенів. Я відкрив насправді чудове дове-
дення, але поля занадто малі, щоб нанести його».
Цю гіпотезу й називають «великою теоремою
Ферм а».
Це твердження залишається педоведеним у загальному
вигляді й досі, хоча правильність його перевірена вже для
всіх показників п аж до числа 4002. Можливо, Ферма
помилявся, вважаючи, що він знайшов доведення цієї
91
теореми. Ось чому правильніше було б назвати її «пробле-
мою Ферма».
Хоча з математичного боку ця теорема не має великого
значення, проте вона найвідоміша з усіх існуючих матема-
тичних проблем. Річ у тому, що німецький математик
П. Вольфскель (1856—1906) заповів 100 000 марок тому,
хто розв’яже проблему Ферма. Присуджувати премію було
доручено Геттінгенській Академії. І з тих пір на проблему
Ферма накинулися численні любителі математики. До Гет-
тінгенської Академії почали надходити всілякі варіанти
доведень, більшість з яких зводилась до перенесення уп
у праву частину рівняння. Зрозуміло, всі вони відпадали,
бо математики-спеціалісти відразу виявляли елементарні
математичні та логічні помилки. Проте деякі помилкові
розв’язання проблеми спочатку вважалися правильними
й навіть були опубліковані. І тепер до багатьох академій
та університетів іноді надходять листи з новими варіантами
доведення великої теореми Ферма.
Притягальна сила цієї задачі полягає, мабуть, у зов-
нішній легкості її формулювання. Однак справді проблема
виявляється надзвичайно складною. Лише деякі частинні
випадки її вдалося розв’язати без значних труднощів. Так,
для п = З та п = 4 задачу елементарно розв’язав ще
Цйлер. Потім для п = 5 її розв’язав Діріхле (1805—1859).
Але найбільших успіхів у цьому напрямі досяг німецький
математик Куммер (1810—1893). За допомогою спеці-
ально знайдених методів алгебраїчної теорії чисел Куммер
та його учні довели цю теорему для всіх значень показника
п аж до числа 100. Одночасно вчений був навіть упевнений
у тому, що повністю довів велику теорему Ферма, але
Діріхле вдалося знайти помилку в його міркуваннях.
Спроби Куммера виправити помилку привели його до ство-
рення нової надзвичайно цікавої та глибокої теорії —
теорії ідеалів у полях алгебраїчних чисел.
Наведений приклад не є винятковим, бо нерідко трапля-
лося так, що серйозні спроби математиків досягти нових
92
успіхів у розв’язанні проблеми Ферма приводили до від*
криття нових глибоких напрямів у теорії чисел.
Але повернемося до самої проблеми. Ще раз нагадаємо
її: треба довести, що рівняння
х" + у* = г",
де п — натуральне число, більше від 2, немає розв’язків
у цілих числах.
Легко бачити, що достатньо показати відсутність цілих
розв’язків лише для показника п = 4 та для непарних
простих значень його 3, 5, 7, 11, 13, 17, ... . Нехай п —
складене число, більше від 4. Тоді воно повинно мати серед
своїх простих дільників яке-небудь непарне просте число
або бути степенем двійки. В першому випадку п = р д,
де р = 3, 5, 7, 11, , а у другому випадку п — 4к.
Для таких п данб рівняння можна записати так:
(х’)р + (Уч)р = (*Р)Р
або
(х*)4 + (р*)4 = (г*)4.
Це й підтверджує, що проблему досить розв’язати для
п = 4 та для непарних простих значень показника, тобто
для п = 3, б, 7,
§ 4. РОЗВ’ЯЗАННЯ ПРОБЛЕМИ ФЕРМА ДЛЯ п =4
Спинимося на найлегшому з частинних випадків про-
блеми Ферма.
Покажемо, що рівняння
х4 + р4 = г4 (1)
не має цілих додатних розв’язків.
Якщо число — четвертий степінь натурального числа,
то воно є квадратом деякого натурального числа. Однак
цілком зрозуміло, що обернене твердження не правильне.
98
Так, 256 = 44 = 162. Але 25 = 52 а4, де а — нату-
ральне число.
З цього випливає, що рівняння
Xі + у* = ? (2)
загальніше, ніж рівняння (1). Інакше кажучи, рівняння (1)
є частинним випадком рівняння (2).
Тепер доведемо, що рівняння х4 + у* = ? не має цілих
додатних розв’язків. Цим автоматично буде розв’язано
проблему Ферма для п = 4.
Метод, яким будемо користуватися, називається мето-
дом «безмежного спуску» (або «нескінченного спуску»).
Ним користувався ще сам П. Ферма.
Припустимо, що існує три цілих додатних числа х, у, і,
які є розв’язком рівняння (2), тобто задовольняють рів-
ність х4 + у* = ґ®. Переписавши це співвідношення так:
(х2)2 + (у2)2 = і2, неважко помітити, що при цьому числа
х2, у2, і повинні утворювати піфагорову трійку. Тоді (див.
§ 2 цього розділу) існує два натуральних взаємно-простих
числа и та о різної парності, такі, що
г х2 = и2 — V2
| у2 = 2 • и • V (3)
(і = и2 + V2.
Оскільки квадрат непарного числа у результаті ділення
на 4 дає остачу 1, то з першої рівності випливає, що число
и непарне, а V — парне. Тоді можна покласти V = 2 цх.
Друга з рівностей (3) після цього набере вигляду:
(у V
(і) = «• VI.
Ми дістали, що добуток двох взаємно-простих чисел
дорівнює квадрату натурального числа. Згадавши допо-
міжну теорему, яку було доведено у § 2, робимо висновок,
що існують натуральні взаємно-прості числа а і Ь, такі,
що и = а2, ох = Ь2.
94
Тоді перше з рівнянь (3) можна подати у такому ви-
гляді:
хг = (а2)2 _ (262)*,
або
х2 + (262)2 = (а2)2.
Отже, числа х, 2Ь2, а2 знову утворюють піфагорову
трійку, тому повинні існувати два натуральних взаємно-
простих числа и2 та о2 різної парності, такі, що
2 2
х = и2 —і>2,
2&2 = 2 • и2 • о2, (4)
о 2,2
а2 = и2 + V2.
Скоротимо другу з рівностей на 2: Ь2 = и2 - о2.
Таким чином, кожне з чисел и2 та х>2 теж є точним ква-
дратом, тобто існують натуральні взаємно-прості числа хх
та у1г такі, що и2 = а?, V2 — у2.
Тоді третя з рівностей (4) перетвориться на:
4 , і о
х2+ Уі = (г.
Для зручності дальших міркувань покладемо а = іу.
X* + у* = і\. (5)
Наші міркування ми починали з припущення про те,
що існують три цілих числа х, у, і, які задовольняють рів-
няння (2). А після деяких перетворень кінець кінцем при-
йшли до того, що повинні існувати три цілих числа х1(
Уі, і1г які задовольняють рівняння (5). При цьому легко
переконатися, що
= а = V и < и < и2 + V2 = і.
Отже, в правій частині рівності (5) стоїть число 4, яке
значно менше за число і, що стоїть у правій частині рів-
ності (2).
З цього легко прийти до суперечності.
95
Справді, зробивши аналогічні перетворення з числами
хі> Ук ^і» ми дістали б три цілих числа х2, у2, і2, таких,
що х£ + уі — При цьому мали б /2 < і- Знову застосу-
вавши ті самі перетворення, мали б числа х3, у3, і3, які
також повинні задовольняти рівняння (2). І при цьому
знову і3 < і2 тощо.
Необмежено продовжуючи цей процес, можна дістати
нескінченну спадну послідовність натуральних чисел
і > /1 > і2 > і3 >
Та оскільки всі ці числа повинні бути цілими й додат-
ними, цілком зрозуміло, що їх може бути лише скінченна
кількість.
Суперечність доводить те, що рівняння X4 4- у* =
не може мати цілих розв’язків.
Отже, проблему Ферма для п = 4 розв’язано.
На закінчення звернемо увагу на один цікавий частин-
ний випадок її.
Покажемо, що для всіх значень п, більших хоча б за
одне з чисел х, у, г (тобто для всіх п > гпіп (х, у, г)), роз-
в’язання проблеми Ферма надзвичайно просте.
Нехай х < у < 2. Доведемо, що для всіх п > х рів-
няння х" + уп = 2ті не має цілих розв’язків.
Але спочатку нагадаємо таку формулу:
ап — Ьп = (а — Ь) (ап~і + ап~2 • Ь + а”-3 • Ь2 + . . . 4-
+ а • Ьп~2 + б"-’).
Тоді
хя = 2Л — і/1 = (г — у) (2п~і + г"-2 • у + ••• + г • уп~2 4-
+ Уп~' > (г — у) (хя_| + хп~2 • х + х”-3 • х2 + • • • +
+ х • хп—2 + х"-1) > 1 • (хп—1 + х"-1 4-----4- х"-1) =
= п • Хл-1 > X • хп~1 = х".
Прийшли до суперечності х” > Xа.
Отже, коли п > х, жодна трійка цілих чисел х, у, 2
не може задовольняти рівняння х” 4- */* = 2П.
96
§ 5. ПРОБЛЕМА ВАРІНГА
Спробуємо подати деяке натуральне число як суму
кількох точних квадратів. Зрозуміло, що ми зробимо це
лише для кількох невеликих натуральних чисел.
1 = І2,
2 = і2 + І2,
З = І2 + І2 + І2,
4 = 22
5 = 22 + І2,
6 = 22 + І2 + І2,
7 = 22 + І2 + І2 + І2,
8 = 22 + 22,
9 = З2
ю = з2’+ І2,
20 = 42 + 22
і т. д.
Поки що нам не було потрібно більш як чотири ква-
драти.
На перший погляд здається, що при дальшому пересу-
ванні вздовж натурального ряду дуже швидко виявляться
потрібними п’ять або ще більше квадратів. Але це не так.
Ще П’єру Ферма вдалося довести, що будь-яке натуральне
число можна подати як суму не більш ніж чотирьох ква-
дратів.
Цей дивний результат наштовхує на таке запитання:
а яка найбільша кількість кубів потрібна, щоб подати до-
вільне натуральне число у вигляді суми кубів?
Можна поставити аналогічне запитання для четвертих
степенів (тобто біквадратів), для п’ятих степенів і т. д.
Ця задача вже давно привертає увагу математиків. Вона
відома під назвою проблеми Варінга, бо першим
висунув її англійський математик Варінг (1734—1798).
В загальному вигляді ця проблема формулюється так:
треба довести, що для будь-якого цілого числа п~^2
97
існує таке ціле число г, залежне від п, що будь-яке на-
туральне число N можна подати у вигляді N = +
+ «2 + + а?, де всі йі — цілі числа, (і =1,2, , г).
Розглянемо кілька прикладів зображення натурального
числа у вигляді суми кубів. (Нагадаємо І3 = І3, 23 = 8,
33 = 27, 43 = 64).
3=1+1+1
7=1+1+1+1+1+1+1
10 = 8 + 1 + 1
15 = 8+1 + 1 + 1 + 1 + 1 + 1 + 1
20 = 8 + 8+1 + 1 + 1 + 1
ЗО = 27 + 1 + 1 + 1
50 = 8 + 8 + 8 + 8 + 8 + 8+1 + 1
100 = 64 + 27 + 8 + 1
Для кількох перших сотень або навіть тисяч натураль-
них чисел неважко безпосередньо перевірити, що кожного
разу нам буде потрібно не більш, як дев’ять кубів. При
цьому найбільша кількість доданків — 9 знадобиться,
наприклад, для числа 23.
23 = 8 + 8+1 + 1 + 1 + 1 + 1 + 1 + 1
На початку XX століття німецькі математики Віферіх
та Е. Ландау довели, що довільне натуральне число можна
подати як суму не більш ніж дев’яти кубів, а починаючи
з деякого певного числа, буде потрібно не більш ніж вісім
або навіть сім кубів.
Подібні математичні дослідження розв’язували лише
частинні випадки проблеми Варінга, в той час як у загаль-
ному вигляді проблема залишалася нерозв’язаною.
Так було доти, поки у 1909 році не з’явилася знаменита
праця видатного німецького математика Д. Гільберта
(1862—1943). У ній доводилося, що при розкладі будь-
якого числа на суми однакових степенів завжди існує
деяка гранична кількість доданків. Причому ця кількість
99
залежить лише від показника степеня й зовсім не залежить
від самого числа.
Слід зазначити, що великих успіхів у цьому досягли
й відомі англійські математики Г. Харді (1877—1947 рр.)
та Дж. Літлвуд (народився у 1885 р.). Зокрема Літлвуд
довів, що довільне натуральне число, починаючи з деякого
визначеного, може бути подане у вигляді суми не більш як
19 четвертих степенів (тобто біквадратів).
Визначна роль у розв’язанні проблеми Варінга нале-
жить радянському математикові І. М. Виноградову. Здо-
буті ним у 20—30-х роках успіхи є значно кращими й за-
гальнішими, ніж у Гільберта.
Розв’язання проблеми Варінга ще раз показало, як
тісно переплелися у теорії чисел стародавні елементарні
методи з надзвичайно глибокими й складними аналітичними
методами сучасної математики.
Наша подорож у світ цілих додатних чисел підійшла
до кінця. Ми ознайомились з одним з найстародавніших
розділів математики — теорією чисел, або, як її ще влучно
називають, вищою арифметикою.
Справді, теорія чисел виникла із задач арифметики,
пов’язаних з множенням і діленням цілих чисел, причому,
як ми побачили, більшість цих задач, незважаючи на еле-
ментарність їх постановки, довгий час були й залишаються
нерозв’язаними.
Розвиток теорії чисел має величезне значення для бага-
тьох розділів математики. В сучасному розумінні теорія
чисел вивчає не тільки властивості цілих раціональних
чисел, а й властивості інших класів чисел, причому для
доведення її тверджень вживаються засоби математичного
аналізу, теорії функцій, алгебри, геометрії тощо.
Використовуючи при розв’язуванні своїх задач резуль-
тати і методи різних математичних дисциплін, теорія чисел,
в свою чергу, відіграє велику роль у їх розвитку і вдоско-
наленні.
СПИСОК РЕКОМЕНДОВАНОЇ
І ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
1. Берман Г. Н. Число и наука о нем. М.»
Физматгиз, 1960.
2. Б у х ш т а б А. А. Теория чисел. М.» Просве-
щение, 1966.
3. Виноградов И. М. Основні теории чисел.
М., Наука, 1965.
4. В о р о б ь е в Н. Н. Признаки делимости. М.,
Физматгиз, 1963.
5. Дзвснпорт Г. Внісшая арифметика. М.,
Наука, 1965.
6. К а лу ж нин Л. А. Основная теорема ариф-
метики. М., Наука, 1965.
7. Литцман В. Великаньї и карлики в мире
чисел. М., Физматгиз, 1959.
8. Литцман В. Теорема Пифагора. М., Физ-
матгиз, 1960.
9. О ж и г о в а Е. П. Что такое теория чисел.
М., Знание, 1970.
10. Серпинский В. О решении уравнений
в цельїх числах. М., Физматгиз, 1961.
11. Серпинский В. Что мьі знаєм и чего не
знаєм о простьіх числах. М.—Л., Физматгиз, 1963.
12. Серпинский В. 250 задач по елемен-
тарної! теории чисел. М., Просвещение, 1968.
13. X и н ч и н А. Я. Цепньїе дроби. М., Физмат-
гиз, 1961.
ЗМІСТ
Вступ
З
Розділ І
Прості числа
| 1. Прості і складені числа............... 12
§ 2. Нескінченність множини простих чисел 15
| 3. Знаходження простих чисел . 16
§ 4. Розподіл простих чисел. Прості числа-
близняга ........... 19
§ 5. Числа Ферма і числа Мерсенна. Псе в до-
прості числа . . . 25
6 6. Прості числа в арифметичних прогресіях 34
8 7- Основна теорема арифметики . . 37
§ 8. Властивості дільників натурального
числа............... 41
6 9. Досконалі числа.................... . 45
§ 10. Деякі проблеми, пов’язані з простими
числами 48
Розділ II
Подільність чисел
6 1< Операція ділення.................... 54
§ 2. Найбільший спільний дільник та наймен-
ше спільне кратне . 56
ІЗ. Алгоритм Евкліда.................... 59
4. Про одну важливу властивість Е> (а, Ь) 61
$. Ланцюгові дроби . 63
6. Діофантові рівняння . 67
7. Властивості остач . . . . 71
8, Конгруенції. Мала теорема Ферма . 75
9. Ознаки подільності . 78
Розділ III
Піфагорові числа та проблема Ферма
§ 1. Піфагорові та геронові числа........ 82
8 2. Знаходження основних піфагорових трійок 85
§ 3. Велика теорема Ферма . 89
§ 4. Розв’язання проблеми Ферма для п = 4 . 93
8 5. Проблема Варінга . ... 97
Список рекомендованої і використаної літера-
тури . • • • ♦ .101
Балерин Яковлевич Валах
ПУТЕШЕСТВИЕ В МИР ЦЕЛЬІХ ЧИСЕЛ
(на украинском язьіке)
Издательство «Радянська школа» Государственного
комитета Совета Министров Украйнской ССР по делам
издательств, лолиграфии и книжной тор гов ли
Редактор Л. М. Шут. Літредактор К. М. Лаіико. Художній
редактор В. Ф. Монжеран. Обкладинка художника
В. Г. Гури. Технічний редактор З, С. Бурдейна. Коректор
Г. Т. Марчук.
Інформ. бланк Ке 1301
Здано до набору 16.12.77. Підписано до друку 26.05.78. БФ
10263.Формат 70Х1081/зі- Папір друк. Ке 2. Літературна
гарнітура, високий друк. Умови, арк. 4,65. Обл-
видавн. арк. 4,22. Тираж 47.000. Зам. Ке 8-6. Ціна ІВ к.
Видави. Ке 24735
Видавництво «Радянська школа» Державного комітету Ради
Міністрів Української РСР у справах видавництв, поліг-
рафії і книжкової торгівлі, Київ, вул. Юрія Коцюбин-
ського, 5. Темплан 1978 р.
Книжкова фабрика ім. М. В. Фрунзе Республіканського
виробничого об'єднання «Поліграфинига» Держкомвидаву
УРСР, Харків, Донець-Захаржевська, 6/8.
Валах В. Я.
В15 Подорож у світ цілих чисел. К., «Рад. шко-
ла», 1978. ©
102 с. з іл.
47 000 пр. 15 к.
У книжці в популярній формі розповідається про древній, надзви-
чайно цікавий 1 дещо загадковий розділ математики — теорію Чисел.
Розглядаються властивості подільності чисел та конгруенції. Форму-
люються ще не розв’язані проблеми. Розрахована на учнів старшого
шкідьного віку І всіх, хто цікавиться математикою. Може бути викори-
стана вчителями для гурткових та факультативних занять.
Держ. респ. б-ка
УРСР ім. КПРС 517.1
ПОДОРОЖ
У СВІТ
ЦІЛИХ ЧИСЕЛ