* Данный текст распознан в автоматическом режиме, поэтому может содержать ошибки

МЕТОД СРАВНЕНИЙ 281 взаимно простым с произведением тп число должно быть взаимно простым как с те, так и с л. Поэтому мы можем наш подсчёт вести так: сначала отобрать из таблицы все числа, взаимно простые с те, а потом уже из них выбрать те, которые взаимно просты и с п. Так мы и поступим. В нашей таблице, очевидно, все числа, в одном столбце, принадлежат одному классу по модулю т и, значит, либо все вза­ имно просты с те, либо все не взаимно Мы можем поэтому говорить о «столбцах, взаимно простых с тт>1 Число таких столб­ цов проще всего определить, подсчитывая, сколько чисел, взаимно простых с те, содержит верхняя строка нашей таблицы 1, 2, т. Очевидно, таких чисел будет 9 (те), и под каждым из них лежит столбец чисел, взаимно простых с те. Выберем теперь любой из этих 9 (те) столбцов, например 9 стоящие простои k, те-f-A, 2m-\-k, (я—l)m-{~k, (5) и подсчитаем, сколько в нём будет чисел, взаимно простых с w. Числа этого Столбца представляют собою значения выражения mx-\-k когда х пробегает ряд чисел О, I , 2, п — 1, т. е. пол­ ную систему вычетов по модулю п. Так как те взаимно просто с /г, то в силу теоремы 3 числа ( 5 ) также образуют полную систему вычетов по модулю п\ но любая полная система вычетов по моду­ лю п содержит в точности 9 (п) чисел, взаимно простых с п\ итак, любой столбец нашей таблицы содержит 9 (п) чисел, взаимно про­ стых С /2. Резюмируем: наша таблица содержит 9 (те) столбцов, взаимно простых с те, и в каждом из этих столбцов имеется 9 (л) чисел, взаимно простых с п\ таким образом, таблица содержит y(tn)cp(n) чисел, взаимно простых как с те, так и с п; но это и будут числа, взаимно простые с произведением те/z, так что действительно 9 9(теи) = 9 ( т е ) 9 ( л ) , что и требовалось доказать* Теперь уже легко найти общее выражение для функции 9 (те). Пусть разложение числа те на простые множители имеет вид где p р% ..., р — различные между собой простые числа, a <*я> г — любые натуральные числа. Тогда согласно только что доказанному свойству функции 9 (те) i9 9 г а 9(те)=9(/??1)9(/?|0 . . . 9 ( ^ ) г (6) Но 9(/>"*)О ^l^t) число натуральных чисел, не превосхо­ дящих рн и взаимно простых с p\i т. е. просто не делящихся е с т ь 9