§ 13. Использование общего метода решета в теории чисел

Рассмотрим применение формул предыдущего параграфа в элементарной теории чисел.

Пусть Введем следующие обозначения: целая часть числа наибольший общий делитель взаимно просты н. о. д. делит не делит

Теорема I. Пусть попарно взаимно просты. Количество целых чисел таких, что равно

Доказательство. Обозначим

и выпишем формулу (12.7):

Имеем

Подставляя (13.4) в (13.3), получаем (13.1).

Числовой пример. Пусть

Количество целых чисел, не превосходящих 35 и не делящихся ни на 3, ни на 7, ни на 8, равно

Рассмотрим другие приложения. Количество целых чисел таких, что

обозначают через и называют функцией Эйлера.

Теорема II. Пусть Тогда

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

Доказательство. Так как все делят и взаимно просты, то имеем

По формуле (13.1)

т. е. получаем (13.8).

Пример. Пусть Простыми делителями 84 являются 2, 3, 7; поэтому

Выписываем все числа, взаимно простые с 2, 3, 7 и не превосходящие 84: 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 79, 83.

Функция Мёбиуса. Представим (13.8) в другом виде, используя функцию Мёбиуса определяемую следующим образом:

Тогда

где суммирование производится по всем делящим (включая 1).

Пример на функцию Мёбиуса. Имеем

При формула (13.13) дает

Решето Эратосфена. Известен следующий способ перечисления простых чисел вычисляется и из последовательности вычеркиваются последовательно

все числа, кратные 2, затем кратные кратные с. Оставшиеся числа и есть искомые.

Используя теорему II, можно получить следующую формулу пересчета. Если через обозначить количество простых чисел таких, что то в силу (13.1)

где простые числа, не превосходящие в правой части добавляется, так как 1 не считается простым).

В силу (13.13)

где суммирование в (13.17) производится по всем простым делителям (включая 1).

Пример. Сколько простых среди чисел Имеем Простыми числами между 2 и 9 будут 2, 3, 5, 7. Согласно (13.16)

Таким образом, имеется всего простых числа среди Решето Эратосфена перечисляет их: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83.