Теория остатков (стр. 9 из 10)
Лемма 2. Пусть
.Тогда:
1)
(формула Эйлера);2)
в частности, ( p ) = p - p -1 , ( p ) = p - 1.
Доказательство. Пусть x пробегает числа 0, 1, 2,..., a - 1. Положим x = ( x , a ) - наибольший общий делитель. Тогда ( a ) есть число значений x , равных 1. Придумаем такую функцию ( x ), чтобы она была единицей, когда x единица, и была нулем в остальных случаях. Вот подходящая кандидатура:
Последнее легко понять, если вспомнить лемму 1 из этого пункта и в ее формулировке взять ( d ) 1. Далее, сделав над собой некоторое усилие, можно усмотреть, что:
Поскольку справа сумма в скобках берется по всем делителям d числа x = ( x , a ), то d делит x и d делит a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел 0, 1, 2,..., a - 1 ровно a / d штук. Получается, что:
что и требовалось.
Пояснение для читателей, у которых предыдущие соображения не захотели укладываться в голову, например, из-за плохих погодных условий. Имеем
Зафиксируем некоторое d 0 такое, что d 0 делит a , d 0 делит x , x < a . Значит в сумме справа в скобках слагаемых ( d 0 ) ровно a / d 0 штук и ( a ) есть просто сумма
После этого, равенство
получается применением следствия из леммы 1 этого пункта. Должен признать, что приведенное доказательство формулы Эйлера и, в особенности, его последний момент с изменением порядка суммирования, объективно тяжеловаты для понимания. Но мы не боимся трудностей!
Второе утверждение леммы следует из первого внесением впереди стоящего множителя a внутрь скобок.
Оказывается, только что доказанная формула
для вычисления функции Эйлера имеет ясный "физический смысл". Дело в том, что в ней отражено так называемое правило включений и исключений:
Правило включений и исключений. Пусть задано множество А и выделено k его подмножеств. Количество элементов множества А , которые не входят ни в одно из выделенный подмножеств, подсчитывается так: надо из общего числа элементов А вычесть количества элементов всех k подмножеств, прибавить количества элементов всех их попарных пересечений, вычесть количества элементов всех тройных пересечений, прибавить количества элементов всех пересечений по четыре и т.д. вплоть до пересечения всех k подмножеств.
Проиллюстрирую это правило на примере подсчета функции Эйлера для чисел вида
Посмотрите на рисунок 1.
Рис. 1.
Прямоугольник изображает множество всех целых чисел от 0 до a ; овал N 1 - множество чисел, кратных p 1 ; кружок N 2 - числа, кратные p 2 ; пересечение N 1,2 - множество чисел, делящихся одновременно на p 1 и p 2 , т.е. на p 1 p 2 ; числа вне овала и кружочка взаимно просты с a . Для подсчета числа чисел, взаимно простых с a , нужно из a вычесть количество чисел в N 1 и количество чисел в N 2 (их, соответственно, a / p 1 и a / p 2 штук), при этом общая часть N 1,2 (там a /( p 1 p 2 ) штук чисел) вычтется дважды, значит ее надо один раз прибавить (вот оно, "включение - исключение"!). В результате получим:
что я вам и утверждал. Мне кажется, что таким способом можно объяснить формулу Эйлера любому смышленому школьнику.
Кстати, любому смышленому школьнику вполне возможно объяснить и то, что при a > 2, ( a ) всегда число четное. Действительно, если k взаимно просто с a и k < a , то число a - k тоже меньше a , взаимно просто с a и не равно k . (Если бы a и a - k имели общий делитель, то их разность a - ( a - k ) = k тоже делилась бы на этот делитель, что противоречит взаимной простоте a и k .) Значит числа, взаимно простые с a разбиваются на пары k и a - k , следовательно, их четное число.
Из леммы 2 вытекают приятные следствия.
Следствие 2. Функция Эйлера мультипликативна.
Доказательство. Имеем:
- произведение двух мультипликативных функций, первая из которых мультипликативна по лемме 2 пункта 13. Значит, ( a ) - мультипликативна.
Следствие 3.
.Доказательство. Пусть
.Тогда, по лемме 1 пункта 13 имеем:
.5 Китайская теорема об остатках
В этом пункте детально рассмотрим только сравнения первой степени вида
ax b(mod m),
оставив более высокие степени на съедение следующим пунктам. Как решать такое сравнение? Рассмотрим два случая.
Случай 1. Пусть а и m взаимно просты. Тогда несократимая дробь m/a сама просится разложиться в цепную дробь:
Эта цепная дробь, разумеется, конечна, так как m/a - рациональное число. Рассмотрим две ее последние подходящие дроби:
.Вспоминаем (пункт 9) важное свойство числителей и знаменателей подходящих дробей: mQ n-1 -aP n-1 =(-1) n . Далее (слагаемое mQ n-1 , кратное m , можно выкинуть из левой части сравнения):
-aP n-1 (-1) n (mod m) т.е.
aP n-1 (-1) n-1 (mod m) т.е.
a[(-1) n-1 P n-1 b] b(mod m)
и единственное решение исходного сравнения есть:
x (-1) n-1 P n-1 b(mod m)
Пример. Решить сравнение 111x 75(mod 322).
Решение. (111, 322)=1. Включаем алгоритм Евклида:
322=11 · 2+100
111=100 · 1+11
100=11 · 9+1
11=1 · 11
(В равенствах подчеркнуты неполные частные.) Значит, n=4 , а соответствующая цепная дробь такова:
Посчитаем числители подходящих дробей, составив для этого стандартную таблицу:
| 0 | 2 | 1 | 9 | 11 | |
| P n | 1 | 2 | 3 | 29 | 322 |
Числитель предпоследней подходящей дроби равен 29, следовательно, готовая формула дает ответ: x (-1) 3 29 75 -2175 79(mod 322)
Ох уж эти мне теоретико-числовые рассуждения из разных учебников, продиктованные традицией изложения и необходимостью обязательно использовать ранее изложенную теорию! О чем идет речь в нескольких строках выше? Дано сравнение ax b(mod m) , где a и m взаимно просты. Ну возьмите вы алгоритм Евклида, найдите те самые пресловутые u , v Z такие, что au+vm=1 , умножьте это равенство на b : aub+vmb=b , откуда немедленно следует: aub b(mod m) . Значит решением исходного сравнения является x ub(mod m) . Собственно, и все. Поворчал.
Случай 2. Пусть (a,m)=d . В этом случае, для разрешимости сравнения ax b(mod m) необходимо, чтобы d делило b , иначе сравнение вообще выполняться не может. Действительно, ax b(mod m) бывает тогда, и только тогда, когда ax- b делится на m нацело, т.е. ax- b=t · m ,
t Z , откуда b=ax- t m , а правая часть последнего равенства кратна d .
Пусть b=db 1 , a=da 1 , m=dm 1 . Тогда обе части сравнения xa 1 d b 1 d(mod m 1 d) и его модуль поделим на d :
xa 1 b 1 (mod m 1 ) ,
где уже а 1 и m 1 взаимно просты. Согласно случаю 1 этого пункта, такое сравнение имеет единственное решение x 0 :
x x 0 (mod m 1 ) (*)
По исходному модулю m , числа (*) образуют столько решений исходного сравнения, сколько чисел вида (*) содержится в полной системе вычетов: 0,1,2,..., m-2, m-1 . Очевидно, что из чисел x=x 0 +t m в полную систему наименьших неотрицательных вычетов попадают только x 0 , x 0 +m 1 , x 0 +2m 1 , ..., x 0 +(d-1)m 1 , т.е. всего d чисел. Значит у исходного сравнения имеется d решений.