Принцип Діріхле в задачах

Доводитимемо від супротивного.

Припустимо, що c > 1. Поділимо число на с. Матимемо

.

Якщо , то

₀ + у₀)=

Таким чином натуральне число  можна подати у вигляді

,

 де та у цілі числа. Проте це неможливо, оскільки < с, а за припущенням с - найменше натуральне число виду

.

Якщо 0, то

,

тобто ділиться на с. Згідно з припущенням, число також ділиться на с. Число с, с > 1 є спільним дільником чисел та , а це суперечить тому, що числа і взаємно прості. Отже, припустивши, що с > 1, дійшли до суперечності. Таким чином, с = 1. Теорему доведено.

У теорії подільності чисел  важливу роль відіграє таке твердження.

Теорема 4. Якщо число ділиться на кожне з двох взаємно простих чисел , то ділиться на добуток .

Доведення. Оскільки число ділиться на і на , то

,

де і - деякі натуральні числа. Числа взаємно прості, тому за теоремою 3 є цілі числа та такі, що

.

Помножимо цю рівність на . Дістанемо

.

Таким чином,

,

 а це означає, що ділиться на .

Зауваження. У цій теоремі  дуже істотно, що взаємно прості. Справді, число 24, наприклад, ділиться на 8 і на 12, але не ділиться на добуток 812 = 96 (числа 8 і 12 не є взаємно простими, отже, теорему 4 застосовувати не можна).

Теорема 5. Якщо добуток с ділиться на і числа взаємно прості, то число с ділиться на.

Доведення. Оскільки числа взаємно прості, то за теоремою 3 є цілі числа ₀ і у₀ такі, що .

Помножимо цю рівність на с. Дістанемо

.

 Добуток за умовою ділиться на , також ділиться на . Отже, с ділиться на .

Теорема 6. Якщо числа взаємно прості, то

існують такі натуральні числа і у, що

 

Доведнн я. Застосуємо принцип Діріхле. Нехай ()=1. Розглянемо всі числа виду , де послідовно набуває значень

1,2, ..., .

Якщо число при діленні на дає в остачі 1, то

,

Тобто

,

і теорема справджується.

Припустимо, що жодне з чисел при діленні на не дає в остачі 1. Можливими остачами тоді є числа: 2, 3, ..., .

Оскільки маємо  число, а всього можливо остачі, то існують натуральні числа такі, що числа і при діленні на , дають однакові остачі. Тому число

 

 ділиться на . Оскільки числа взаємно прості, то

 

ділиться на . Проте це неможливо, бо

 

Маємо суперечність. Отже, існує  таке , що при діленні на дає в остачі 1.

Теорема 7 (основна теорема арифметики). Кожне натуральне число, яке більше від 1, можна розкласти на прості множники. Будь-які два розклади того самого числа на прості множники можуть відрізнятися тільки порядком множників.

Доведення. Існування розкладу чисел на прості множники було доведено вище. Доведемо тепер єдність розкладу. Нехай число має два розклади на прості множники:

 

 

З першого розкладу випливає, що число ділиться на . Отже,

 

ділиться на . Доведемо, що одне з чисел

обов'язково дорівнює . Якщо, тo теорему доведено. Нехай . Оскільки і взаємно прості, і добуток

 

ділиться на , то за теоремою 5 число

 

 повинно ділитися на . Якщо то теорему доведено. Якщо , то повторюючи проведені вище міркування, впевнюємося, що ділиться на . Продовжуючи міркування далі, або знайдемо серед чисел

 

число, яке дорівнює , аюо дістанемо, що ділиться на . Тоді

,

оскільки - просте число. Одже серед чисел

є число, яке дорівнює

Нехай, наприклад, . Поділивши рівність

на матимемо

.

Візьмемо тепер просте число р₂. Повторюючи проведені вище міркування, дістаємо, що серед чисел

обов'язково є число, яке  дорівнює р₂. Аналогічно всі числа

 

зустрічаються серед чисел

,

 ніяких інших чисел  серед

 

бути не може, бо тоді б  добуток

 

був би більшим, ніж добуток

.

Отже, обидва розклади числа  на прості множники можуть відрізнятися тільки порядком множників. Теорему доведено.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

РОЗДІЛ ІІІ. ГЕОМЕТРИЧНІ АНАЛОГИ ПРИНЦИПУ ДІРІХЛЕ

 

У цьому розділі розглянуто деякі твердження, що є геометричними аналогами принципу Діріхле. Сформульований принцип Діріхле для площ

також має важливі застосування в багатьох розділах сучасної математики. Я розглядатиму лише множини на площині.

 

§ 3.1. Множина на площині

 

§3.1.1. Операції над множинами

 

Нагадаю деякі основні означення з теорії множин. Позначають множини великими латинськими буквами.

Запис (читається «А належить В» або «А є підмножиною множини В») означає, що кожен елемент множини А є також елементом множини В.

 

 

 

Рис. 2               Рис. 3

 

 

Нехай є дві множини А і В. Об'єднанням множин АВ Називається множина всіх тих елементів, які належать принаймні одній з множин А і В (рис. 9).

Перерізом А В множин А і В називається множина всіх тих елементів, які належать кожній з множин А і В рис. 10).

Різницею А\В множин А і В називається множина тих елементів А, які не належать В.

Множину , яка не містить  жодного елемента, називають порожньою  і позначають символом . Зокрема, запис означає, що множини А і В не мають спільних елементів.

 

§3.1.2. Множини на площині

 

Надалі розглядатиму лише множини точок площини, причому замість терміна «множина» часто вживатиму термін «фігура».

Розглянемо в площині  прямокутну декартову систему координат. Положення кожної точки площини  однозначно визначається її декартовими координатами і у. Нехай кожній точці (, у) з множини D поставлено у відповідність певне дійсне число . Тоді кажуть, що на множині D визначено функцію двох змінних і у.

Кожному співвідношенню між і у, яке задано у вигляді рівності або нерівності, або системи нерівностей на площині відповідає множина тих точок (х, у), для яких виконується задане співвідношення. Цю множину називають геометричним образом заданого співвідношення.

 

§3.1.3. Внутрішні точки множини на площині

 

Нехай А - деяка множина точок (х₀, у₀) на площині (А - фігура на площині). Точку (х₀, у₀) називають внутрішньою точкою множини А, якщо існує такий круг (можливо досить малого радіуса), з центром у точці (х₀, у₀),всі точки якого належать множині А.

 

§3.1.4.Обмежені та опуклі множини

 

Множина А точок площини  називається обмеженою, якщо існує  круг, який повністю покриває множину  А.

Множина А точок площини називається опуклою, якщо разом з будь-якими двома своїми точками вона містить відрізок, який сполучає ці точки. Круг, трикутник, півплощина — опуклі множини.

 

§3.1.5.Площа фігури

 

Поняття про площі деяких фігур таких, як прямокутник, трикутник, многокутник, відоме із шкільного курсу математики. Покажемо, як можна ввести поняття площі для більш широкого класу фігур.

Називатимемо фігуру простою, якщо її можна розбити на скінченне число трикутників. Площа такої фігури є сумою площ відповідних трикутників. Площу простої фігури А позначають через S(А). Клас усіх простих фігур позначають буквою . Легко впевнитися, що виконуються такі властивості:

1) якщо проста фігура А має внутрішні точки, то S(А)> 0.

2) якщо фігура А (А ) складена з простих фігур і , які не мають спільних внутрішніх точок, то

;

3) рівні фігури, тобто фігури, які можна накласти oдна на одну, мають однакові площі,

4) для квадрата  із стороною 1 S (∆) = 1. Можна довести також, що на множині * простих фігур існує тільки одна функція множини S(A), яка задовольняє властивості 1 - 4.

Означення. Вважають, що фігура має певну площу (є квадрованою), якщо для будь-якого існують прості фігури і такі, що

Клас усіх квадрованих  фігур позначимо через K. Очевидно, кожна проста фігура є квадрованою.

Можна довести, що на класі квадрованих фігур існує  тільки одна функція S(А), яка має властивості 1 - 4 і така, що для простої фігури А ця функція дорівнює площі фігури, А. Число S(А) називається площею квадрованої фігури А.

Не кожна фігура на площині є квадрованою, тобто  має площу. У шкільному курсі  математики розглядаються в основному  фігури, обмежені відрізками прямих і  дугами кіл. Такі фігури є квадрованими.

Питання, пов'язані  із строгими oзначеннями поняття площі, об'єму, належать до розділу математики, який називається теорією міри.

 

§ 3.2. Принцип Діріхле для площ і його застосування

 

§3.2.1. Принцип Діріхле для площ

 

Доведемо геометричне  твердження, яке дуже нагадує «  принцип ящиків» Діріхле, називатиму його принципом Діріхле для площ. Як і «принцип ящиків», принцип Діріхле  для площ є очевидним твердженням. Проте за його допомогою здобуто  глибокі результати в так званій геометричній теорії чисел.

Теорема 1 (принцип  Діріхле для площ). Нехай А –  кадрована фігура, – кадровані фігури, причому

 

Відомо, що

 

Тоді принаймі дві з фігур  мають спільні внутрішні точки.

Доведення. Припустимо супротивне. Нехай будь-які дві  з фігур  не мають спільних внутрішніх точок. Тоді

 

(2)

Внаслідок властивості  адитивності площ. Проте 

і тому

⊂А.

Отже,

 

Порівнюючи (1), (2) і (3), дійдемо до суперечливої нерівності

.

Одже, наше припущення неправильне.

 

§3.2.2. Узагальнений принцип Діріхле для площ

 

Теорема 2 (узагальнений принцип Діріхле для площ). Нехай

А,

- квадровані фігури, причому

.

 Припустимо, що

 

Тоді принаймні k + 1 фігура з фігур

 

спільну внутрішню  точку.

Доведення. Припустимо, що переріз будь-яких

k + 1  множини з множин

А,

не містить  внутрішніх точок. Тоді

 

оскільки площа  кожної відкритої множини, яка належить

,

 враховується  в сумі, що стоїть у лівій  частині нерівності (5), не більше  як раз. Маємо суперечність з нерівністю (4). Таким чином, переріз деяких + 1 множини з множин

 

містить внутрішні точки.

 

§3.2.3.Теорема Бліхфельдта

 

Візьмемо прямокутну декартову систему координат  на площині і через кожну точку  цілими координатами проведемо прямі, паралельні координатним осям. Утворена система прямих називається цілочисловою решіткою, точки з цілими координатами — вузлами цілочислової решітки. Цілочислова решітка розбиває всю площину на систему квадратів із стороною 1. Моделлю цілочислової решітки може бути звичайний папір у клітинку.

Розглянемо цілочислову решітку і деяку квадровану фігуру А. Кількість вузлів решітки, покритих фігурою А, залежить від її положення. Існують фігури як завгодно, великої і навіть нескінченної площі, які не покривають жодного вузла решітки (рис.4).

 

 

 

 

Рис. 4

Теорема 3 (Бліхфельдта). Нехай А - квадрована фігура, причому

S (A).

Фігуру А можна  перенести паралельно таким чином, що вона покриє принаймні вузол решітки.

Доведення. Прямі цілочислової решітки розбивають фігуру А на частини

,

які лежать у  різних одиничних квадрантах решітки

,

 де оскільки

 

(на рис. 12 . Виберемо один з цих квадратів, наприклад. Кожен з решти квадратів

 

перенесемо паралельно так, щоб він сумістився з Очевидно, паралельний перенос здійснюється на вектори, компоненти яких є цілими числами (такі вектори називатимемо цілочисловими).

        Частини

 

фігури А перейдуть при цьому в конгруентні їм частини

 

(для симетрії позначень покладy, що ). Оскільки за умовою теореми S (A) , то

.

Зазначимо також, що

 .

Тому згідно з  узагальненим принципом Діріхле  для площ, всередині існує точка а, яка належить принайні n+1 фігурі з фігур .

Кожна з цих  частин утворилася в результаті паралельного перенесення на цілочисловий вектор відповідної частини . При цьому деяка внутрішня точка фігури A переходить у точку а. Вектор є цілочисловим. Таким чином, існує n + 1 точка , які є внутрішніми для фігури А і такі, що всі вектори є цілочисловими.

Нехай b - найближча до а вершина квадрата Довжина вектора менша від 1. Якщо всю площину перенести паралельно на вектор , то кожна з n+1 точки перейде в точку , таку, що . Отже, вектори є цілочисловими векторами. Оскільки b є вузол решітки, то й усі точки також є вузлами решітки. Тоді фігура, яка утворюється з фігури А паралельним перенесенням на вектор (довжина якого менша від 1) міститиме принаймні n+ 1 вузол решітки.

Для n-1 теорему 3 можна сформулювати інакше. При цьому з міркувань, наведених при доведенні теореми 3, випливає, що існують точки які належать А, і точка а(х₀, у₀) такі, що векторі є цілочисловими векторами (це означає, що числа

 

є цілими). Тоді

є також цілими числами. Отже, справджується таке твердження.

Теорема 4. Нехай А - квадрована фігура, при чому

.

 Тоді в А є дві різні внутрішні точки такі, що числа

 

є цілими.

Цю теорему також називають теоремою Бліхфельта.

 

§3.2.4.Теорема Мінковського

 

Розглянемо теорему, яка  належить німецькому математику Герману Мінковському і яка відіграє важливу роль у геометричній теорії чисел.

Теорема 5 (Мінковського). Нехай А - симетрична відносно початку координат, обмежена, опукла множина точок площини і така, що

.

Тоді А містить відмінну від початку координат точку з цілими координатами.

Доведення. Застосуємо до А перетворення гомотетії з центром у початку координат і коефіцієнтом . Дістанемо фігуру подібну до А, причому