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

ВСТУП

Під принципом Діріхле в математиці розуміють твердження, яке полягає в тому, що якщо деякі предмети розкладено в ящики, причому кількість предметів є більшою за кількість ящиків, то хоча б в одному ящику буде принаймі два предмети ( якщо ж кількість предметів є меншою за кількість ящиків, то хоча б один з ящиків буде порожнім). Подібні міркування неодноразово використовував німецький математик Петер Густав Лежен Діріхле (1805 – 1859) при вивченні наближення ірраціональних чисел раціональними. Принцип Діріхле досить ефективно використовується при розв'язуванні різних задач з теорії множин, комбінаторики, теорії графів, комбінаторної геометрії,  тощо.

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

В даній дипломній роботі систематично і послідовно викладено Принцип  Діріхле і його додаток до різних задач теорії чисел, розглядаються  різноманітні застосування принципу Діріхле та його модифікацій до розв'язування задач, доводяться класичні теореми Діріхле, Кронекера. Задачі згруповані за спільною тематикою та спорідненими методами їхнього розв'язування. Наведені типові методи і прийоми розв'язування задач.

 

 

 

 

РОЗДІЛ І. ПРИНЦИП ДІРІХЛЕ

§ 1.1. Принцип Діріхле

 

Якщо + 1 предмет розкладено в ящиків, то знайдеться два предмети, які лежать в одному ящику.

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

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

 

§ 1.2. Більш загальні формулювання принципу Діріхле

 

Якщо предмет розкладено в ящиків, то принаймні в одному з ящиків знаходиться не менше як предмет.

Для доведення пронумеруємо ящики  числами 1, 2,...,. Нехай х_і — число предметів, які знаходяться в ящику з номером і. За умовою

 

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

 

Тоді 

 

Дістали суперечливу  нерівність

 

Отже, наше припущення неправильне, тобто принаймні одне таке, що . Доведене твердження можна сформулювати так: якщо заєць розміщено в п клітках, то принаймні в одній з кліток знаходиться не менш як  заєць.

 

§ 1.3. Відображення множин і принцип Діріхле

 

Поняття множини  відіграє важливу роль в усіх розділах сучасної математики. Я також використовуватиму деякі поняття теорії множин, проте означення поняття множини не даватиму. Зазначу те, що множини можуть бути різного характеру. Можна говорити, наприклад, про множину учнів певної школи, про множину читачів книги, про множину натуральних чисел, які діляться без остачі на 3, про множину коренів даного рівняння і т. д. Позначають множини великими латинськими буквами. Запис А означає, що елемент а належить множині А. Іноді записують множину, перераховуючи в фігурних дужках усі її елементи. Наприклад,

 

• множина коренів рівняння

 

      Нехай є дві скінченні множини

 . Припустимо, що кожному елементу з множини А поставлено у відповідність деякий елемент множини В. Тоді кажуть, що задано відображення множини А у множину B, елемент називають образом елемента .

      Якщо А - множина зайців, а В - множина кліток, в яких треба розмістити зайців, то, визначивши клітку для кожного зайця, дістанемо відображення множини А у множину В .

       У термінах теорії множин принцип Діріхле можна сформулювати так. Нехай m> . Тоді при будь-якому відображенні множини А у множину В знайдуться два елементи множини А, які мають один і той же образ. Інакше кажучи, якщо m зайців розміщувати в клітках ( < m), то знайдуться два зайці, які потрапляють в ту саму клітку.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

РОЗДІЛ ІІ. ПОДІЛЬНІСТЬ ЧИСЕЛ І ПРИНЦИП ДІРІХЛЕ

 

§ 2.1. Натуральні та цілі числа

 

Числа 1, 2, 3, 4, 5 ... називаються натуральними. Найменшим  натуральним числом є одиниця, найбільшого  натурального числа не існує, бо яке  б натуральне число ми не взяли, можна вказати ще більше натуральне число.

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

При додаванні  і множенні натуральних чисел  дістаємо теж натуральне число. Коротко цю властивість формулюють так: множина всіх натуральних чисел замкнена відносно операцій додавання і множення. Множина натуральних чисел не е замкненою відносно операції віднімання.

Як відомо, операція віднімання від числа п числа т полягає в знаходженні числа х(його позначають п - т) такого, що т + х = . Якщо = 7, т= 3, то х = 4. Якщо, наприклад, п= 8, т= 11, то операцію 8-11 обмежуючись тільки натуральними числами, виконати не можна. Для того щоб операцію віднімання можна було виконати, розглядають більш широку множину, ніж множина натуральних чисел - множину цілих чисел.

Множина цілих  чисел складається з натуральних  чисел 1, 2, 3, ..., числа 0 і від'ємних чисел -1, -2, -3, ...

Множину цілих  чисел часто позначають буквою Z. Ця множина замкнена відносно операцій додавання і множення, вона замкнена також і відносно операції віднімання. Рівняння т + х = п у множині цілих чисел завжди має єдиний розв'язок х = п - т.

Проте Множина Z не є замкненою відносно операції ділення. Ділення (дія, обернена до множення) виконується у множині Z не завжди. Нагадаю, що результатом ділення (часткою) числа а на число b називається таке число х (його позначають а : b), що ах =b.

 

§ 2.2. Подільність цілих чисел.

 

Вважають, що ціле число а ділиться на ціле число b, якщо існує ціле число k, таке, що а =. Число b називають дільником числа а.

Теорема. Якщо числа а і b діляться на с, то числа а + b,а - b діляться на с. Якщо число а ділиться на с, число b ділиться на d, то ділиться на .

Доведення. Якщо і b діляться на с, то а = k,

де k і цілі числа. Тому

.

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

Якщо  ділиться на с, а b ділиться на d, то ,

де і - деякі цілі числа. Тоді

.

Таким чином, ділиться на .

Наслідок. Якщо а ділиться на число с, то при будь-якому натуральному п число а^п ділиться

на с^п.   

§ 2.3. Ділення з остачею

 

Нанесемо на числову  вісь точки, які відповідають цілим  числам (рис. 3). У подальшому з метою  скорочення

 

 

 

 

                       в          а

      

       0   1   2   3   4   5   6    7   8   9

 

 

Рис. 3

 

замість слів «точки, які відповідають числам» говорить просто «числа». Позначимо на числовій осі також усі цілі числа, які  діляться на b. (Вони розміщені на однаковій відстані одне від одного). Ці числа називаються ще числами, кратними числу b.

Нехай тепер а - число, яке не ділиться на b.

На числовій осі воно міститиметься між якимись двома числами, кратними b. Нехай це числа і .

Тоді

,

де .

Отже, справджується  таке твердження.

Теорема 1. Для цілого числа а і натурального числа b можна знайти такі цілі числа і , де 0 < < b, що

 

Числа і за даними а і b визначаються однозначно, число називається часткою від ділення а на b, а число - остачею від ділення а на b.

Доведемо єдиність чисел і . Припустимо, що число а можна подати двома способами:

 

 

Віднімаючи ці рівності, матимемо

.

Звідси

   (2)

Отже,  ділиться на b. Нехай , зокрема . Тоді

> 0 і 0 < < b.

 Отже, є натуральним числом, меншим від b, і тому воно не ділиться на b. У зв'язку з цим виникає суперечність. Тому виконується рівність . З рівності (2) випливає, що

.

 Оскільки , то . Отже,

.

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

  або , або ,..., або у вигляді

.

Числа, які діляться на 2 без остачі, називаються парними, числа, які не діляться на 2, називаються непарними.

Зауваження. Число а, про яке йшлося в теоремі, може бути від'ємним. Знайдемо, наприклад, остачу від ділення а на b, де а = -38,

b = 7. Маємо - 38 = (-6)7 + 4. Отже, дорівнює 4.

 

§ 2.4. Прості числа

 

§ 2.4.1.Дільники числа

Розглянемо деяке  натуральне число а і випишемо всі його дільники. Нехай, наприклад а = 24. Тоді множина D усіх його дільників складається з 8 чисел:

D = {1, 2, 3, 4, 6, 8, 12, 24}.

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

,

де b — деяке натуральне число. Таким чином, число k є дільником. Такі два дільники числа , добуток яких дорівнює , називатимемо доповняльними. Поставивши у відповідність кожному дільнику числа а його доповняльний дільник, матимемо взаємно однозначне відображення множини й на себе. Наприклад, для числа а =24 це відображення можна подати у вигляді табл. 1 (додаток 1).

Кожне натуральне число , яке більше за 1, має принаймні два дільники: 1 і а.

Означення. Натуральне число а (а >1) називається простим, якщо воно не має інших дільників, крім 1 і а. Число а називається складеним, якщо крім 1 і а,воно має ще й інші дільники.

Серед перших 100 чисел простими є: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Інші числа  першої сотні, крім 1, є складеними; число 1 має тільки один натуральний дільник, воно не є ні простим, ні складеним.

Теорема 1. (теорема Евкліда). Існує нескінченно багато простих чисел.

Доведення. Доводитимемо від супротивного. Нехай існує скінченне число простих чисел. Тоді всі ці числа можна перелічити:

2, 3, 5, 7, 11, ..., ,

де - найбільше просте число (за припущенням таке число є). Перемножимо всі ці числа і до здобутого числа додамо 1. Матимемо

N =

З'ясуємо, яким є  число N - простим чи складеним? Якщо N просте, то маємо суперечність, оскільки за припущенням найбільше просте число, а N > . Якщо складене число, то воно має деякий простий дільник t,

1 < t < N. Очевидно,  t не може збігатися з жодним з простих чисел

2, 3, 5, ... ,

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

 

§ 2.4.2 Розклад натурального числа на добуток простих чисел

 

Кожне натуральне число можна розкласти  на добуток простих чисел.

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

Враховуючи кратність простих  множників, розклад числа можна  подати у вигляді

,

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

У подальшому покажемо, що кожне натуральне число можна разкласти на прості множники тільки єдиним способом.

 

 

 

§ 2.4.3. Число різних дільників числа

Розглянемо натуральне число

 

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

При підрахунку числа дільників  числа 

 

міркуємо так. Кожний дільник числа  має вигляд

,

де  .

Число різних наборів () дорівнює

(.

Отже, справджується таке твердження.

Теорема 2. Нехай  - число дільників числа  
.

Тоді

(

 

§ 2.4.4. Найбільший спільний дільник. Взаємно прості числа

 

Кожне ціле число, яке дорівнює нулю, має скінченне число дільників. Очевидно, якщо d - дільник числа , то й - d й є також дільником числа . Тому надалі йтиметься тільки про натуральні дільники числа

Означення. Нехай і b — два цілих числа, які не дорівнюють одночасно нулю. Розглянемо всі спільні дільники чисел і b. Найбільший з них називають найбільшим спільним дільником чисел і b і позначають символом (,b).

Означення. Числа і b називають взаємно простими, якщо

(b) = 1.

Взаємно прості числа не мають інших спільних дільників крім 1.

Теорема 3. Якщо числа і b взаємно прості, то існують такі цілі числа ₀ і у₀, що

₀ + bу₀= 1.

Доведення. Зазначимо, що числа і b не можуть одночасно дорівнювати нулю, оскільки в противному разі кожне з них ділилося б на будь-яке натуральне число, тобто   і b не були б взаємно простими. Розглянемо всі можливі цілі числа, які можна подати у вигляді

,

де х і у — деякі цілі числа. Серед таких чисел будуть числа

.

Серед чисел х + будуть і натуральні числа. Наприклад, якщо від'ємне, то

 

натуральне число.

Розглянемо найменше натуральне число, яке можна подати у вигляді

х +у.

 Позначимо його с = х₀ +у₀. Доведемо, що с = 1. Тим самим буде встановлено існування ₀ та у₀, для яких виконується рівність

₀ + у₀ = 1.