Функция Эйлера

Одной из главных задач арифметики остатков является решение уравнения относительно . Линейное уравнение с вещественными коэффициентами при всегда разрешимо. Если же рассматривать его над кольцом целых чисел, то такое уравнение может не иметь решения. Рассмотрим некоторые уравнения в кольце вычетов.

Уравнение имеет ровно одно решение. Действительно, , где , или . Тогда . Это возможно только в случае, если . Однако, в этом случае и при любом , т. е. все решения этого уравнения равны между собой по модулю 143. Рассмотрим уравнение . В этом случае , где , или , т. е. уравнение не имеет решений. Уравнение () имеет 11 решений (при , т. к. - целое число, причем ).

Таким образом, встает вопрос, при каких значениях и уравнение имеет решения и как их все найти.

Существует критерий, позволяющий определить, имеет ли данное уравнение ни одного, одно или несколько решение.

1. Если НОД , то существует равно одно решение. Оно может быть найдено с помощью промежуточного числа , удовлетворяющего уравнению , после чего искомое неизвестное вычисляется по формуле .

Пример. Рассмотрим уравнение . В этом случае НОД и можно взять . Тогда . Если взять , то . В общем виде можно взять и .

2. Если НОД и НОД делит , то уравнение будет иметь решений. Чтобы их найти, нужно разделить исходное уравнение на : , где , , . Если - решение полученного уравнения, то решение исходного - любое число вида , где .

Пример. Рассмотрим уравнение . В этом случае НОД и уравнение имеет 11 решений. Тогда . Решение полученного уравнения и , .

3. В других случаях решений нет.

Определение. Числа и называются взаимно простыми, если НОД .

Число элементов кольца , взаимно простых с , дается функцией Эйлера и равно . Значение можно найти по разложению числа на простые множители. Если , где - различные простые числа, то .

По разложению числа на простые множители очень легко вычислить . Особый интерес представляют следующие случаи:

1. Если - простое, то .

2. Если и - простые числа и , то .