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

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

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/pZ) обладает мультипликативным обратным. Кольца с такими свойствами называются полями.

Определение. Полем называется множество (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.

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