§ 4. Найважливіші функції в теорії чисел
Пункт 12. Ціла і дробова частина.
Визначення . Нехай x ??R - дійсне число. Цілою частиною [ x ] числа x називається його нижнє ціле, тобто найбільше ціле, що не перевершує x ; дробовою частиною { x } числа x називається число { x } = x - [ x ].
Приклади. [2,81] = 2; {2,81} = 0, 81; [- 0,2] = -1; {-0,2} = 0,8.
Відзначимо, що ці дві функції відомі кожному зі шкільної лави; що ціла частина - неспадна функція; що дробова частина - періодична з періодом 1 функція; що дробова частина завжди невід’ємна, але менша за одиницю; що обидві ці функції розривні при цілих значеннях x , але неперервні при цих x справа.
Лема 1. Показник, з яким просте число р входить у розклад n! , дорівнює ??= [ n/p ] + [ n/p2 ] + [ n/p 3 ] + ...
Доказ. Очевидно, ряд [ n / p ] + [ n / p 2 ] + [ n / p 3 ] + ... обривається в тому місці k , на якому pk перевершить n . Маємо:
n! = 1· 2· 3·...· p· ...· p2 ...· p3 ...· ( n -1) · n .
Число співмножників, кратних p , дорівнює [ n/p ]. Серед них, кратних p2 , міститься [ n / p2 ]; кратних p3 є [ n/p3 ] і т.д. Сума ?? дає шуканий результат, тому що всякий співмножник, кратний pm , але не кратний p m +1 , полічений у ній точно m раз: як кратний p , як кратний p2 , як кратний p3 ,..., як кратний pm .
Приклад. Показник, з яким 5 входить у 643! дорівнює:
[643/5] + [643/25] + [643/125] + [643/625] = 128 + 25 + 5 + 1 = 159.
Визначення. Точка координатної площини називається цілою, якщо обидві її координати - цілі числа.
Лема 2. Нехай функція f ( x ) неперервна і невід’ємна на відрізку [ a, b ]. Тоді число цілих точок в області D = { a < x ??b , 0 < y ??f ( x )} дорівнює
EMBED Equation.3
Доказ. На вертикальній прямій з цілою абсцисою x в області D лежить [ f ( x )] цілих крапок.
Ще одне твердження про цілі точки відноситься до області комбінаторної геометрії:
Лема 3. Нехай М - многокутник на координатній площині з вершинами в цілих точках, контур М сам себе не перетинає і не торкається, S - площа цього многокутника,
EMBED Equation.3
де підсумовування ведеться по всіх цілих точках А, що лежать усередині і на границі цього многокутника, причому ?A = 1, якщо крапка А лежить усередині М , і ?A = 1/2, якщо крапка А лежить на границі М. Тоді T = S .
Доказ цієї леми не приводитимо, тому що ця лема, узагалі кажучи, не відноситься до теорії чисел. Схема цього доказу.
1) Для трикутника з вершинами в цілих крапках і без цілих крапок усередині твердження очевидне.
2) Для опуклого багатокутника - фіксуємо одну з його вершин і з'єднуємо її прямими з іншими вершинами - попадаємо у випадок трикутників.
3) Випадок неопуклого багатокутника розглядаємо як різницю опуклих багатокутників.
.
Теорема (Лежен Діріхле (1805-1859)). Для будь-якого ????R число 0 є граничною точкою послідовності xn = { ??· n }.
Доказ. Візьмемо будь-яке натуральне t і покажемо, що нерівність
EMBED Equation.3
обов'язково має розв’язок в цілих числах p і q , де q ??1. Нехай 0 = { ??· 0}, { ??· 1}, { ??· 2},..., { ??· ( t -1)}, { ??· t } - ( t +1) чисел. Усі вони з відрізка [0, 1]. Розділимо цей відрізок на t рівних частин кроком 1/t . За принципом Діріхле (саме для доказу цієї теореми Діріхле і придумав свій знаменитий "принцип Діріхле" про t клітинок і ( t+ 1) кролика, яким ніде сидіти) в одній з частин відрізка лежить два числа { ??· k1 } і { ??· k2 }, де k2 > k1 . Маємо:
|{ ??k1 } - { ??k2 }| = | ??( k2 - k1 ) - ([ ??k2 ] - [ ??k1 ])| < 1/t
Покладемо k 2 - k 1 = q , [ ??· k 2 ] - [ ??· k 1 ] = p , ясно, що q ??t . Тоді будемо мати
| ??q - p | < 1/t, 0 < q ??t .
Це означає, що p / q – розв’язок нерівності
EMBED Equation.3
Спрямуємо t до нескінченності. Одержимо, що ??q відмінне від цілого числа p менш, ніж на 1/ t , а
EMBED Equation.3
Отже, або 0, або число 1 - гранична точка послідовності xn ={ ??· n }. Якщо число 0 - гранична точка, то усе доведено. Якщо ж гранична точка - число 1, то тоді для будь-якого ?>0, знайдеться член x послідовності xn такий, що x > 1 - ??. Нехай x =1- ??. Тоді 2 x = 2 - 2 ??, а {2 x } (очевидно, що {2 x } - теж член послідовності xn ) не дотягає до 1 уже на 2 ??; число {3 x } менше 1 уже на 3 ??, і т.д. Отже, можна підібрати таке натуральне k , що член { kx } буде менший за одиницю на k ??и потрапить у ??-окіл нуля. Це означає, що число 0 також є граничною точкою послідовності xn , що саме й було потрібно.
Очевидно, що якщо ??= p / q - раціональне число, де ( p , q ) =1, то послідовність xn ={ ??· n } є періодичною з періодом q і її членами є лише числа
0, EMBED Equation.3, EMBED Equation.3, … , EMBED Equation.3
Трохи модернізувавши міркування з доказу попередньої теореми, можна обґрунтувати наслідок, що так само належить перу Діріхле.
Наслідок. Якщо число ????R іррациональне, то члени послідовності xn ={ ??· n } усюди щільно заповнюють відрізок [0, 1].
Пункт 13. Мультиплікативні функції.
Визначення. Функція ??: R ??R (чи, більш загально, ??: C ??C ) називається мультиплікативною якщо:
1). Функція ??визначена на N і існує а ??N таке, що ?( а) ??0.
2). Для будь-яких взаємно простих натуральних чисел а1 і а2 виконується ?(а1·а2)=?(а1)·?(а2).
Приклад 1. ??( а) = аs , де s - кожне (хоч дійсне, хоч комплексне) число. Перевірка аксіом 1) і 2) з визначення мультиплікативної функції не є важким, а сам приклад показує, що мультиплікативних функцій щонайменше континуум, тобто багато.
Перелічимо, подекуди доводячи, деякі властивості мультиплікативних функцій. Нехай усюди нижче ??( а) - довільна мультиплікативна функція.
Властивість 1. ??(1) = 1.
Доказ. Нехай а - натуральне число, для якого ??(а)??0. Тоді ??(а·1) = ??( а) · ??(1) = ??( а).
Властивість 2.
EMBED Equation.3
де р 1 , р 2 ,..., р n - різні прості числа.
Доказ очевидний.
Властивість 3. Завжди можна побудувати деяку мультиплікативну функцію ??(a), якщо задати ??(1) = 1 і довільно визначити ??( р ??) для всіх простих р і всіх натуральних ??, а для інших натуральних чисел довизначимо функцію ??( a ) використовуючи рівність
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-001.gif".
Доказ відразу випливає з основної теореми арифметики.
Приклад 2. Нехай ??(1) = 1 і ??( р ??) = 2 для всіх р і ??. Тоді, для довільного числа,
EMBED Equation.3
Властивість 4. Добуток декількох мультиплікативних функцій є мультиплікативною функцією.
Доказ. Спочатку доведемо для двох співмножників: Нехай ?1 і ?2 - мультиплікативні функції ??= ?1 · ?2 , тоді (перевіряємо аксіоми визначення)
1) ??(1) = ?1 (1) · ?2 (1) = 1 і, крім того, існує таке a (це a = 1), що ??( a ) ??0.
2) Нехай ( a , b ) = 1 - взаємно прості. Тоді
??( a · b ) = ??1 ( a · b ) · ??2 ( a · b ) = ??1 ( a ) ??1 ( b ) ??2 ( a ) ??2 ( b ) =
= ??1 ( a ) ??2 ( a ) · ??1 ( b ) ??2 ( b ) = ??( a ) ??( b ).
Доказ для більшого числа співмножників проводиться стандартним індуктивним міркуванням.
Уведемо зручне позначення. Усюди далі, символом EMBED Equation.3будемо позначати суму чого-небудь, у якій підсумовування проведене по всіх дільниках d числа n. Наступні менш очевидні, ніж попередні, властивості мультиплікативних функцій сформулюємо у вигляді лем.
Лема 1. Нехай EMBED Equation.3
канонічний розклад числа a ??N , ??- будь-яка мультиплікативна функція. Тоді:
EMBED Equation.3
Якщо a = 1, то вважаємо праву частину рівною 1.
Доказ. Розкриємо дужки в правій частині. Одержимо суму усіх (без пропусків і повторень) доданків виду
EMBED Equation.3
де 0 ???k ???k , для всіх k ??n . Оскільки різні прості числа взаємно прості, то
EMBED Equation.3
а це саме те, що стоїть в рівності, що доводиться, ліворуч.
Лема 2. Нехай ??( a ) - будь-яка мультиплікативна функція. Тоді
EMBED Equation.3 - також мультиплікативна функція.
Доказ. Перевіримо для ??( a ) аксіоми визначення мультиплікативної функції.
1). EMBED Equation.3
2). Нехай
(a,b)=1, EMBED Equation.3, EMBED Equation.3
і всі р и q різні. Тоді, за попередньою лемою, маємо: ( дільники в чисел a і b різні)
EMBED Equation.3
Пункт 14. Приклади мультиплікативних функцій.
Приклад 1. Число дільників даного числа.
Нехай ??( а) = а 0 ??1 - тотожна одиниця (свідомо мультиплікативна функція). Тоді, якщо
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif",
та тотожність леми 1 пункту 13 набуває вигляду:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-001.gif",
- це не що інше, як кількість дільників числа a . За лемою 2 пункту 13, кількість дільників ??(a) числа a є мультиплікативною функцією.
Чисельний приклад. ??(720) = ??(2 4 · 3 2 · 5) = (4 + 1)(2 + 1)(1 + 1) = 30.
Приклад 2. Сума дільників даного числа.
Нехай ??( a ) = a 1 ??a - тотожна мультиплікативна функція. Тоді, якщо
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif",
то тотожність леми 1 пункту 13 набуває вигляду:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-002.gif"
- сума всіх дільників числа a . За лемою 2 пункту 13, сума всіх дільників є мультиплікативною функцією.
Чисельний приклад.
S (720) = S (2 4 · 3 2 · 5) =EMBED Equation.3
Пример 3. Функція Мебіуса.
Функція Мебіуса ??( a ) - це мультиплікативна функція, що визначається так: якщо p - просте число, то ??( p ) = -1; ??( p ??) = 0, при ??> 1; для інших натуральних чисел функція довизначається за мультиплікативністю.
Таким чином, якщо число a ділиться на квадрат натурального числа, відмінний від одиниці, то ??( a ) = 0; якщо ж a = p 1 p 2· · · p n то ??( a ) = (-1)k , де k - число різних простих дільників a . Зрозуміло, що ??(1) = (-1)0 = 1, як і повинно бути.
Лема 1. Нехай ??( a ) - довільна мультиплікативна функція,
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif".
Тоді:
EMBED Equation.3,INCLUDEPICTURE \d \z "../pict/14-005.gif"
(при a = 1 вважаємо праву частину рівною 1).
Доказ. Розглянемо функцію ?1 ( x ) = ??( x ) · ??( x ). Ця функція мультиплікативна, як добуток мультиплікативних функцій. Для ?1 ( x ) маємо ( p - просте): ?1 ( p ) = - ??( x ); ?1 ( p ??) = 0, при ??> 1. Отже, для ?1 ( x ) тотожність леми 1 пункту 13 виглядає так:
EMBED Equation.3
Наслідок 1. Нехай ??( d ) = d-1 = 1/ d (це, звичайно, мультиплікативна функція),
EMBED Equation.3, a>0.INCLUDEPICTURE \d \z "../pict/14-007.gif"
Тоді:
EMBED Equation.3
Приклад 4. Функція Ейлера.
Функція Ейлера ?( a ) є кількістю чисел з ряду 0, 1, 2,..., a-1, що є взаємно простими до a.
Лема 2. Нехай EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif".
Тоді:
1) EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-009.gif"(формула Эйлера);
2) EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-010.gif"
зокрема, ?( p??) = p??- p??-1 , ?( p ) = p - 1.
Доказ. Нехай x набуває значень з діапазону чисел 0, 1, 2,..., a - 1. Нехай ?x = ( x , a ) - найбільший спільний дільник. Тоді ?( a ) є кількість значень ?x , рівних 1. Придумаємо таку функцію ?(?x), щоб вона була одиницею, коли ?x одиниця, і була нулем в інших випадках.
EMBED Equation.3
Останнє легко зрозуміти, якщо згадати лему 1 з цього пункту й у її формулюванні взяти ??(d)??1. Далі можна помітити, що:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-012.gif"
Оскільки сума справа в дужках береться по всіх дільниках d числа ?x = ( x, a ), то d ділить x і d ділить a . Тому у першій сумі справа у підсумовуванні присутні лише ті x, що кратні d . Таких x серед чисел 0, 1, 2,..., a - 1 є a/d штук. Виходить, що:
EMBED Equation.3,INCLUDEPICTURE \d \z "../pict/14-013.gif" що і було потрібно.
Маємо
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-014.gif"
Зафіксуємо деяке d0 таке, що d0 ділить a, d0 ділить x, x < a. Отже у сумі справа у дужках доданків ??(d0 ) рівно a/d0 штук і ?( a ) є сумою EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-015.gif"
Після цього, рівність
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-008.gif"
одержується після застосування наслідку з леми 1 цього пункту.
Друге твердження леми випливає з першого внесенням множника а усередину дужок.
Виявляється, тільки що доведена формула
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-009.gif"
для обчислення функції Ейлера має зрозумілий "фізичний зміст". Справа в тому, що в ній відображене, так зване, правило включень і виключень:
Правило включень і виключень. Нехай задана множина А и виділено k її підмножин. Кількість елементів множини А, що не входять у жодне з виділених підмножин, підраховується так: треба з загального числа елементів А відняти кількість елементів усіх k підмножин, додати кількість елементів усіх їхніх попарних перетинів, відняти кількість елементів усіх потрійних перетинів, додати кількість елементів усіх перетинів по чотирьох і т.д. аж до перетинів всіх k підмножин.
Проілюструємо це правило на прикладі підрахунку функції Ейлера для чисел виду
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-016.gif"
Рис. 4.
Прямокутник зображує множину усіх цілих чисел від 0 до a; овал N1 - множину чисел, кратних p1; коло N2 - числа, кратні p2 ; перетин N1,2 - множину чисел, що діляться одночасно на p1 і p2 , тобто на p1 p2; числа поза овалом і колом взаємно прості з a. Для підрахунку кількості чисел, взаємно простих з a, потрібно від a відняти кількість чисел у N1 і кількість чисел у N2 (їх, відповідно, a/p1 і a/p2 штук), при цьому загальна частина N1,2 (там a/(p1 p2) штук чисел) відніметься двічі, значить її треба один раз додати (от воно, "включення - виключення"!). У результаті одержимо:
EMBED Equation.3, що й стверджувалося.
При a>2, ?(a) завжди парне. Дійсно, якщо k взаємно просте до a і k<a, то число a-k теж менше за a, взаємно просте до a і не дорівнює k . (Якби a і a-k мали спільний дільник, то їхня різниця a-(a-k) = k теж ділилася б на цей дільник, що суперечить взаємній простоті a і k.) Отже числа, взаємно прості з a розбиваються на пари k і a-k, тому, їх є парне число.
З леми 2 випливають наслідки.
Наслідок 2. Функція Ейлера мультиплікативна.
Доказ. Маємо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-019.gif" - добуток двох мультиплікативних функцій, перша з який мультиплікативна за лемою 2 пункту 13. Виходить, ?(a) - мультиплікативна.
Наслідок 3.INCLUDEPICTURE \d \z "../pict/14-019.gif" EMBED Equation.3
Доказ. Нехай EMBED Equation.3INCLUDEPICTURE \d \z "../pict/13-004.gif".
Тоді, за лемою 1 пункту 13 маємо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-021.gif"
Чисельні приклади.
??(5) = 5 - 1 = 4
??(30) = ??(2 · 3 · 5) = (2 - 1)(3 - 1)(5 - 1) = 8
EMBED Equation.3
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/14-023.gif"
На цьому, мабуть, пункт 14 закінчимо. Крім того, пропозиція, що ви зараз почали уважно читати, теж закінчилося.
Пункт 15. ??-функція Рімана.
Цей пункт трохи складніший за попередні, тому що для його розуміння будуть потрібні знання з області математичного аналізу і теорії функцій комплексних змінних. Буквою C позначимо поле комплексних чисел.
Визначення. Нехай s ??C, дійсна частина Re(s)>1. ??-функцією Рімана називається функція комплексної змінної, що задається рядом:
EMBED Equation.3.INCLUDEPICTURE \d \z "../pict/15-001.gif"
Правомірність такого визначення підтверджує таке спостереження.
Спостереження. У напівплощині Re( s ) > 1 ряд EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-002.gif"сходиться абсолютно.
Доказ. Нехай s ??C, Re( s ) > 1, s = ??+ i ??(див. рис. 5).
Рис. 5.
Порахуємо абсолютні величини членів ряду:
|n-s|=|e-slns|=|e-?lnn-i?lnn|=|e-?lnn(cos(?lnn)-isin(?lnn))INCLUDEPICTURE \d \z "../pict/15-004.gif"|=|e-?lnn|=EMBED Equation.3.
Тепер скористаємося інтегральною ознакою збіжності (ми пам'ятаємо, що ??> 1):
EMBED Equation.3.INCLUDEPICTURE \d \z "../pict/15-005.gif"
Отже, при ??> 1 ряд EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-002.gif"сходиться абсолютно. ?
З цього спостереження випливає
Наслідок 1. Функція ??( s ) аналитична в напівплощині Re( s ) > 1.
Доказ. Дійсно, при всякому ??> 0 і фіксованому ??> 1+ ??, числовий ряд EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-006.gif"мажорує ряд з абсолютних величин INCLUDEPICTURE \d \z "../pict/15-002.gif"INCLUDEPICTURE \d \z "../pict/15-006.gif"EMBED Equation.3=EMBED Equation.3, де ??????, звідки, за теоремою Вейєрштрасса, випливає рівномірна збіжність ряду INCLUDEPICTURE \d \z "../pict/15-002.gif"в напівплощині Re( s ) ????. Сума ряду з аналітичних функцій, що рівномірно сходиться сама є аналітичною функцією.
Тепер залишилося лише безмежно наближатися до вертикальної пунктирної прямої Re(s)=1 на рис.5, спрямовуючи ??до нуля. Виходить, що у всіх напівплощинах, границя яких як завгодно близько підходить до прямої Re(s)=1, ряд INCLUDEPICTURE \d \z "../pict/15-002.gif"сходиться абсолютно і рівномірно, а його сума - аналітична функція. ?
Нематематичний відступ. Функцію EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-001.gif"вперше розглядав Ейлер і дослідив багато її властивостей і відкрив свою знамениту формулу EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-007.gif", що зв'язує ??(s) з простими числами. Тому, вірніше було б називати функцію дзета-функцією Ейлера. Кілька слів про Бернгарде Рімане (1826 - 1866). Ріман був сином сільського священика, учився в Геттингенському університеті, де в 1851 році одержав ступінь доктора, у 1854 році став приват-доцентом, у 1859 році - професором, наступником Діріхле на кафедрі математики. Йому належать введення в аналіз топологічних представлень, поняття ріманової поверхні, інтеграл Рімана, дослідження гіпергеометричних рядів і абелевих функцій. У роботі 1859 року він досліджував кількість простих чисел, менших заданого числа, і дав точну формулу для знаходження цього числа з функції ?(s). У цій же роботі сформульована "гіпотеза Рімана" про нулі аналітичного продовження ?(s) на всю комплексну площину (Чи вірно, що всі не дійсні нулі дзета-функції лежать на прямій Re(s) =1/2?). Ця гіпотеза, мабуть, є однієї із самих старих, важких і насущних математичних проблем. Вона дотепер не доведена і не спростована.
Далі нам будуть потрібні деякі відомості з матаналізу і теорії функцій комплексної змінної про нескінченні добутки.
Визначення. Нехай u1 , u2 ,..., un ,... - нескінченна послідовність комплексних чисел і всі uj?-1. Вираз виду: INCLUDEPICTURE \d \z "../pict/15-008.gif"
EMBED Equation.3 ( ??) називається нескінченним добутком, а вирази:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-009.gif" - частковими добутками нескінченного добутку.
Якщо послідовність часткових добутків vk при k ????сходиться до числа v ??0, то говорять, що нескінченний добуток сходиться і дорівнює v. В іншому випадку, якщо vk не сходиться (чи vk ??0), то говорять, що нескінченний добуток розходиться (розходиться до нуля).
Теорема 1 (Ознака збіжності ( ??)). Якщо ряд
u 1 + u 2 +... + u n +... сходиться абсолютно, то нескінченний добуток ( ??) сходиться.
Доказ . Нехай EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-010.gif"- сходиться, тому загальний член цього ряду прямує до нуля і можна вважати, що, наприклад, | un | ??1/2 для всіх n > n0 ??N . Нехай спочатку un ??R. Тоді, виходячи з чудової границі EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-011.gif", починаючи з деякого номера n > n0 , маємо: |ln(1+un)|??2|un|. Отже, послідовність логарифмів часткових добутків
Sn = ln (1 + u 1 ) + ln (1 + u 2 ) +…+ln(1+un)=lnvn
сходиться, тому що EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-012.gif", а справа в останній нерівності стоять часткові суми ряду, що сходиться. Отже, сходиться і нескінченний добуток ( ??).
Нехай тепер un - довільні комплексні числа. Треба довести, що при n???сходяться дві послідовності дійсних чисел:
| vn | = |(1+ u1 ) ·...· (1+ un )| = |1+ u1 | ·...· |1+ un | (1)
arg vn = arg ((1+ u1 ) ·...· (1+ un )) = arg (1+ u1 ) +...+ arg (1+ un ) (2)
Нехай un = ?n + i ?n . Ясно, що для збіжності послідовності
| vn | необхідно і досить збіжності послідовності | vn |2 .
Але |1+ un | 2 = |1 + ?n + i ?n | 2 = 1 + ?n 2 + ?n 2 + 2 ?n і, оскільки
| ?n2 + ?n2 + 2 ?n | ??| un |2 + 2| un |, то збіжність (1) випливає з уже доведеного. Збіжність (2) випливає з того, що при всіх n, що більші за деяке n0,
|arg(1+un)|=EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-013.gif"(тут знову використана чудова границя EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-014.gif"), а | ?n | ??0 оскільки un ??0.
Теорема 2 (Формула Ейлера).
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-015.gif",
де pj - j - те просте число і нескінченний добуток справа береться по всіх простих числах.
Доказ. Нехай X ??1, Re(s) > 1. Ряди
1+EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-016.gif"
абсолютно сходяться (тому що мажоруються геометричними прогресіями). За теоремою 1 це означає, що нескінченний добуток у формулі Ейлера сходиться. Маємо (значок EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-017.gif"означає добуток по всіх простих числах, що не перевищують X ):
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-018.gif".
Тут при одержанні першої рівності використовувалася формула суми геометричної прогресії, при одержанні останньої рівності істотну роль зіграла основна теорема арифметики. Через R(s, X) позначений залишковий член, приписування якого в потрібному місці дозволяє поставити знак рівності між будь-якими величинами. Насправді ж, R(s, X) містить нескінченне число доданків виду 1/ ns, що не ввійшли в суму, що стоїть перед ним. Оцінимо залишковий член:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-019.gif",
тобто R(s, X) ??0, при X ?????Це й означає справедливість формули Ейлера.
Наслідок 2. При Re( s ) > 1, ??( s ) не має нулів.
Доказ. Маємо:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-020.gif",
отже INCLUDEPICTURE \d \z "../pict/15-021.gif"EMBED Equation.3
Продовжимо ??( s ) у напівплощину Re( s ) > 0. Наступні лема і наслідок мають лише показати один з можливих способів реалізації її продовження, тому їхній доказ можна пропустити.
Лема 1. При Re( s ) > 0, N ??1
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-022.gif"
Доказ. Маємо при Re( s ) > 1:
EMBED Equation.3
INCLUDEPICTURE \d \z "../pict/15-023.gif"Але останній інтеграл справа визначає аналітичну функцію навіть при Re(s) > 0. Тому, завдяки принципу аналітичного продовження, твердження леми 1 справедливе. ?
Наслідок 3. Функція ??( s ) є аналітичної в напівплощині Re(s)>0 за винятком крапки s = 1; у крапці s = 1 дзета-функція має простий полюс з відрахуванням, рівним 1. ?
Виявляється, що дзета-функція має нескінченно багато нулів у "критичній смузі" 1>Re(s)>0. Відомо, що ці нулі лежать симетрично відносно прямих Re( s ) =1/2 і Im( s ) = 0; відомо, що в області Re(s)? EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-024.gif", де b = Im(s), а с - абсолютна стала, нулів у ??(s) немає (Теорема Ш. Валле-Пуссена). Проте знаменита гіпотеза Рімана, що всі нулі ??(s) лежать на прямій Re(s)=1/2 дотепер не доведена, хоча перевірена для більш, ніж 7 мільйонів коренів. Ось перші десять коренів ??(s) = 0:
?1,2=1/2?14,134725i, ?3,4=1/2?21,022040i, ?5,6=1/2?25,010856i, ?7,8=1/2?30,424878i, ?9,10=1/2?32,935057i.
Наведемо формулу Рімана, про яку вже згадувалося в цьому пункті дрібним шрифтом, для числа ?(x) простих чисел, що не перевищують x:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-025.gif",
де підсумовування справа ведеться по всіх нулях ??(s), а
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-026.gif".
Доведемо за допомогою дзета-функції Рімана відомі твердження.
Твердження 1. Простих чисел нескінченно багато.
Доказ перший. Ну нехай p1 , p2 ,..., pk - усі прості. Тоді, оскільки
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-027.gif",
одержуємо (при s = 1 і досить великих N ):
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-028.gif", оскільки EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-029.gif".
Але це неможливо, бо гармонійний ряд INCLUDEPICTURE \d \z "../pict/15-030.gif" EMBED Equation.3 розходиться.
Доказ другий. Ну нехай p1 , p2 ,..., pk - усі прості.
ТодіINCLUDEPICTURE \d \z "../pict/15-031.gif", EMBED Equation.3 , що неможливо, оскільки кінцевий добуток є раціональним числом, що не скажеш про число ?2/6. ?
Наступне твердження набагато менш відоме, ніж нескінченність множини простих. Візьмемо гармонійний ряд EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-030.gif"і сильно прорідимо його, залишивши в ньому тільки доданки, зворотні до простих чисел і викинувши всі доданки, що є зворотними до складних. Це дійсно сильне прорідження, тому що в натуральному ряді існують як завгодно довгі проміжки без простих чисел, наприклад:
n ! + 2 , n ! + 3 , n !+4,..., n ! +n .
Гармонійний ряд, як відомо, розходиться. Дивно, що
Твердження 2. Ряд EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-032.gif"зі зворотних величин до всіх простих чисел розходиться.
Доказ. Нехай X ??N . Маємо:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-033.gif"
де значок ???означає, що підсумовування ведеться по всіх n>X, у розкладі яких немає простих співмножників, більших за Х. Значить:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-034.gif" і INCLUDEPICTURE \d \z "../pict/15-035.gif",
EMBED Equation.3 , оскільки гармонійний ряд розходиться. З останнього випливає, що нескінченний добуток
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-036.gif" - розходиться до нуля, тобто
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-037.gif".
Виходить, що
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-038.gif".
Ми пам'ятаємо чудову границю: EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-039.gif",
з якої випливає, що:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-040.gif", звідки:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-041.gif".
Таким чином, у ряді EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-043.gif", INCLUDEPICTURE \d \z "../pict/15-042.gif"
кожен член менший за відповідний член розбіжного до - ??ряду EMBED Equation.3
отже, ряд EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-044.gif"розходиться до + ????
Зазначимо, що незважаючи на те, що ряд EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-044.gif"розходиться, він розходиться все-таки повільніше гармонійного. Про часткові суми цих рядів відомо, що EMBED Equation.3 зINCLUDEPICTURE \d \z "../pict/15-045.gif"ростає як lnn, у той час, як EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-046.gif"росте тільки як ln(ln pn ). Більш того, відомий разючий результат Л. Ейлера про те, що границя EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-059.gif"існує і ??0,5772... . Число ??називається сталою Ейлера.
Встановимо, який зв'язок між дзета-функцією (яка не мультиплікативна) і функцією Мебіуса ??(n) (яка мультиплікативна). З цього зв'язку зрозуміло, що ?(s) дуже близька до мультиплікативних функцій - просто одиниця, ділена на дзета-функцію, є сумою (нескінченною) мультиплікативних функцій.
Лема 2. Нехай Re( s ) > 1. Тоді:
EMBED Equation.3
Доказ. Нехай EMBED Equation.3INCLUDEPICTURE \d \z "../pict/15-050.gif". У лемі 1 з пункту 14 приймемо ??(x)=1/xs - мультиплікативна функція. Тоді:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-051.gif",
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-052.gif",
де значок ?, означає, що підсумовування ведеться по всіх n>X, у розкладі яких немає простих співмножників, більших за Х. Далі, спрямовуючи Х до нескінченності і згадуючи визначення функції Мебиуса, одержуємо:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-053.gif",
отже:
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/15-054.gif". ?
§5. Теорія порівнянь
Пункт 16. Визначення і найпростіші властивості.
Визначення. Нехай а, b ??Z , m ??N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a ??b(mod m) .
Очевидно, що бінарне відношення порівняння ??m є відношенням еквівалентності на множині цілих чисел, або це відношення є конгруенцією кільця Z, фактор-кільце за якою Z/ ??m називається кільцем лишків і позначається Zm.
Зрозуміло, що число a порівняльне з b за модулем m тоді і тільки тоді, коли a-b ділиться на m без остачі. Очевидно, що це буває тоді і тільки тоді, коли знайдеться таке ціле число t, що a=b+mt. Порівняльність a і b за модулем m означає, що a і b є тим самим елементом у кільці Zm.
Процес збирання цілих чисел у класи порівняльних між собою за модулем m (класи еквівалентності ??m ) ілюструє рисунок:
На ньому зображений процес намотування ланцюжка цілих чисел на кільце з m діленнями, при цьому на одне ділення автоматично попадають порівняльні між собою числа. До речі, ця картинка непогано пояснює і термін "кільце".
Перелічимо, далі, властивості порівнянь, схожі на властивості відношення рівності.
Властивість 1. Порівняння за однаковим модулем можна почленно додавати.
Доказ. Нехай a1??b1(mod m), a2??b2(mod m). Це означає, що a1 =b1 +mt1, a2 =b2 +mt2. Після додавання останніх двох рівностей, одержимо a1 +a2 =b1 +b2 +m(t1 +t2 ), що означає a1+a2??b1 +b2 (mod m).
Властивість 2. Доданок, що стоїть в якій-небудь частині порівняння, можна переносити в іншу частину, змінивши його знак на зворотний.
Доказ. EMBED Equation.3.
Властивість 3. До будь-якої частини порівняння можна додати будь-яке число, кратне модулю.
Доказ. EMBED Equation.3.
Властивість 4. Порівняння за однаковим модулем можна почленно перемножувати і, відповідно,
Властивість 5. Обидві частини порівняння можна піднести до однакового степеня.
Доказ. EMBED Equation.3INCLUDEPICTURE \d \z "../pict/16-004.gif".
Наслідком перелічених властивостей, є
Властивість 6. Якщо a0 ??b0 (mod m), a1 ??b1 (mod m),..., an ??bn (mod m), x ??y(mod m), то a0xn+a1 xn-1 +...+an ??b0 yn +b1 yn-1 +...+bn (mod m)
Властивість 7. Обидві частини порівняння можна поділити на їхній спільний дільник, взаємно простий з модулем.
Доказ. Нехай a ??b(mod m) , a=a1 d , b=b1 d . Тоді (a1 -b1 ) ??d ділиться на m. Оскільки d і m взаємно прості, то на m ділиться число (a1 -b1 ), що означає a1 ??b1 (mod m).
Властивість 8. Обидві частини порівняння і його модуль можна помножити на те саме ціле число або розділити на їхній спільний дільник.
Доказ.
a ??b(mod m) ??a=b+mt ??ak=bk+mkt ??ak ??bk(mod mk).
Властивість 9. Якщо порівняння a ??b існує за кількома різними модулями, то воно існує й за модулем, що дорівнює найменшому спільному кратному цих модулів.
Доказ. Якщо a ??b(mod m1 ) і a ??b(mod m2 ), то a-b ділиться на m1 і на m2, отже a-b ділиться на найменше спільне кратне m1 і m2.
Властивість 10. Якщо порівняння існує за модулем m, то воно існує і за модулем d, що дорівнює будь-якому дільнику числа m.
Доказ очевидний (випливає з транзитивності відношення подільності: якщо a ??b(mod m), то a-b ділиться на m, отже a-b ділиться на d, де d|m).
Властивість 11. Якщо одна частина порівняння і модуль діляться на деяке число, то й інша частина порівняння мусить ділитися на те ж число.
Доказ.
a ??b(mod m) ??a=b+mt
Приклад. Довести, що для будь-якого натурального n число 37n+2+16n+1+23n ділиться на 7.
Рішення. Очевидно, що 37 ??2(mod 7), 16 ??2(mod 7), 23 ??2(mod 7)
Піднесемо перше порівняння до степеня n+2, друге – до степеня n+1, третє – до степеня n і додамо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/16-005.gif"
тобто 37n+2+16n+1+23n ділиться на 7.
Пункт 17. Повна і зведена системи лишків.
У попередньому пункті було зазначено, що відношення ??m порівняння за довільним модулем m є відношенням еквівалентності на множині цілих чисел. Це відношення еквівалентності індукує розбиття множини цілих чисел на класи еквівалентних між собою елементів, тобто в один клас об’єднуються числа, що мають при діленні на m однакові залишки. Число класів еквівалентності ??m (індекс еквівалентності ??m) дорівнює m .
Визначення. Будь-яке число з класу еквівалентності ??m називається лишком за модулем m. Сукупність лишків, узятих по одному з кожного класу еквівалентності ??m, називається повною системою лишків за модулем m (у повній системі лишків усього m чисел). Безпосередньо самі залишки ділення на m називаються найменшими невід’ємними лишками і утворюють повну систему лишків за модулем m. Лишок ??називається абсолютно найменшим, якщо ????найменший серед модулів лишків даного класу.
Приклад : Нехай m = 5 . Тоді:
0, 1, 2, 3, 4 - найменші невід’ємні лишки;
-2, -1, 0, 1, 2 - абсолютно найменші лишки.
Обидві наведені множини чисел утворять повні системи лишків за модулем 5 .
Лема 1. 1) Будь-які m попарно непорівняльних за модулем m чисел утворюють повну систему лишків за модулем m .
2) Якщо а і m взаємно прості, а x набуває значень з повної системи лишків за модулем m, то значення лінійної форми ах+b, де b - будь-яке ціле число, також набувають значень з повної системи лишків за модулем m.
Доказ. Твердження 1) – очевидне. Доведемо твердження 2). Чисел ах+b є m штук. Покажемо, що вони між собою непорівняльні за модулем m. Нехай для деяких різних x1 і x2 з повної системи лишків виявилося, що ax1+b??ax2+b(mod m). Тоді, за властивостями порівнянь з попереднього пункту, одержуємо:
ax1 ??ax2 (mod m) x1 ??x2 (mod m)
– протиріччя з тим, що x1 і x2 різні й узяті з повної системи лишків.
Оскільки всі числа з даного класу еквівалентності ??одержуються з одного числа даного класу додаванням числа, кратного m, то всі числа даного класу мають з модулем m той самий найбільший спільний дільник.
Визначення. Зведеною системою лишків за модулем m називається сукупність усіх лишків з повної системи, взаємно простих з модулем m.
Зведену систему звичайно вибирають з найменших невід’ємних лишків. Зрозуміло, що зведена система лишків за модулем m містить ?(m) лишків, де ?(m) – функція Ейлера – кількість чисел, менших за m і взаємно простих з m.
Приклад. Нехай m = 42. Тоді зведеною системою лишків є:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лема 2. 1) Будь-які ?(m) чисел, попарно непорівняльні за модулем m і взаємно прості з модулем, утворюють зведену систему лишків за модулем m.
2) Якщо (a,m)=1 і x набуває значень із зведеної системи лишків за модулем m, то ах так само набуває значень із зведеної системи лишків за модулем m.
Доказ. Твердження 1) – очевидне. Доведемо твердження 2). Числа ах попарно непорівняльні (доводиться так само, як лема 1 цього пункту), їх є ?(m) штук. Зрозуміло, що усі вони взаємно прості з модулем, оскільки (a,m)=1, (x,m)=1 ??(ax.m)=1. Таким чином числа ах утворять зведену систему лишків.
Лема 3. Нехай m1, m2, ..., mk – попарно взаємно прості і m1 m2 ...mk =M1 m1=M2 m2=...=Mk mk, де Mj =m1 ...mj-1 mj+1 ...mk
1) Якщо x1 , x2 , ..., xk набувають значень з повних систем лишків за модулями m1, m2, ..., mk відповідно, то значення лінійної форми M1 x1 +M2 x2 + ...+Mk xk набувають значень з повної системи лишків за модулем m=m1 m2 ...mk .
2) Якщо ?1 , ?2 , ..., ?k набувають значень із зведених систем лишків за модулями m1, m2, ..., mk відповідно, то значення лінійної форми M1 ?1 +M2 ?2 + ...+Mk ?k набувають значень із зведеної системи лишків за модулем m=m1 m2 ...mk .
Доказ.
1) Форма M1 x1 +M2 x2 + ...+Mk xk приймає m1 m2 ...mk=m значень. Покажемо, що ці значення попарно непорівняльні. Нехай
M1 x1 +M2 x2 + ...+Mk xk ??M1 x1??+M2 x2??+ ...+Mk xk ??(mod m)
Усяке Mj, що відмінне від Ms, кратне до ms. Забираючи зліва і справа в останньому порівнянні що додаються, кратні до ms, одержимо:
Ms xs ??Ms xs??(mod ms ) ??xs ??xs??(mod ms )
– протиріччя з тим, що xs набуває значень з повної системи лишків за модулем ms.
2). Форма M1 ?1 +M2 ?2 + ...+Mk ?k приймає ?(m1) ?(m2) ?... ??(mk)=?(m1 m2 ??... ??mk )=?(m) (функція Ейлера мультипликативна!) різних значень, що між собою за модулем m=m1 m2 ...mk попарно непорівняльні. Останнє доводиться міркуваннями, аналогічними з доказом твердження 1) цієї леми. Оскільки (M1?1+M2?2+...+Mk?k,ms)=(Ms?s,ms)=1 для кожного 1?s??k, то (M1?1+M2?2+...+Mk?k ,ms)=1, отже множина значень форми M1?1+M2?2+...+Mk?k утворить зведену систему лишків за модулем m.
Лема 4. Нехай x1, x2, ...,xk , x набувають значень з повної, а ?1, ?2 ,..., ?k , ??– набувають значень із зведених систем лишків за модулями m1, m2, ..., mk і m=m1 m2 ...mk відповідно, де (mi mj )=1 при i?j. Тоді дроби {x1/m1+x2/m2+...+xk /mk } збігаються з дробами {x/m}, а дроби {?1 /m1 +?2 /m2+...+?k /mk} збігаються з дробами {??/m}.
Доказ. Доказ обох тверджень леми 4 одержується із застосуванням попередньої леми 3 після того, як звести кожну суму {x1 /m1 +x2 /m2 +...+xk /mk } і {?1 /m1+?2 /m2+...+?k /mk } до спільного знаменника:
{x1 /m1 +x2 /m2 +...+xk /mk }={(M1 x1 +M2 x2 +...+Mk xk )/m};
{?1 /m1 +?2 /m2 +...+?k /mk }={(M1 ?1 +M2 ?2 +...+Mk ?k )/m},
де Mj =m1 ...mj-1 mj+1 ...mk .
Якщо врахувати, що дробові частини чисел, що одержуються при діленні на модуль m будь-яких двох чисел, порівняльних за модулем m, однакові (вони рівні r/m, де r – найменший невід’ємний лишок даного класу), то твердження дійсної леми очевидні.
Перейдемо до підсумовування комплексних коренів m -ого степеня з одиниці. Позначимо через ?k k -ий корінь m- ого степеня з одиниці:
EMBED Equation.3,INCLUDEPICTURE \d \z "../pict/17-001.gif"
де k=0,1,...,m-1 – набуває значень з повної системи лишків за модулем m.
Нагадаємо, що сума ?0 +?1+...+?m-1 усіх коренів m -ого степеня з одиниці дорівнює нулю для будь-якого m. Нехай ?0 +?1 +...+?m-1 =a. Помножимо цю суму на ненульове число ?1. Таке множення геометрично в комплексній площині означає поворот правильного m -кутника, у вершинах якого розташовані корені ?0, ?1,..., ?m-1, на ненульовий кут 2?/m. При цьому корінь ?0 перейде в корінь ?1, корінь ?1 перейде в корінь ?2, і т.д., а корінь ?m-1 перейде в корінь ?0, тобто сума ?0 + ?1 +...+ ?m-1 не зміниться. Маємо ?1 a=a, звідки a=0.
Теорема 1. Нехай m>0 - ціле число, a ??Z, x набуває значень з повної системи лишків за модулем m. Тоді, якщо а кратне m, то
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/17-002.gif"
в іншому випадку, при а не кратному m, EMBED Equation.3INCLUDEPICTURE \d \z "../pict/17-003.gif".
Доказ. При а кратному m маємо: a=md і
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/17-004.gif".
Якщо а не ділиться на m, то розділимо чисельник і знаменник дробу a/m на d – найбільший спільний дільник а і m, одержимо нескоротний дріб a1 /m1. Тоді, за лемою 1, a1 x набуватиме значень з повної системи лишків за модулем m. Маємо:
EMBED Equation.3,INCLUDEPICTURE \d \z "../pict/17-005.gif"
оскільки сума всіх коренів степеня m1 з одиниці дорівнює нулю.
Нагадаю, що корінь ?k m -ого степеня з одиниці називається первісним, якщо його індекс k взаємно простий з m. У цьому випадку послідовні степені ?k1, ?k2,..., ?km-1 кореня ?k утворять сукупність коренів m -ого степеня з одиниці або, іншими словами, ?k є породжуючим елементом циклічної групи всіх коренів m -ого степеня з одиниці.
Очевидно, що кількість первісних коренів m -ого степеня з одиниці дорівнює ?(m), де ??– функція Ейлера, оскільки індекси первісних коренів утворять зведену систему лишків за модулем m.
Теорема 2. Нехай m>0 – ціле число, ??набуває значень із зведеної системи лишків за модулем m. Тоді (сума первісних коренів степеня m):
EMBED Equation.3,INCLUDEPICTURE \d \z "../pict/17-006.gif"
де ?(m) – функція Мебіуса.
Доказ. Нехай m=p1?1 p2 ?2 ...pk ?k – канонічний розклад числа m; m1 =p1?1, m2 =p2?2, m3=p3?3; ?i набуває значень із зведеної системи лишків за модулем mi. Маємо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/17-007.gif"
При ?s=1 одержується, що лише корінь ?0=1 не є первісним, тому сума всіх первісних коренів є сумою всіх коренів мінус одиниця:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/17-008.gif"
Таким чином, якщо m не ділиться на r2, при r>1, то EMBED Equation.3INCLUDEPICTURE \d \z "../pict/17-009.gif".
Якщо ж який-небудь показник ?s більший за одиницю (тобто m ділиться на r2, при r>1), то сума всіх первісних коренів степеня ms є сумою всіх коренів степеня ms мінус сума всіх не первісних коренів, тобто всіх коренів деякого степеня, меншого за ms. Якщо ms =ps ms* , то:
EMBED Equation.3.INCLUDEPICTURE \d \z "../pict/17-010.gif"
Пункт 18. Теорема Ейлера і теорема Ферма.
Невелике есе про Ейлера
Як учений, Ейлер (1707–1783) сформувався у швейцарському місті Базелеві, університет якого довгий час був осередком європейської науки того часу. Леонард вивчав математику під посібником Йоганна Бернуллі, а коли в 1725 році син Йоганна Микола виїхав у Петербург, молодий Ейлер пішов за ним у недавно засновану Російську (Петербурзьку) Академію Наук. Ейлер жив у Росії до 1741 року, потім перейшов в Берлінську академію під особливе заступництво Фрідріха Другого, а з 1766 року він знову в Росії. Ейлера з повним правом можна вважати російським ученим, тому що основні роки його творчості пройшли в Петербурзі і він був академіком саме Петербурзької Академії Наук під особливим заступництвом Катерини Великої.
Сліпий Ейлер, користаючись своєю феноменальною пам'яттю, диктував свої роботи, загальне число яких досягло 886. Його роботи присвячені аналізу, алгебрі, дискретній математиці (теорії графів), варіаційному численню, функціям комплексної змінної, астрономії, гідравліці, теоретичній механіці, кораблебудуванню, артилерії, теорії музики і т.д., і т.п. Колосальна продуктивність і "пробивна сила" Ейлера в різних областях математики і нематематики була і залишається приводом подиву.INCLUDEPICTURE \d \z "../pict/18-001.gif" Можна скласти довжелезний список відомих і важливих математичних відкриттів, пріоритет у який належить Ейлеру. Можна скласти величезний перелік його ідей, що ще чекають своєї розробки.
Хочеться додати, що в мирському житті Ейлер був розважливою і спокійною людиною. Він був двічі одружений і мав тринадцять дітей. Про його надзвичайну побожність ходять легенди. Говорять, що коли Петербурзький двір відвідав з візитом відомий французький богохульник Вольтер, для ведення суперечки з ним був запрошений Ейлер, що заліз на стілець і гробовий голос вимовив у захист Бога залізний аргумент: "Синус квадрат плюс косинус квадрат дорівнює одиниці, значить Бог існує!". Вольтер у шоку ретирувався у Францію.
Теорема (Ейлер). Нехай m>1, (a,m)=1, ?(m) – функція Ейлера. Тоді:
a?(m) ??1(mod m).
Доказ. Нехай х набуває значення із зведеної системи лишків за mod m:
x=r1,r2,...,rc
де c=?(m) їх кількість, r1,r2,..., rc - найменші невід’ємні лишки за mod m. Отже, найменші невід’ємні лишки, що відповідають числам ax є відповідно:
??1 , ??2 ,..., ??c
– теж набувають значень із зведеної системи лишків, але в іншому порядку (див. Лему 2 з пункту 17). Значить:
a ??r1 ?????(mod m)
a ??r2 ?????(mod m)
...
a ??rc ?????(mod m)
Перемножимо ці с порівнянь. Вийде:
ac r1 r2 ...rc ??j 1 ?j 2 ... ?j c (mod m)
Оскільки r1 r2 ...rc = ?1 ?2 ... ?c ??0 і взаємно просте з модулем m, то, поділивши останнє порівняння на r1 r2 ...rc, одержимо a?(m) ??1(mod m).
Друга теорема цього пункту - теорема Ферма – є безпосереднім наслідком теореми Ейлера.
Теорема (Ферма). Нехай р – просте число, р не ділить a. Тоді:
ap-1 ??1(mod p) .
Доказ 1. Нехай в умові теореми Ейлера m=p, тоді ?(m)=p-1 (див. пункт 14 ). Одержуємо ap-1 ??1(mod p).
Необхідно відзначити важливість умови взаємної простоти модуля і числа a у формулюваннях теорем Ейлера і Ферма. Простий приклад: порівняння 62 ??1(mod 3) очевидно не виконується. Однак можна легко підправити формулювання теореми Ферма, щоб зняти обмеження взаємної простоти.
Наслідок 1. Без всяких обмежень на a ??Z,
ap ??a(mod p) .
Доказ. Помножимо обидві частини порівняння ap-1 ??1(mod p) на a. Зрозуміло, що вийде порівняння, справедливе і при a, кратному р.
Звичайно, доказ 1 теореми Ферма вийшов настільки коротким завдяки проведеній могутній попередній підготовці (доведена теорема Ейлера і вивчені властивості функції ?(m)). Наведемо ще один варіант доказу теореми Ферма.
Доказ 2. Оскільки р - просте число, то всі біноміальні коефіцієнти (крім C0p і Cpp) діляться на р, тому що чисельник виписаного виразу містить р, а знаменник не містить цього множника. Якщо згадати біном Ньютона, то стає зрозуміло, що різниця (A+B)p-Ap -Bp= =Cp1Ap-1B1+Cp2Ap-2B2+...+Cpp-2A2Bp-2+Cpp-1A1Bp-1, де А і В – довільні цілі числа, завжди ділиться на р. Послідовним застосуванням цього спостереження одержуємо, що (A+B+C)p--Ap-Bp-Cp={[(A+B)+C]p-(A+B)p-Cp}+(A+B)p -Ap -Bp завжди ділиться на р; (A+B+C+D)p-Ap–Bp -Cp-Dp завжди ділиться на р; і взагалі, (A+B+C+...+K)p -Ap-Bp-Cp-...-Kp завжди ділиться на р. Нехай A=B=C=...=K=1 і візьмемо кількість цих чисел рівним a. Вийде, що ap-a ділиться на р, а це і є теорема Ферма в більш загальному формулюванні.
Наслідок 2. (a+b)p ??ap +bp (mod p).
Наведемо кілька прикладів застосування теорем Ферма і Ейлера. Зазначимо, що ефективність застосування теорем Ферма і Ейлера ґрунтується на тому, що порівняння, що даються цими теоремами, зручно підносити до степеня, оскільки справа у них стоїть одиниця, що на піднесення до степеня не реагує.
Приклад 1. Дев'ятий ступінь однозначного числа закінчується на 7. Знайти це число.
Розв’язування. a9 ??7(mod 10) – дано. Крім того, (7, 10)=1 і ( a , 10)=1. За теоремою Ейлера, a?(10) ??1(mod 10). Отже, a4 ??1(mod 10) і, після піднесення до квадрату, a8 ?1(mod 10). Поділимо почленно a9 ??7(mod 10) на a8 ??1(mod 10) і одержимо a?7(mod 10). Це означає, що a=7.
Приклад 2. Довести, що 118 +218 +318 +418 +518 +618 ??-1(mod 7)
Доказ. Числа 1, 2, 3, 4, 5, 6 взаємно прості з 7. За теоремою Ферма маємо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/18-003.gif"
Піднесемо ці порівняння до кубу і додамо:
118 +218 +318 +418 +518 +618 ??6(mod 7) ??-1(mod 7)
Приклад 3. Знайти залишок ділення 7402 на 101.
Рішення. Число 101 – просте, (7, 101)=1, отже, за теоремою Ферма: 7100?1(mod 101). Піднесемо це порівняння до четвертої степені: 7400?1(mod 101), домножимо його на очевидне порівняння 72?49(mod 101), одержимо: 7402??49(mod 101). Виходить, що залишок ділення 7402 на 101 дорівнює 49.
Приклад 4. Знайти дві останні цифри числа 243402.
Рішення. Дві останні цифри цього числа є залишком ділення його на 100. Маємо: 243=200+43; 200+43 ??43(mod 100) і, піднімаючи останнє очевидне порівняння в 402-у степінь, розкриємо його ліву частину за біномом Ньютона. У цьому гігантському виразі всі доданки, крім останнього, містять ступінь числа 200, тобто діляться на 100, тому їх можна викинути з порівняння, після чого зрозуміло, чому 243402 ??43402(mod 100). Далі, 43 і 100 взаємно прості тому, за теоремою Ейлера, 43?(100)?1(mod 100). Вважаємо:
?(100)= ?(22 ??52 )=(10–5)(10–2)=40.
Маємо порівняння: 4340?1(mod 100), що піднесемо в десяту степінь і помножимо почленно на порівняння: 432 ??49(mod 100). Одержимо:
EMBED Equation.3
отже, дві останні цифри числа 243402 є 4 і 9.
Приклад 5. Довести, що (7312 -1) поділяється на 105.
Рішення. Маємо: 105=3 ??5 ??7, (73,3)=(73,5)=(73,7)=1. По теоремі Ферма:
732 ??1(mod 3)
734 ??1(mod 5)
736 ??1(mod 7)
Перемножуючи, одержуємо:
7312 ??1(mod 3),(mod 5),(mod 7),
звідки, за властивостями порівнянь, з пункту 16, випливає:
7312 -1 ??0(mod 105),
Пункт 19. Порівняння першого степеня.
У наступних трьох пунктах навчимося розв’язувати порівняння з одним невідомим виду:
f(x) ??0(mod m),
де f(x)=a0 xn +a1 xn-1 +...+an-1 x+an – многочлен з цілими коефіцієнтами. Якщо m не ділить a0, то говорять, що n – ступінь порівняння. Зрозуміло, що якщо яке-небудь число х підходить для порівняння, то для цього ж порівняння підійде і будь-яке інше число, порівняльне з х за mod m.
Розв’язати порівняння – означає знайти всі ті х, що задовольняють даному порівнянню, при цьому весь клас чисел за mod m вважається одним розв’язком.
Таким чином, число розв’язків порівняння є числом лишків з повної системи, що цьому порівнянню задовольняють.
Приклад. Дано порівняння: x5 +x+1 ??0(mod 7)
З чисел: 0, 1, 2, 3, 4, 5, 6, це порівняння задовольняють два: x1 =2, x2 =4. Це означає, що в даному порівнянні два розв’язки:
x ??2(mod 7) і x ??4(mod 7) .
Порівняння називаються рівносильними, якщо вони мають однакові розв’язки – повна аналогія з поняттям рівносильності рівнянь. Однак, на відміну від алгебраїчних рівнянь, що часто нерозв'язуються радикалами, порівняння будь-якого ступеня завжди розв’язується, наприклад, перебором усіх лишків за mod m. Перебір і підставлення всіх лишків - найчастіше дуже довгий процес (особливо, при великих m і n), але і тут існують набори інструкцій, виконуючи які можна завжди знайти всі розв’язки даного порівняння будь-якого степеня, минаючи процес перебору.
Розглянемо порівняння першого степеня виду ax??b(mod m), (два випадки).
Випадок 1. Нехай а і m взаємно прості. Тоді нескоротний дріб m/a розкладається в ланцюговий дріб:
EMBED Equation.3
Цей ланцюговий дріб, зрозуміло, скінченний, тому що m/a - раціональне число. Розглянемо два останні прямуючі дроби:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-002.gif"; EMBED Equation.3
Згадуємо (пункт 9) властивість чисельників і знаменників прямуючих дробів: mn-1-an-1=
=(-1)n. Далі (доданок mn-1, кратний m, можна викинути з лівої частини порівняння):
-an-1 ??(-1)n (mod m) тобто
an-1 ??(-1)n-1 (mod m) тобто
a[(-1)n-1 Pn-1 b] ??b(mod m)
і єдиним розв’язком вихідного порівняння є:
x ??(-1)n-1 Pn-1 b(mod m)
Приклад. Розв’язати порівняння 111x ??75(mod 322).
Розв’язування. (111, 322)=1. Включаємо алгоритм Евкліда:
322=11 · 2+100
111=100 · 1+11
100=11 · 9+1
11=1 · 11
(У рівностях підкреслені неповні частки.) Виходить, n=4, а відповідний ланцюговий дріб:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-003.gif"
Порахуємо чисельники прямуючих дробів, склавши для цього стандартну таблицю:
Чисельник передостаннього прямуючого дробу дорівнює 29, отже, маємо відповідь:
x ??(-1)3 ??29 ??75 ??-2175 ??79(mod 322)
Іншими словами, дано порівняння ax ??b(mod m), де a і m взаємно прості. Візьмемо алгоритм Евкліда і знайдемо u, v ??Z такі, що au+vm=1. Помножимо цю рівність на b: aub+vmb=b, звідки випливає: aub ??b(mod m). Отже розв’язком вихідного порівняння є x??ub(mod m).
Випадок 2. Нехай (a,m)=d. У цьому випадку, для можливості розв'язку порівняння ax??b(mod m) необхідно, щоб d ділило b, інакше порівняння узагалі виконуватися не може. Дійсно, ax??b(mod m) буває тоді, і тільки тоді, коли ax-b ділиться на m без остачі, тобто ax-b=t · m,
t ??Z, звідки b=ax-t ??m , а права частина останньої рівності кратна d.
Нехай b=db1, a=da1, m=dm1. Тоді обидві частини порівняння xa1 d??b1 d(mod m1 d) і його модуль поділимо на d :
xa1 ??b1 (mod m1),
де вже а1 і m1 взаємно прості. Згідно випадку 1 цього пункту, таке порівняння має єдиний розв’язок x0 :
x ??x0 (mod m1 ) (*)
За вихідним модулем m, числа (*) утворять стільки розв’язків вихідного порівняння, скільки чисел виду (*) міститься в повній системі лишків: 0,1,2,..., m-2, m-1. Очевидно, що з чисел x=x0+t??m в повну систему найменших невід’ємних лишків попадають лише x0, x0+m1, x0+2m1, ..., x0+(d-1)m1, тобто усього d чисел. Значить у вихідного порівняння є d розв’язків.
Теорема 1. Нехай (a,m)=d . Якщо b не ділиться на d, то порівняння ax??b(mod m) немає розв’язків. Якщо b кратне d, то порівняння ax??b(mod m) має d розв’язків.
Приклад. Розв’язати порівняння 111x ??75(mod 321) .
Розв’язування. (111,321)=3, тому поділимо порівняння і його модуль на 3:
37x ??25(mod 107) і (37,107)=1.
Включаємо алгоритм Евкліда (підкреслені неповні частки):
107=37 ??2+33
37=33 ??1+4
33=4 ??8+1
4=1 ??4
Маємо n=4 і ланцюговий дріб такий:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-004.gif"
Таблиця для знаходження чисельників прямуючих дробів:
Одержуємо, x ??(-1)3 ??26 ??25 ??-650(mod 107) ??-8(mod 107) ??99(mod 107).
Три розв’язки вихідного порівняння:
x??99(mod 321), x??206(mod 321), x??313(mod 321),
і інших розв’язків немає.
Розглянемо інші способи розв’язування порівнянь першого ступеня. Ці способи викладаються далі у виді теорем.
Теорема 2. Нехай m>1, (a,m)=1 Тоді порівняння ax??b(mod m) має розв’язок:
x?ba?(m)-1(mod m).
Доказ. За теоремою Ейлера, маємо: a?(m)??1(mod m), отже, a??ba?(m)-1??b(mod m).
Приклад. Розв’язати порівняння 7x??3(mod 10). Обчислюємо:
?(10)=4; x??3 ??74-1 (mod 10) ??1029(mod 10) ??9(mod 10).
Цей спосіб розв’язування порівнянь гарний, але може зажадати піднесення числа а до великого степеня.
Теорема 3. Нехай р – просте число, 0<a<p. Тоді порівняння ax??b(mod p) має розв’язок:
EMBED Equation.3
де Ca p – біноміальний коефіцієнт.
Доказ випливає з очевидного порівняння
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-006.gif"
яке необхідно почленно поділити на взаємно просте з модулем число 1 ??2 ??3 ??... ??a-1.
Приклад. Розв’язати порівняння 7x ??2(mod 11) . Обчислюємо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-008.gif"
Перейдемо до систем порівнянь першого степеня.
Лема 1 (Китайська теорема про лишки). Нехай дана найпростіша система порівнянь першого степеня:
EMBED Equation.3 (*)INCLUDEPICTURE \d \z "../pict/19-009.gif"
де m1,m2,...,mk попарно взаємно прості. Нехай, m1 m2 ...mk =Ms ms; Ms Ms????1(mod ms) (Очевидно, що таке число Ms???завжди можна підібрати хоча б за допомогою алгоритму Евкліда, оскільки (ms, Ms )=1); x0 =M1 M1??b1+M2 M2??b2 +...+Mk Mk??bk. Тоді система (*) рівносильна одному порівнянню
x ??x0 (mod m1 m2 ...mk ),
а саме набір розв’язків (*) збігається з набором розв’язків порівняння x??x0(mod m1m2 ...mk).
Доказ. Маємо: ms ділить Mj, при s?j. Отже, x0 ??Ms Ms??bs (mod ms), звідки x0??bs(mod ms). Це означає, що система (*) рівносильна системі
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/19-010.gif"
яка, у свою чергу, рівносильна одному порівнянню x??x0 (mod m1 m2 ...mk ).
Приклад. Знайти число, що при діленні на 4 дає в залишку 1, при діленні на 5 дає в залишку 3, а при діленні на 7 дає в залишку 2.
Складемо систему:
EMBED Equation.3,INCLUDEPICTURE \d \z "../pict/19-011.gif"
яку розв’язуємо за допомогою леми 1.
b1 =1; b2 =3; b3 =2; m1 m2 m3 , тобто M1 =35, M2 =28, M3 =20.
35 ??3 ??1(mod 4)
28 ??2 ??1(mod 5)
20 ??6 ??1(mod 7)
тобто M1??=3, M2??=2, M3??=6. Значить x0 =35 ??3 ??1+28 ??2 ??3+20 ??6 ??2=513. Після цього, за лемою 1:
x ??513(mod 140) ??93(mod 140),
а саме найменше додатне число дорівнює 93.
У наступній лемі, для стислості формулювання, збережені позначення леми 1.
Лема 2. Якщо b1 ,b2 ,...,bk набувають значення з повних систем лишків за модулями m1,m2,...,mk відповідно, то x0 набуває значення з повної системи лишків за модулями m1 m2 ...mk .
Доказ. Дійсно, x0 =A1 b1 +A2 b2 +...+Ak bk набуває m1 m2 ...mk різних значень. Покажемо, що усі вони попарно непорівняльні за модулями m1 m2 ...mk .
Нехай виявилося, що
A1 b1 +A2 b2 +...+Ak bk ??A1 b'1 +A2 b'2 +...+Ak b'k (mod m1 m2 ...mk ).
Тоді
A1 b1 +A2 b2 +...+Ak bk ??A1 b'1 +A2 b'2 +...+Ak b'k (mod ms )
для кожного s, звідки
Ms Ms??bs ??Ms Ms??b's
Згадаємо тепер, що Ms Ms????1(mod ms), значить Ms Ms????1+ms??t, звідки (Ms Ms??,ms)=1. Розділивши тепер обидві частини порівняння
Ms Ms??bs ??Ms Ms??b's
на число Ms Ms??, взаємно просте з модулем, одержимо, що bs ??b's (mod ms), тобто bs=b's для кожного s.
Отже, x0 набуває m1 m2 ...mk різних значень, попарно непорівняльних за модулями m1 m2 ...mk , а саме значення з повної системи лишків.
Пункт 20. Порівняння будь-якого степеня за простим модулем.
У цьому пункті розглянемо порівняння виду f(x) ??0(mod p), де р - просте число, f(x)=axn +a1 xn-1+…+an-многочлен з цілими коефіцієнтами, і навчимося ці порівняння розв’язувати.
Лема 1. Довільне порівняння f(x) ??0(mod p), де р - просте число, рівносильне деякому порівнянню степеня не вищого за p-1.
Доказ. Розділимо f(x) на многочлен xp-x ("многочлен ділення круга") із залишком: f(x)=(xp-x)??Q(x)+R(x), де, як відомо, степінь залишку R(x) не перевищує р-1. Але за теоремою Ферма, xp-x??0(mod p). Це означає, що f(x)??R(x)(mod p), а вихідне порівняння рівносильне порівнянню R(x)??0(mod p).
За допомогою доведеної леми можна звести розв’язування порівняння високого степеня до розв’язування порівняння меншого степеня.
Лема 2. Якщо порівняння axn+a1 xn-1+…+an??0(mod p) степеня n за простим модулем р має більше n різних розв’язків, то всі коефіцієнти a,a1 ,…,an кратні р.
Доказ. Нехай порівняння axn +a1 xn-1+…+an??0(mod p), має n+1 розв’язок і x1 ,x2 ,…,xn,xn+1–найменші невід’ємні лишки цих розв’язків. Тоді многочлен f(x) представимо у виді:
f(x)=a(x-x 1 )(x-x 2 )…(x-xn-2)(x-xn-1)(x-xn)+
+b(x-x1)(x-x2)…(x-xn-2)(x-xn-1)+
+c(x-x1)(x-x2)…(x-xn-2)+
+…+
+k(x-x1)(x-x2)+
+l(x-x1)+
+m.
Дійсно, коефіцієнт b мусить дорівнювати коефіцієнту при xn-1 у різниці f(x)-a(x-x1 )(x-x2)…(x-xn); коефіцієнт с – це коефіцієнт перед xn-2 у різниці f(x)-a(x-x1 )(x-x2 )…(x-xn)-b(x-x1)(x-x2)…(x-xn-1),і т.д.
Тепер підставимо послідовно x=x1 ,x2 ,…,xn,xn+1... Маємо:
f(x1)=m ??0(mod p), отже, р ділить m.
f(x2 )=m+l(x2 -x1 ) ??l(x2 -x1 )??0(mod p), отже, р ділить l, тому що р не може поділяти x2 -x1, оскільки x2<p, x1<p.
f(x3)??k(x3 -x1 )(x3 -x2 )??0(mod p), отже, р ділить k. І т.д.
Виходить, що всі коефіцієнти a, b, c,...,k, l кратні р. Це означає, що всі коефіцієнти a,a1,…,an теж кратні р, адже вони є сумами чисел, кратних р. (Переконайтеся в цьому самостійно, розкривши дужки в написаному вище розкладі многочлена f(x) на суми добутків лінійних множників.)
Зверніть увагу на умови простоти модуля порівняння у формулюванні леми 2. Якщо модуль- число складне, то порівняння n-ого степеня може мати більше n розв’язків, при цьому, коефіцієнти многочлена не мусять бути кратними р. Приклад: порівняння другого степеня x2?1(mod 16) має аж цілих чотири різних розв’язки:
x?1(mod 16), x?7(mod 16), x??9(mod 16), x?15(mod 16).
Довільне нетривіальне порівняння за mod p рівносильне порівнянню степеня не вищого за p-1 і має не більше p-1 розв’язків.
Теорема (Вільсона). Порівняння (p-1)!+1??0(mod p) виконується тоді і тільки тоді, коли р- просте число.
Доказ. Нехай р - просте число. Якщо р=2, то 1!+1 ??0(mod 2). Якщо р>2, то розглянемо порівняння:
[(x-1)(x-2)…(x-(p-1))]-(xp-1-1)??0(mod p) .
Зрозуміло, що це порівняння степеня не вищого за р-2, але воно має р-1 розв’язок: 1, 2, 3, ... , р-1, тому що при підстановці кожного з цих чисел, доданок у квадратних дужках стає рівним нулю, а (xp-1 ) порівняльне з нулем за теоремою Ферма (х і р взаємно прості, тому що х<р). Це означає, за лемою 2, що всі коефіцієнти виписаного порівняння кратні р, зокрема, на р ділиться його вільний член, рівний 1 ??2 ??3 ??... ??(р–1)+1.
Оскільки коефіцієнти многочлена є значеннями симетричних многочленів від його коренів, то тут з’явився шлях для доказу порівнянь для симетричних многочленів.
Назад. Якщо р – не просте, то знайдеться дільник d числа р, 1<d<p. Тоді (р–1)! ділиться на d, тому (р–1)!+1 не може ділитися на d і, виходить, не може ділитися також і на р. Отже, порівняння (p-1)!+1 ??0(mod 2) не виконується.
Приклад. 1??2??3??... ??10+1=3628800+1=3628801 – ділиться на 11 (Ознака ділення на 11- якщо сума цифр у десятковому записі числа на парних позиціях збігається із сумою цифр на непарних позиціях, то число кратне 11).
Приклад-задача. Довести, що якщо просте число р представляється у виді 4n+1, то існує таке число х, що х 2 +1 ділиться на р.
Розв’язування. Нехай р=4n+1 – просте число. За теоремою Вільсона, (4n)!+1 ділиться на р. Замінимо у виразі 1??2??3??... ??(4n)+1 усі множники більші за (p-1)/2=2n на різниці числа р і чисел менших за (p-1)/2=2n. Одержимо:
(p-1)!+1=1??2??3??… ??2n??(p-2n)(p-2n+1)??… ??(p-1)=(1??2??3??… ??2n)[A??p+(-1)2n ??2n??(2n-1)??…??2??1]+1 = A1 p+(1 ??2 ??3 ??… ??2n)2)+1.
Оскільки це число ділиться на р, то й сума (1 ??2 ??3 ??… ??2n)2 +1 ділиться на р, тобто x=(2n)!=((p-1)/2)!.
Натуральне число N тоді і тільки тоді представляється у виді суми двох квадратів, коли в розкладі N на прості множники всі прості множники виду 4n+3 входять у парних степенях. Спробуйте самостійно довести це твердження.
Теорема. Для будь-якого натурального k існує таке натуральне N, яке залежить від k, що кожне натуральне число представляється у виді суми не більш ніж N доданків, що є k-ми степенями цілих чисел.
Для цієї теореми відомо кілька різних неелементарних доказів, але в 1942 році ленінградський математик Ю.В. Лінник придумав чисто арифметичний елементарний доказ, що, однак, є винятково складним. Що стосується функції N(k ), то тут, у даний час майже нічого не зрозуміло. Всяке натуральне число представляється у виді суми чотирьох квадратів, дев'яти кубів (число 9 не може бути зменшене), 21 штуки четвертих ступенів (от отут, здається, що 21 може бути зменшене до 19). Далі – повний туман. Усяке раціональне число представляється у виді суми трьох кубів раціональних чисел.
Доказ цього твердження вперше отримано в 1825 році. Виглядає воно разюче: для раціонального числа а безпосередньо пишеться його представлення у виді суми трьох кубів раціональних чисел:
EMBED Equation.3
Пункт 21. Порівняння будь-якого степеня за складним модулем.
Теорема 1. Якщо числа m1, m2,…mk попарно взаємно прості, то порівняння f(x)?0(mod m1m2 … mk ) рівносильне системі порівнянь:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-001.gif"
При цьому, якщо Т1, Т2, ..., Тк — кількість розв’язків окремих порівнянь цієї системи за відповідними модулями, то кількість розв’язків Т вихідного порівняння дорівнює Т1Т2...Тк.
Доказ. Перше твердження теореми (про рівносильність системи і порівняння) очевидно, тому що якщо a?b(mod m), то a?b(mod d), де d ділить m. Якщо ж a?b(mod m1) і a?b(mod m2), то a?b(mod HСK (m1, m2)), де НСК (m1, m2)– найменше спільне кратне m1 і m2. (Згадайте властивості порівнянь з пункту 16).
Перейдемо до другого твердження теореми (про кількість розв’язків порівняння).
Кожне порівняння f(x)??0(mod ms) виконується тоді і тільки тоді, коли виконується одне з Ts порівнянь виду x ??bs(mod ms), де bs набувають значення лишків розв’язків порівняння f(x)??0(mod ms). Усього різних комбінацій таких найпростіших порівнянь
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-002.gif"
Т1Т2...Тk штук. Усі ці комбінації, за лемою 2 пункту 19, приводять до різних класів лишків за mod(m1m2…mk)...
Отже, розв’язування порівняння EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-003.gif"зводиться до розв’язування порівнянь виду f(x)??0(mod pa). Виявляється, що розв’язування цього останнього порівняння, у свою чергу, зводиться до розв’язування деякого порівняння g(x)??0(mod p) з іншим многочленом у лівій частині, але вже з простим модулем, що було розглянуто в попередньому пункті. Зведемо розв’язування порівняння f(x)?0(mod pa) до розв’язування порівняння g(x)??0(mod p).
Процес зведення.
Очевидно, що з виконання порівняння f(x)??0(mod pa) випливає те, що х підходить у порівняння f(x)?0(mod p). Нехай x??x1(mod p) – який-небудь розв’язок порівняння f(x)??0(mod p). Це означає, що
x = x1 + p ??t1, де t1 ??Z.
Підставимо це х у порівняння f(x)?0(mod p2). Одержимо порівняння
f(x1+p??t1)??0(mod p2),
яке теж, мабуть, виконується.
Розкладемо далі ліву частину отриманого порівняння за формулою Тейлора за степенями (х - х1):
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-004.gif"
Оскільки x=x1+p??t1, то
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-005.gif".
Зауважимо, що число f(k)(x1)/ k! завжди ціле, бо f(x1+p??t1) – многочлен з цілими коефіцієнтами. Тепер у порівнянні
f(x1+p?t1)??0(mod p2)
можна зліва відкинути члени, кратні р2:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-006.gif".
Розділимо останнє порівняння і його модуль на р:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-007.gif".
Зауважимо знову, що f(x1)/ p – ціле число, тому що f(x1)?0(mod p). Далі обмежимося випадком, коли значення похідної f??(x1) не ділиться на р. У цьому випадку існує єдиний розв’язок порівняння першого степеня
EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/21-007.gif"відносно t1: t1?t1??(mod p).
Це означає, що t1=t1??+p?t2, де t2 ??Z, і
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-008.gif".
Підставимо це x=x2 +p2t2 у порівняння f(x)??0(mod p3) (але тепер це порівняння за mod p3), розкладемо його ліву частину за формулою Тейлора за степенями (х-х2) і відкинемо члени, кратні p3:
f(x2)+(f??(x2)/1!)??p2t2 ?0(mod p3).
Поділимо це порівняння і його модуль на р2:
f(x2)/p2+f??(x2)??t2?0(mod p).
Знову ж f(x2)/p2 – ціле число, адже число t1??таке, що f(x1+p??t1??)?0(mod p2). Крім того, x2?x1(mod p), значить f??(x2)??f??(x1)(mod p), тобто f??(x2), як і f?(x1), не ділиться на р. Маємо єдиний розв’язок порівняння першого степеня f(x2)/p2+f??(x2)??t2)?0(mod p) відносно t2:
t2?t2??(mod p).
Це означає, що t2= t2??+p?t3, де t3?Z, і
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-009.gif"
і процес продовжується далі, аналогічно попереднім крокам, до досягнення степеня pa, у якому стоїть просте число р у модулі вихідного порівняння f(x)?0(mod pa).
Отже:
Всякий розв’язок x?x1(mod p) порівняння f(x)?0(mod p), за умови p/f???(x1), дає один розв’язок порівняння f(x)?0(mod pa) виду x?xa+pata, тобто x?xa(mod pa).
Приклад. Розв’язати порівняння x4+7 x+4??0(mod27).
Розв’язування. 27=33. Можна перевірити перебором повної системи лишків за mod3, що порівняння x4+7 x+4?0(mod3) має єдиний розв’язок x?1(mod3).
f??(x)=(4 x3+7)??x?1?2(mod3),
тобто не ділиться на р=3. Далі:
x1=1+3??t1
f(1)+ f??(1) 3 ??t1?0(mod32)
Шукаємо t1:
3+3 t1?2?0(mod9),
після ділення на р=3:
1+2 t1?0(mod3),
t1?1(mod3) - єдиний розв’язок. Далі:
t1=1+3 t2, x=1+3 t1=4+9 t2,
f (4)+9??t2??f??(4)??0(mod p3=27), 18+9??20??t2?0(mod27),
і, після ділення на p2=9, шукаємо t2:
2+20 t2?0(mod3),
t2?2(mod3), t2=2+3 t3,
звідки
x=4+9?(2+3 t3)=22+27 t3.
Отже, єдиним розв’язком вихідного порівняння є x?22(mod27).
Наступна теорема відноситься до специфічного виду порівнянь.
Теорема 2. Нехай A, m, n - натуральні числа; (A, m)=1, x?x0(mod m) – один з розв’язків порівняння xn?A(mod m).
Тоді всі розв’язки цього порівняння одержуються множенням x0 на лишки розв’язків порівняння yn?1(mod m).
Доказ. Перемножимо порівняння:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/21-010.gif"
звідки видно, що x0y — розв’язок порівняння xn?A(mod m).
Якщо тепер y1?y2(mod m)INCLUDEPICTURE \d \z "../pict/21-011.gif", то x0y1?x0y2(mod m)INCLUDEPICTURE \d \z "../pict/21-012.gif". Дійсно, припустимо, що x0y1??x0y2(mod m). Очевидно, що (x0, m)=1, тому що інакше було б:
x0=d?x0?, m=d?m?,
x0=dn(x0)n?A(mod d m?),
отже d ділить А і ділить m, що суперечить взаємній простоті А і m. Отже (x0, m)=1 і порівняння x0 y1?x0 y2(mod m) можна поділити на x0: y1?y2(mod m) – а це суперечить початковому припущенню. Таким чином, для різних y1 і y2, виходять різні розв’язки.
Залишилося переконатися, що кожний розв’язок порівняння xn?A(mod m) одержується саме таким способом. Маємо:
xn?A(mod m) x0n?A(mod m),
отже, xn?x0n(mod m). Візьмемо число y таке, що x?y?x0(mod m). Тоді ynx0n??x0n(mod m), тобто yn?1(mod m).
Пункт 22. Порівняння другого степеня. Символ Лежандра.
Розглянемо найпростіші двочленні порівняння другого степеня виду
x2?a(mod p),
де а і р взаємно прості, а р - непарне просте число. Зверніть увагу, що умова взаємної простоти (а, р)=1 виключає з нашого розгляду випадок а =0.
Нас буде цікавити питання, при яких а найпростіше двочленне порівняння другого степеня має розв’язок, а при яких – не має. Зрозуміло, що порівняння x2?a(mod 2) має розв’язок при будь-яких а, тому що замість а достатньо підставити тільки 0 або 1, а числа 0 і 1 є квадратами. Саме тому випадок р=2 не представляє особливого інтересу і виводиться з подальшого розгляду.
Що стосується порівняння x2?0(mod p), то воно завжди має розв’язок х=0. Отже, інтерес представляє лише ситуація з непарним простим модулем і а?0.
Визначення. Якщо порівняння x2?a(mod p) має розв’язок, то число а називається квадратним лишком за модулем р. В іншому випадку, число а називається квадратним нелишком за модулем р.
Отже, якщо а – квадрат деякого числа за модулем р, то а -“квадратний лишок”, якщо жодне число в квадраті не порівнянльне з а за модулем р, то а - “квадратний нелишок”.
Приклад. Число 2 є квадратом за модулем 7, бо
42?16?2(mod7). Виходить, 2 - квадратний лишок. (Порівняння x2?2(mod7) має ще й інший розв’язок: 32?9?2(mod7).) Навпаки, число 3 є квадратним нелишком за модулем 7, тому що порівняння x2?3(mod7) розв’язків не має, у чому неважко переконатися послідовним перебором повної системи лишків: x = 0,1,2,3,4,5,6.
Спостереження: Якщо а - квадратний лишок за модулем р, то порівняння x2?a(mod p) має лише два розв’язки. Дійсно, якщо а - квадратний лишок за модулем р, то в порівняння x2?a(mod p) є хоча б один розв’язок x?x1(mod p). Тоді x2=-x1 – теж розв’язок, адже (-x1)2=x12. Ці два розв’язки непорівняльні за модулем р>2, бо з x1?-x1(mod p) випливає 2x1?0(mod p), тобто (оскільки р??2) x1?0(mod p), що неможливо, тому що а??0.
Оскільки порівняння x2?a(mod p) є порівнянням другого степеня за простим модулем, то більше двох розв’язків воно мати не може (див. пункт 20, лема 2).
Спостереження: Зведена (тобто без нуля) система лишків
EMBED Equation.3
за модулем р складається з (p-1)/2 квадратних лишків, порівняльних з числами 12,22,…,((p-1)/2)2,і (p-1)/2 квадратних нелишків, тобто лишків і нелишків порівну.
Дійсно, квадратні лишки порівняльні з квадратами чисел
EMBED Equation.3
тобто з числами 12,22,…,((p-1)/2)2, при цьому всі ці квадрати різні за модулем р, тому що з k2?l2(mod p), де 0<k<l??(p-1)/2, випливає, що нетривіальне порівняння x2?k2(mod p) має аж чотири розв’язки: l, –l, k, –k, що неможливо (див. пункт 20, лема 2).
Французький математик Адріен-Марі Лежандр запропонував ввести зручний символ (a/p), який читається: “символ Лежандра а по пе”.
Визначення. Нехай а не кратне р. Тоді символ Лежандра визначається як:
EMBED Equation.3
Теорема. (Критерій Ейлера) Нехай а не кратне р. Тоді:
a(p-1)/2?(a/p)(mod p).
Доказ. За теоремою Ферма, ap-1?1(mod p) тобто
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/22-002.gif". В лівій частині останнього порівняння один співмножник ділиться на р, адже обидва співмножники на р ділитися не можуть, інакше їхня різниця, що дорівнює двом, ділилася б на р>2. Отже, можливе одне і тільки одне з порівнянь:
a(p-1)/2?1(mod p)
a(p-1)/2?-1(mod p)
Але довільний квадратний лишок а задовольняє при деякому х порівняння a?x2(mod p) і, отже, задовольняє також одержаному з нього почленним піднесенням до степеня (p-1)/2 порівнянню
a(p-1)/2?xp-1?1(mod p) (знову теорема Ферма). При цьому, квадратні лишки є всіма розв’язками порівняння
a(p-1)/2?1(mod p), оскільки, будучи порівнянням степеня (p-1)/2, воно не може мати більше (p-1)/2 розв’язків. Це означає, що квадратні нелишки задовольняють порівнянню a(p-1)/2?-1(mod p)
(Властивість a(p-1)/2?(a/p)(mod p), що дає критерій Ейлера, можна прийняти за визначення символу Лежандра, показавши попередньо за теоремою Ферма, що a(p-1)/2??1(mod p).
Приклад. Чи буде число 5 квадратом за модулем 7?
5(7-1)/2=53=125=18??7-1?-1(mod7),
тобто порівняння x2?5(mod7) розв’язків не має і 5 - квадратний нелишок за модулем 7. Перелічимо найпростіші властивості символу Лежандра.
Властивість 1. Якщо a?b(mod p), то (a/p)=(b/p).
Ця властивість випливає з того, що числа того самого класу за модулем р будуть всі одночасно квадратними лишками або квадратними нелишками.
Властивість 2. (1/p)=1.
Доказ очевидний, адже одиниця є квадратом.
Властивість 3.INCLUDEPICTURE \d \z "../pict/22-003.gif" EMBED Equation.3.
Доказ цієї властивості випливає з критерію Ейлера при а=-1. Оскільки (p-1)/2 – парне, якщо р виду 4n+1, і непарне, якщо р виду 4n+3, то число -1 є квадратним лишком за модулем р тоді і тільки тоді, коли р виду 4n+1.
Властивість 4. INCLUDEPICTURE \d \z "../pict/22-004.gif"EMBED Equation.3.
Дійсно, EMBED Equation.3лишкамиINCLUDEPICTURE \d \z "../pict/22-005.gif". Властивість 4 поширюється на будь-яке число співмножників у чисельнику символу Лежандра, взаємно простих з р. Крім того, з неї випливає
Властивість 5. EMBED Equation.3INCLUDEPICTURE \d \z "../pict/22-006.gif", тобто в чисельнику символу Лежандра можна відкинути будь-який квадратний множник. Дійсно:
EMBED Equation.3.INCLUDEPICTURE \d \z "../pict/22-007.gif"
Пункт 23. Інші властивості символу Лежандра. Закон взаємності Гауса.
Історичний відступ про Гауса.
Карл Фрідріх Гаус (1777–1855) – народився в німецькому містечку Брауншвейгу. Дебютом Гауса був доказ можливості побудови правильного сімнадцятикутника циркулем і лінійкою. У 1795 – 1798 роках юний геній учився в Геттінгенському університеті, у 1799 році він одержав ступінь доктора, а з 1807 року до самої смерті він спокійно працював як директор астрономічної обсерваторії і професор математики Геттінгенського університету.
Володіючи феноменальними обчислювальними здібностями, Гаус склав величезні таблиці простих чисел (йому були відомі всі прості числа, менші п'яти мільйонів) і самостійно, шляхом їхнього разгляду, він відкрив квадратний закон взаємності (до Гауса цей закон вперше помітив Ейлер, але не зміг його довести): якщо р и q – два непарних простих числа, то EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-001.gif"
Сам Гаус не користувався для запису цього закону символом Лежандра, хоча знав цей формалізм, та й виразу “квадратна взаємність” у Гауса немає (його потім придумав Діріхле). У знаменитій книзі Гауса “Арифметичні дослідження”, що вважається родоначальницею сучасної теорії чисел (видана в Лейпцігу, у 1801 році), відзначається, що сам закон квадратної взаємності вперше сформулював Ейлер, докладно обговорював Лежандр, але до 1801 року не було опубліковано жодного строгого доказу цього закону. Свій перший доказ закону взаємності Гаус одержав у 1796 році, у дев'ятнадцятирічному віці. Настільки видатний результат Гауса був названий сучасниками “золотою теоремою”.
Нехай р – непарне просте число, S={1,2,…,(p-1)/2}-множина всіх додатних чисел із зведеної системи лишків за модулем р.
Розглянемо порівняння a??s???s rs(mod p), де а - чисельник досліджувального символу Лежандра, s??S, ?s rs - абсолютно найменший лишок числа as за модулем р (тобто лишок, абсолютна величина якого найменша), rs - абсолютна величина цього лишку, а ?s, - його знак. Таким чином, rs??S, а ?s=??1.
Лема 1 (Гаус).INCLUDEPICTURE \d \z "../pict/23-002.gif" EMBED Equation.3.
Доказ. Розглянемо порівняння
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-003.gif"(*)
Множина чисел
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-004.gif"
є зведеною системою лишків за модулем р (див. пункт 17, лема 2). Їхні абсолютно найменші лишки є, відповідно,
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-005.gif",
додатні з них, а саме r1, r2,…,r(p-1)/2, збігаються з числами 1,2,…,(p-1)/2, тобто утворять множину S. Перемножимо тепер почленно порівняння (*) і скоротимо добуток на
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-006.gif". Одержимо: a(p-1)/2???1?2 … ?(p-1)/2(mod p)
За критерієм Ейлера з попереднього пункту, a(p-1)/2?(a/p)(mod p) тобто EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-002.gif", що і було потрібно.
Лема 2. При непарному а,
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-007.gif", де [ as/p ] - ціла частина числа as/p.
Доказ. Маємо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-008.gif",
що буде парним чи непарним, залежно від того, чи буде найменший невід’ємний лишок числа as меншим або більшим числа p/2, тобто чи буде ?s=1 чи ?s=-1. Звідси,
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-009.gif", тому, за лемою Гауса, INCLUDEPICTURE \d \z "../pict/23-010.gif".
Перетворимо цю рівність (пам'ятаємо, що а+р – парне, а квадратний множник з чисельника символу Лежандра можна відкидати):
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-013.gif"
Оскільки (2 a/ p)=(2/ p)( a / p), а EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-011.gif", то лема 2 доведена.
Лема 3. EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-012.gif"
Доказ. Безпосередньо випливає з леми 2 при а =1.
Число p2-1=(p-1)(p+1) на 8 ділиться без остачі, оскільки з двох послідовних парних чисел одне обов'язково ділиться на 4. Крім того, просте число р можна представити у вигляді p=8n+k, де k – одне з чисел 1, 3, 5, 7. Оскільки число
EMBED Equation.3
буде парним при k=1 і k=7, то 2 буде квадратним лишком за модулем р, якщо р виду 8n+1 чи 8n+7. Якщо ж р виду 8n+3 чи 8n+5, то 2 буде квадратним нелишком.
Теорема (Закон взаємності квадратних лишків). Якщо p і q - непарні прості числа, то
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-014.gif".
Іншими словами, якщо хоча б одне з чисел p чи q виду 4n+1, то р є квадратом за модулем q тоді і тільки тоді, коли q є квадратом за модулем р. Якщо ж обидва числа p і q виду 4n+3, то р є квадратом за модулем q тоді і тільки тоді, коли q не є квадратом за модулем р.
Доказ. Оскільки EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-012.gif", то формула з леми 2 набуває виду: EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-015.gif".
Розглянемо дві множини: S ={1,2,…,(p-1)/2}і K ={1,2,…,(q-1)/2}...
Утворимо (p-1)/2??(q-1)/2 штук пар чисел (qx,py), де х набуває значень з S, a y набуває значень з К. Перший і другий компонент однієї пари ніколи не збігаються, тому що з py=qx випливає, що py кратне q. Але це неможливо, бо (p,q)=1 і, оскільки 0<y<q, то (y,q)=1.
Нехай (p-1)/2?(q-1)/2=V1+V2, де V1 – число пар, у яких перший компонент менший за другий (qx<py), V2 – число пар, у яких другий компонент менший за перший (qx>py).
Очевидно, що V1 є числом пар, у яких x<(p/q)y. (Взагалі кажучи, x?(p-1)/2, але (p/q)y<p/2 бо y/q<1/2, отже [(p/q)y]?[p/2]=(p-1)/2, і нерівність x<(p/q)y не суперечить нерівності x?(p-1)/2.) Тому,
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-016.gif". Аналогічно, EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-017.gif".
Тоді з рівності на початку цього доказу: EMBED Equation.3, EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-018.gif".
Це означає, що EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-019.gif", що було потрібно.
Тригонометрична лема. Нехай m – непарне натуральне число. Тоді
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-020.gif".
Доказ одержується після безпосередньої перевірки. Наприклад, за формулою Муавра, переконуємося, що ліва частина є поліномом степеня (m-1)/2 від sin2 x, корені якого є sin2(2??j/m), де 1?j?(m-1)/2. Множник (-4)(m-1)/2 одержується після порівняння коефіцієнтів у лівій і правій частинах.
Доказ закону взаємності. Нехай р и q – два різних непарних простих числа. За лемою Гауса,
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-021.gif".
З рівності qs=?s rs (позначення леми 1 збережені), маємо: EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-022.gif".
(Синус - функція непарна, і знак можна винести вперед.)
Перемножуючи ці рівності і враховуючи, що відображення s ??rs бієктивне, одержуємо
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-023.gif".
Застосуємо тепер тригонометричну лему при m=q:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-024.gif".
де K={1,2,…(q-1)/2}... Замінюючи q і р, одержимо:
EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-025.gif"
Множники у формулах для (q/p) і (p/q) однакові з точністю до знака. Кількість протилежних знаків дорівнює EMBED Equation.3 INCLUDEPICTURE \d \z "../pict/23-026.gif", тому EMBED Equation.3INCLUDEPICTURE \d \z "../pict/23-027.gif".