Таблицы Брадиса

В частности, 1 ...

В частности, 1 ...

Элементы математики в задачах - Г. А. Мерзон

Задача 15. Пусть p — простое число. Докажите, что:

а) Скр\р при 0<к<р;

-ф-                                    б) (а + ЪУ = ар + Ър (mod р);                                                                    -ф-

в) (малая теорема Ферма) ap — a .p.

k p!

Решение, a) Вспомним, что С = ----- гтттт- Но при 0 < к < р число р

p (p — k)! k!

делит числитель, но не знаменатель (так как при n < p число n! есть произведение чисел меньших p, а значит, на p не делящихся).

б) По биному Ньютона (a + b)p = ^k Ckakbp—k. Остается только за­метить, что (по предыдущему пункту) все слагаемые, кроме первого и последнего, в этой сумме сравнимы с 0 по модулю p.

в) Из предыдущего пункта видно, что по модулю p возведение в степень аддитивно (то есть переводит сумму в сумму). В частности, ap = (1 + ... + 1)p = 1p + ... + 1p = a (mod p), что и требовалось дока­зать.

Решение 2. Пусть мы хотим покрасить колесо обозрения, состоящее из p одинаковых кабинок, в не более чем a различных цветов. Под­считаем, сколькими различными способами это можно сделать.

Сначала разберемся, какие способы являются различными. Так как колесо обозрения крутится, то способы, получающиеся друг из друга поворотом, естественно считать одинаковыми. Будем также

190                             Целые числа 3. Сравнения

считать, что с разных сторон колесо обозрение разное, то есть спо­собы, получающиеся друг из друга симметрией относительно верти­кальной плоскости, считаются разными.

Каждую из p кабинок можно покрасить в a цветов, так что, на первый взгляд, число способов равно ap. Но некоторые способы мы считали несколько раз. Хочется сказать, что каждый способ мы под­считали p раз (число различных положений колеса обозрения при поворотах), то есть число ap надо разделить на p. Но это неправильно: например, если мы покрасим все кабинки в один цвет, то при пово­ротах эта раскраска переходит в себя (кроме того, ap далеко не всегда делится на p). Есть ли еще способы, которые при некотором повороте переходят в себя? Так как p — простое число[18], в себя при некотором повороте переходят только «одноцветные» раскраски (докажите!).