Решение сравнений и их приложения

Примеры.
№1. Чему равна сумма
Решение: ,
, =18 (1- ) (1- =18 , тогда = 1+1+2+2+6+6=18.
№2. На основании свойств числовой функции Эйлера доказать, что в последовательности натуральных чисел существует бесконечное множество простых чисел.
Решение: Пологая количество простых чисел конечным множеством, допустим, что - наибольшее простое число и пусть a= есть произведение всех простых чисел, на основании одного из свойств числовой функции Эйлера

Так как a≥ , то a – составное число, но так как его каноническое представление содержит все простые числа, то =1. Имеем:
=1 ,
что невозможно, и таким образом доказано, что множество простых чисел бесконечно.
№3.Решить уравнение , где х= и =2.
Решение: Используем свойство числовой функции Эйлера,
,
и по условию =2.
Выразим из =2 , получим , подставим в
:
(1+ -1=120, =11 =>
Тогда х= , х=11·13=143.
Ответ: х= 143

2. 
   Теорема Эйлера и Ферма.
   

В теории сравнений важную роль играет теорема Эйлера.

Теорема Эйлера.
Если целое число a взаимно простое с m, то
(1)
Доказательство. Пусть
(2)
есть приведённая система вычетов по модулю m.
Если a-целое число, взаимно простое с m, то
(3)
также есть приведённая система вычетов по модулю m. Поэтому произведение чисел (3) сравнимо с произведением чисел (2), то есть
(4)
Произведение взаимно простое с m. Поэтому согласно свойству 9 обе части сравнения (4) можно разделить на это произведение, тогда

Особенно простой вид теорема Эйлера принимает, если m=p – простое число. В этом случае , а потому получаем следующее утверждение.
Теорема Ферма.
Если целое число а не делится на простое число p, то

Теорема Ферма часто формулируется иначе:
Если p-простое и а-любое целое число, то