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

Рассмотрим число такое, что и Тогда видно, что только одно из чисел и может быть сравнимо с единицей по модулю А любое число в промежутке не взаимно простое с точно не может в степени давать единицу по модулю Откуда сразу следует, что чисел не более

______________________________________________________________________________________________________________________________________________________

Замечание. Эта задача связана с тестом простоты Ферма, в котором мы пытаемся определить простое ли число выбрав случайно число в промежутке и проверить верно ли Данная задача как раз говорит о том, что если существует число из условия, то с хорошей вероятностью нам выдаст нужное число то есть неверно, а значит, составное. Оказывается число из условия задачи может не существовать и по составному модулю, такие числа называют числами Кармайкла. Предлагается подумать о том, как тогда проверять простое ли число. Для этого также есть именной вероятностный тест, а именно тест Соловея-Штрассена.