Функция Эйлера и теорема Эйлера из ТЧ

Сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма.

Пусть - функция Эйлера числа (Количество чисел от до взаимно простых с ) Тогда для любого натурального числа справедливо неравенство

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство леммы.

Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если то

Используя формулу суммы геометрической прогрессии, получаем:

Функция Эйлера вычисляется по формуле Тогда чтобы получить в знаменателе, домножим числитель и знаменатель на

_________________________________________________________________________________________________________________________________________________________________________________

Решение задачи.

По условию и лемме

Тогда

То есть количество чисел от до взаимно простых с меньше

Рассмотрим два случая: делится на и не делится на

1. Число делится на Тогда можно разбить числа от до на групп по идущих подряд чисел. Если количество чисел от до взаимно простых с меньше , то хотя бы в одной группе не будет числа взаимно простого с

2. Число не делится на Тогда среди чисел до можно выделить групп по идущих подряд чисел. Если в каждой группе будет число взаимно простое с , то чисел взаимно простых с хотя бы ( тоже взаимно проста с ). Это противоречит тому, что количество чисел от до взаимно простых с меньше