Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма

Одна из центральных задач арифметики остатков - решение сравнения:

a · x º b (mod n)

- Если НОД (a, n) = 1, то существует ровно одно решение, и оно находится с помощью a ^-1: так как

a · a ^-1 º 1 (mod n),

то, домножив обе части сравнения на a ^-1, получим

x º b · a ^-1 (mod n).

- Если НОД (a, n) = g ¹ 1 и g | b, то сравнение имеет g решений. Чтобы их найти нужно разделить исходное сравнение на g:

a’ · x’ º b’ (mod n’),

где a’ = a / g, b’ = b / g, n’ = n / g. Если x’ – решение полученного сравнения, то решение исходного сравнения - любое число вида

x = x’ + i · n’,

где i = 0, 1,..., g – 1.

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

Пример:

7 · x º 3 (mod 143) – одно решение,

11 · x º 3 (mod 143) – решений нет,

11 · x º 22 (mod 143) – 11 решений.

Ситуация с единственным решением наиболее интересна для криптологии, поэтому важно знать количество элементов кольца, взаимно простых с его модулем. Оно дается функцией Эйлера j и равно j (n). Значение j (n) можно легко найти по разложению числа n на простые множители. Если

,

где p_i – различные простые числа, то

Функция Эйлера для любого n > 2 имеет четное значение.

- наибольшее подмножество элементов, образующих группу по умножению # = j (n). (количество элементов мультипликативной группы кольца вычетов по модулю n равно j (n)).

Особый интерес представляют частные случаи:

1. Если p простое, то j (p) = p – 1.

2. Если p и q – простые и p ¹ q, то j (p · q) = (p – 1)(q – 1).

Если p - простое число, то любой элемент в Z _p (или Z / p Z) обладает мультипликативным обратным. Кольца с такими свойствами называются полями.

Определение. Полем называется множество (F, ·, +) с двумя операциями, обладающее свойствами:

- (F, +) – абелева группа с нейтральным элементом 0,

- (F \ {0}, ·) – абелева группа с нейтральным элементом 1,

- (F, ·, +) удовлетворяет закону дистрибутивности (умножение дистрибутивно относительно сложения).

Поле – коммутативное кольцо, в котором каждый ненулевой элемент обратим. Каждый ненулевой элемент кольца Z _p взаимно прост с p, так как p простое и, следовательно, обратим. Значит Z _p – конечное поле, которое обычно называют полем вычетов по модулю p и обозначают F _p = {0, 1,..., p – 1}. Мультипликативная группа = {1,..., p – 1} поля вычетов содержит все ненулевые элементы F _p.

Теорема Лагранжа. .

Обобщение Эйлера для малой теоремы Ферма. , при НОД(x, n) = 1.

Малая теорема Ферма. .