Для доказательства достаточно слегка видоизменить метод Ивори, опустив среди чисел О, 1, ..ш - 1 не только число О, но и все числа, имеюгцие обгцие множители с т. Останется (р(т) чисел, обозначим их соответственно через ai, а2, ..., а, здесь /X = (р{т). Тогда числа

aix а2Х ..., Qfjx

сравнимы (в некотором порядке) с предыдугцими числами; перемножив их и затем сократив на aia2...a (что допустимо), получим х = 1 (mod ш); это дает (4).

Для иллюстрации доказательства положим ш = 20. Числа, меньгпие 20 и взаимно простые с 20, таковы:

1, 3, 7, 9, 11, 13, 17, 19,

поэтому (f{20) = 8. Если мы умножим эти числа на любое число, взаимно простое с 20, то новые числа будут сравнимы с исходными числами, взятыми в некотором другом порядке. Например, если X равно 3, новые числа сравнимы соответственно с

3, 9, 1, 7, 13, 19, 11, 17 (mod 20);

наше рассуждение доказывает, что 3 = 1 (mod 20). Фактически 3 = 6561.

4. Функция Эйлера (р{т). Как только что было сказано, (f{m) - это количество чисел, меньших т и взаимно простых с т. Естественно спросить, какие соотношения связывают (f{m) и т. Мы видели, что (f{p) = р-1 для любого простого р. Легко вычислить также (f{p) для степени простого числа р. В ряду О, 1, ..., - 1 не взаимно просты с р только числа, делягциеся на р. Это - числа вида р\ где t = О, 1, 2, ..., р~. Их число равно а когда мы вычтем это из полного количества р

всех чисел, меньших р, мы получим

=Р"-К"=К"(р-1)- (5)

Чтобы найти значение (f{m) для любого ш, докажем, что эта функция мультипликативна. Это означает, что для любых взаимно простых чисел а и b выполняется равенство

{ab) = ip{a)ip{b). (6)

Начнем с одного обгцего замечания: если а и b взаимно просты, то система двух сравнений вида

X = а (mod а), х = (3 (mod Ъ) (7)

в точности эквивалентна одному сравнению по модулю аЬ. Действительно, первое сравнение означает, что х = а + at, где t - какое-нибудь целое. Число х удовлетворяет второму сравнению тогда и только тогда, когда

а + at = Р (mod b) или at = (3 - а (mod Ъ). Последнее сравнение, будучи линейным, разрешимо относительно t. Значит, система сравнений (7) также разрешима. Ес-яи X vl х - два решения этой системы, то х = х (mod а) и X = х (mod 6), и поэтому х = х (mod аЪ). Таким образом, имеется ровно одно решение системы по модулю аЬ. Этот принцип, обобгценный на несколько сравнений с попарно взаимно простыми модулями, иногда называют «китайской теоремой об остатках». Эта теорема показывает, что имеются числа с любыми предписанными остатками от деления на заданные попарно взаимно простые модули.

Обозначим решение системы сравнений (7) через х = = [а, (5] (mod а), так что [а, (5] - это некоторое число, зависягцее от а vl (5 {д, также, конечно, от а и 6) и однозначно определенное по модулю аЬ. Различные пары значений а и (3 порождают разные значения для [а, [5]. Если придавать а значения О, 1, ..., а - 1 (образуюгцие полную систему вычетов по модулю а), а 5 придавать значения О, 1, 1, то получаюгциеся значения

а, (3] образуют полную систему вычетов по модулю аЪ.

Ясно, что если а и а имеют обгций множитель, то х из (7) делится на этот множитель; иными словами, [а, (5] делится на обгций множитель а и а. Таким образом, [а, (5] взаимно просто с аЬ, только если а взаимно просто с а и Р взаимно просто с 6, и, наоборот, эти условия гарантируют, что [а, (3] взаимно просто с аЬ, Следовательно, если а принимает (f{a) значений, меньших а и взаимно простых с а, (5 принимает (р(Ь) меньших и взаимно простых с b значений, то для [а,13\ получается (р{а)(р{Ь) значений и среди значений [а, (3] содержатся все меньшие аЬ и взаимно простые с аЬ числа. Значит, р{аЬ) - (р{а)(р{Ь), и равенство (6) доказано.

Для иллюстрации возникающей в только что приведенном доказательстве ситуации составим таблицу величин [а (3] при а = 5 и 6 = 8. Возможные значения для а - числа О, 1, 2, 3, 4; возможные значения для /3 - числа О, 1, 2, 3, 4, 5, 6, 7. Из них для а имеется четыре значения, взаимно простых с а (в согласии с тем, что = 4); для (3 также имеется 4 значения.

взаимно простых с Ъ (это согласуется с формулой (5), по которой Lp(S) = 4). Эти значения выделены в таблице курсивом, как и соответствующие им значения [о:,/5]. Выделенные курсивом значения [о:, 13] дают 16 чисел, меньших числа 40 и взаимно простых с ним; таким образом,

((40) = ¥)(5)¥)(8) = 4 . 4 = 16.

Вернемся теперь к вопросу о вычислении Lp{m) для произвольного числа т. Пусть разложение т в произведение степеней простых имеет вид т = pq .... Тогда из (5) и (6) следует, что

(т) = (К-р«-)(/-/-)...

или в более изящной форме

ipim) = ш ( 1--

Например,

<(40) = 40 <(60) = 60

1 - -

2 1\

= 16;

= 16.

В своих «Арифметических исследованиях ь Гаусс впервые приводит одно замечательное свойство функции Lp(m): сумма чисел {а), где а пробегает всевозможные делители числа т, равна самому т. Например, при m = 12 делителями т будут