Принцип Дирихле в теории чисел

Следующую теорему часто используют в школьном курсе алгебры, но доказательство не рассматривают. Его очень просто получить с помощью принципа Дирихле.

ТЕОРЕМА 1. Пусть p, q - натуральные числа, p < q. Если обыкновенную дробь p/q обратить в десятичную, то получится либо конечная, либо бесконечная периодическая десятичная дробь, причём длина периода не превосходит q-1.

Доказательство Будем делить p на q "уголком" и следить за остатками. Если на каком-то шаге остаток будет нулевым, то получится конечная дробь. Если же все остатки будут отличны от нуля, то рациональное число p/q запишется в виде бесконечной десятичной дроби. Докажем, что она будет периодической. Каждый раз при нахождении очередной цифры частного будет получаться в остатке одно из чисел 1, 2,..., q-1. Эти возможные значения остатков мы и будем считать "клетками", так что всего имеется q-1 "клеток". "Зайцами" же будут остатки, которые получаются в действительности при выполнении деления (См. рисунок). Рассмотрим первых q "зайцев". Так как их на 1 больше, чем число "клеток", то какие-то два "зайца" попадут в одну "клетку". Другими словами, не позже, чем через q - 1 шагов начнут повторяться остатки, а вслед за этим - и цифры в частном. Действительно, если на некотором шаге повторился остаток, то, приписав как обычно к нему 0, мы получим то же число, что было прежде, а, значит, снесём в частное ту же самую цифру, что и раньше; поэтому наши действия начнут повторяться. Таким образом, получится периодическая десятичная дробь с периодом длиной не более q - 1.

С давних пор математиков интересовал вопрос о существовании функций f(k), значениями которых при всех натуральных k являлись бы только простые числа. Известны функции, которые принимают подряд много простых значений. Например, Эйлер указал интересный многочлен x2 - x + 41, который при всех целых x от -39 до 40 включительно принимает только простые значения (т.е. при x = 0, ±1, ±2,..., ±39, 40). Однако при x = 41 и x = 42 значения этого многочлена будут уже составными числами. В общем случае многочлен с целыми коэффициентами не может при всех натуральных значениях аргумента принимать только простые значения.

ТЕОРЕМА 2. Любой многочлен с целыми коэффициентами (отличный от константы) при некотором натуральном значении аргумента принимает значение, представляющее собой составное число.

Доказательство Пусть f(x) = a0xn + a1xn - 1 +... +an, где все ai - целые числа. Предположим, что при некотором k значение многочлена f(x) - простое число, т.е. f(k) = p, где p - простое. Многочлен степени n принимает одно и то же значение не более чем в n точках. (Действительно, если f(x) = y0 более чем в n точках x1, x2,..., xn + 1, то многочлен g(x) = f(x)-y0 имеет корни x1, x2,..., xn + 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) + c1pt + c2(pt)2 +... + cn(pt)n,    

где все ci - некоторые целые числа. Поскольку f(k) = p, из предыдущего равенства получаем, что f(k + pt) делится на p, причём f(k + pt) № 0 и f(k + pt) № p, так что f(k + pt) - составное число. Теорема доказана.

В доказательстве этой теоремы была применена несколько модифицированная форма принципа Дирихле. Далее мы расскажем о других его разновидностях, наиболее широко используемых в решениях аналитических и геометрических задач.

Следующая теорема, сформулированная П. Ферма, является одним из самых фундаментальных фактов в теории делимости целых чисел и находит широкое применение как в теоретических исследованиях, так и в арифметических приложениях.

МАЛАЯ ТЕОРЕМА ФЕРМА. Если p - простое число, a - целое число, не делящееся на p, то ap - 1 при делении на p даёт остаток 1, т. е.

ap - 1 є 1 (mod p).    

Доказательство Каждое из p - 1 чисел a, 2a,..., (p-1)a ("зайцев") даёт при делении на p ненулевой остаток (ведь a не делится на p):

a = k1p + r1,
2a = k2p + r2,
...............
(p - 1)a = kp - 1p + rp - 1.

Если число различных встречающихся здесь остатков ("клеток") меньше p - 1, то среди них найдутся по крайней мере два одинаковых ("в клетке по крайней мере два зайца"). Но это невозможно, так как при rn = rm число (n-m)a = (kn-km)p делится на p, что противоречиво, ибо |n-m| < p и a взаимно просто с p. Значит, все остатки r1,..., rp - 1 между собой различны и образуют перестановку чисел 1, 2,..., p - 1. Перемножая все предыдущие равенства, получаем

(p-1)! ap - 1 = N·p+ r1r2·...·rp - 1 = Np + (p-1)!,    

где N - некоторое целое число. Следовательно, (p-1)!·(ap-1-1) делится на p, а тогда и ap - 1 - 1 делится на p. Теорема доказана.

Следствие. Если p - простое число, то при любом целом a разность ap - a делится на p.

Помимо малой теоремы Ферма применение принципа Дирихле к остаткам при делении встречается во многих других задачах элементарной теории чисел. Возможна следующая переформулировка принципа Дирихле:

"Среди p + 1 целых чисел найдутся два числа, дающие при делении на p один и тот же остаток".

При делении с остатком на p может встретиться конечное число различных остатков: 0, 1, 2,..., p-1. Они то и играют здесь роль "клеток", а сами целые числа являются "зайцами". Так как чисел ("зайцев") больше, чем остатков ("клеток"), то хотя бы два числа "сидят в одной клетке", т.е. имеют одинаковые остатки при делении на p. Рассмотрим классические примеры.

Пример 10. Дано 11 различных целых чисел. Доказать, что из них можно выбрать два числа, разность которых делится на 10.

Решение По крайней мере два числа из 11 дают одинаковый остаток при делении на 10 (принцип Дирихле). Пусть это будут A = 10a + r и B = 10b + r. Тогда их разность делится на 10: A - B = 10(a - b).

Пример 11. Доказать, что если имеется 100 целых чисел x1, x2,..., x100, то из них можно выбрать несколько чисел (может быть, одно), сумма которых делится на 100.

Решение Рассмотрим 100 следующих сумм:

S1 = x1,
S2 = x1 + x-2,
S3 = x1 + x2 + x3,
....................
S100=x1+x2+ x3+...+ x100.

Если хотя бы одна из этих сумм делится на 100, то наша цель достигнута. Допустим, что ни одно из чисел S1, S2,..., S100 не делится на 100. Значит, два из них при делении на 100 дают равные остатки (т. к. сумм у нас 100, а различных остатков может быть лишь 99). Пусть это Sn и Sm (n < m). Тогда разность

Sm-Sn= (x1 +...+ xm) - (x1 +...+ xn) = xn + 1+...+ xm    

делится на 100, и поэтому сумма xn + 1+...+ xm является искомой.

Пример 12. Первоклассник Петя знает только цифру 1. Доказать, что он может написать число, делящееся на 1997.

Решение

Рассмотрим последовательность a1 = 1, a2 = 11,..., an = = 11...1,... чисел, десятичная запись которых состоит из одних единиц. Поскольку существует лишь конечное число остатков от деления на 1997, а последовательность содержит бесконечно много членов, то, согласно принципу Дирихле, среди них найдутся два, дающих одинаковые остатки: ak и al (k > l). Их разность ak - al = 10l·ak - lделится на 1997. Так как 10l и 1997 - взаимно просты, то ak - l делится на 1997. Это число Петя сможет записать.

КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ. Если числа a1, a2,..., an попарно взаимно просты, то для любых остатков r1, r2,..., rnтаких, что 0 Ј ri < ai при всех i = 1, 2,..., n, найдётся число N, которое при делении на ai даёт остаток ri при всех i = 1, 2,..., n.

Доказательство Применим индукцию по n. При n = 1 утверждение теоремы очевидно. Пусть теорема справедлива при n = k - 1, т.е. существует число M, дающее остаток ri при делении на ai при i = 1, 2,..., k - 1. Обозначим d = a1a2... ak - 1 и рассмотрим числа M, M + d, M + 2d,..., M + (ak - 1)d. Покажем, что хотя бы одно из этих чисел даёт остаток rk при делении на ak. Допустим это не так. Поскольку количество чисел равно ak, а возможных остатков при делении этих чисел на ak может быть не более чем ak - 1 (ведь ни одно число не даёт остаток rk), то среди них найдутся два числа, имеющих равные остатки (принцип Дирихле). Пусть это числа M + sd и M + td (0 Ј s Ј ak - 1 и 0 Ј t Ј ak - 1). Тогда их разность (M + sd) - (M + td) = (s - t)d делится на ak, что невозможно, т.к. 0 < |s - t| < ak и d = a1a2...ak - 1 взаимно просто с ak, ибо числа a1, a2,..., ak попарно взаимно просты (по условию). Противоречие.

Таким образом, среди рассматриваемых чисел найдётся число N, которое при делении на ak даёт остаток rk. В то же время при делении на a1, a2,..., ak-1 число N даёт остатки r1, r2,..., rk-1 соответственно. Теорема доказана.

Дата добавления: 2015-05-10