нні аргументу приймає значення, що представляє собою складене число.
Доказ Нехай f (x) = a 0 x n + a 1 x n - 1 +. . . + A n , де всі a i - цілі числа. Припустимо, що при деякому k значення многочлена f (x) - просте число, тобто f (k) = p, де p - просте. Багаточлен ступеня n приймає одне і те ж значення не більше ніж в n точках. (Дійсно, якщо f (x) = y 0 більше ніж в n точках x 1 , x 2 ,. . ., X n + 1 , то многочлен g (x) = f (x)-y 0 має коріння x 1 , x 2 ,. . ., X n + 1 , а, як відомо, будь многочлен не може мати більше n дійсних коренів.) Покажемо, що знайдеться таке ціле t, що f (k + pt) відмінно від 0 і p. Нам допоможе принцип Дирихле. Будемо вважати значення багаточлена (в натуральних точках) "Клітинами", а натуральні числа виду k + pt "зайцями". Натуральне число N = k + pt будемо розміщати в "клітку", відповідну значенню многочлена f (N). Згідно висловлену вище твердженням, в "Клітці" не може поместітьс більше n "зайців". Так як "Зайців" багато, то це означає, що f (k + pt) не може приймати тільки значення 0 і p при різних цілих t, тобто знайдеться "заєць" k + pt, який не потрапить ні в "клітку" 0, ні в "клітку" p. Отже, при деякому t маємо: f (k + pt) № 0 і f (k + pt) № p. Розкладаючи f (k + pt) за ступенями pt (використовуючи біном Ньютона), отримаємо
f (k + pt) = f (k) + c 1 pt + c 2 (pt) 2 +. . . + C n (pt) n ,
де всі c i - деякі цілі числа. Оскільки f (k) = p, з попереднього рівності отримуємо, що f (k + pt) ділиться на p, причому f (k + pt) № 0 і f (k + pt) № p, так що f (k + pt) - складене число. Теорема доведена.
В доказі цієї теореми була застосована кілька модифікована форма принципу Діріхле. Далі ми розповімо про інші його різновидах, найбільш широко використовуваних в рішеннях аналітичних та геометричних задач.
Наступна теорема, сформульована П. Ферма, є одним з найбільш фундаментальних фактів в теорії подільності цілих чисел і знаходить широке застосування як в теоретичних дослідженнях, так і в арифметичних додатках.
МАЛА ТЕОРЕМА ФЕРМА. Якщо p - просте число, a - ціле число, не ділиться, на p, то a p - 1 при діленні на p дає залишок 1, тобто
a p - 1 є 1 (mod p).
Доказ Кожне з p - 1 чисел a, 2a,. . ., (P-1) a ("зайців") дає при діленні на p ненульовий залишок (адже a не ділиться на p):
a = k 1 p + r 1 ,
2a = k 2 p + r 2 ,
. . . . . . . . . . . . . . .
(p - 1) a = k p - 1 p + r p - 1 .
Якщо число різних зустрічаються тут залишків ("клітин") менше p - 1, то серед них знайдуться принаймні два однакових ("в клітці по крайней мірі два зайці "). Але це неможливо, так як при r n = r m число (nm) a = (k n -k m ) p ділиться на p, що суперечливо, бо | nm |
1 ,. . . , R p - 1 між собою різні і утворюють перестановку чисел 1, 2, . . . , P - 1. Перемножая всі попередні рівності, отримуємо
(p-1)! a p - 1 = N В· p + r 1 r 2 В·. . . В· R p - 1 = Np + (p-1)!,
де N - деяке ціле число. Отже, (p-1)! В· (A p-1 -1) ділиться на p, а тоді і a p - 1 - 1 ділиться на p. Теорема доведена.
Слідство. Якщо p - просте число, то при будь-якому цілому a різниця a p - a ділиться на p.
Крім малої теореми Ферма застосування принципу Діріхле до залишків при діленні зустрічається в багатьох інших завданнях елементарної теорії чисел. Можлива наступна переформулировка принципу Діріхле:
"Серед p + 1 цілих чисел знайдуться два числа, що дають при діленні на p один і той же залишок ".
При розподіл із залишком на p може зустрітися кінцеве число різних залишків: 0, 1, 2,. . . , P-1. Вони то і грають тут роль "клітин", а самі цілі числа є "зайцями". Так як чисел ("зайців") більше, ніж залишків ("клітин"), то хоча б два числа "сидять в одному клітці ", тобто мають однакові залишки при діленні на p. Розглянемо класичні приклади.
Приклад 10.
Рішення
Приклад 11. . .
Рішення
. . . . . . . . . . . . . . . . . . .
.
Якщо Припустимо, . . ділиться на 100.
.
.
Приклад 12.
Рішення
Розглянемо . . . . .
. . . . . ., N.
Доказ Нехай теорема . . . . . . . Суперечність.
Таким . . . Теорема доведена.
Стосовно
"Якщо
Для
"Якщо
"Якщо
В
"Якщо
"Якщо
В
Приклад 13.
Рішення . . . . . тому
. .
Таким
Приклад 14.чином поміщені кілька кіл, сума радіусів яких дорівнює 25. Довести, що знайдеться пряма, що перетинає НЕ менше дев'яти з цих кіл.
Рішення Спроектуємо всі кола на довільний діаметр AB великого кола (AB = 6). Сума довжин проекцій, очевидно, дорівнює сумі діаметрів кіл, тобто 50. Оскільки 50> 8AB, то на відрізку AB є точка, що належить проекціям по крайней мірою дев'яти кіл. Пряма, що проходить через цю точку і перпендикулярна діаметру AB, - шукана.
Приклад 15. Дана фігура площі більше N. Довести, що в ній знайдуться N +1 точок, різниці відповідних координат яких - цілі числа.
Рішення Розіб'ємо вихідну фігуру паралельним...
