МЕТОД СРАВНЕниИ

281

взаимно простым с произведением гип, число должно быть взаимно

простым как с т, так и с п. Поэтому мы можем наш подсчёт вести

так: сначала отобрать из таблицы все числа, взаимно простые с т,

а потом уже из них выбрать те, которые взаимно просты и с п.

Так мы и поступим.

В нашей таблице, очевидно, все числа, стоящие в одном столбце,

принадлежат одному классу по модулю т и, значит, либо все вза-

имно просты с т, либо все не взаимно просты. Мы можем поэтому

говорить о «столбцах, взаимно простых с т». Число таких столб-

цоп проще всего определить, подсчитывая, сколько чисел, взаимно

простых с т, содержит верхняя строка нашей таблицы 1, 2, ..

т.

Очевидно, таких чисел будет ф (т), и под каждым из них лежит

столбец чисел, взаимно простых с т.

Выберем теперь любой из этих 9 (т) столбцов, например

К, т-+К, 2nz+k, (п— 1) т + К,

(5)

и подсчитаем, сколько в нём будет чисел, взаимно простых с п.

Числа этого Столбца представляют собою значения выражения

тх+К, когда х пробегает ряд чисел 0, 1, 2, .. ., п— 1, т. е- пол-

ную систему вычетов по модулю п. Так как т взаимно просто с п,

то в силу теоремы З числа (5) также образуют полную систему

вычетов по модулю п; но любая полная система вычетов по моду-

лю п содержит в точности ф (п) чисел, взаимно простых с п; итак,

любой столбец нашей таблицы содержит ф (п) чисел, взаимно про-

стых с п.

Резюмируем: наша таблица содержит ? (т) столбцов, взаимно

простых с т, и в каждом из этих столбцов имеется (п) чисел,

взаимно простых с п; таким образом, таблица содержит ф (т) (п)

чисел, взаимно простых как с т, так и с п; но это и будут числа,

взаимно простые с произведением тп, так что действительно

ф (тп) ф (т) ф (П),

что и требовалось доказать.

Теперь уже легко найти общее выражение для функции ф

Пусть разложение числа т на простые множители имеет вид

рт — различные между собой простые числа,

где [11, П,

а аи, аг—любые натуральные числа. Тогда согласно только

что доказанному свойству функции ф(т)

(6)

Но есть число натуральных чисел, не превосхо-

дящих раз и взаимно простых с p?i, т. е. просто не делящихся