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

 

Имеется целое, положительное число m. Оно может быть как составным, так и простым.

Функцию Эйлера принято обозначать, практически во всех учебниках как:

 

 

Назначение функции:

 

Допустим, мы имеем число m – натуральное. Рассмотрим на оси все числа.

 

1,2,3,4…. m-1 m

 

Вопрос:

 

Сколько чисел в диапазоне от 1 до m-1 (m) , являются взаимно простыми? (имеют с m НОД=1)

(a,m)=1 – должны быть взаимно простыми. (должны быть взаимно простыми с m)

Если m=p, то взаимно простых будет p-1. Т.к. если число m-простое, то все числа являются для него взаимно простыми, исключая само число m.

Ну а если число m составное?

 

Эйлер установил такую закономерность, что существует определенная формула, по которой можно вычислить число взаимно простых. (самый простой способ это перебор).

Эта формула определяется на основе разложения числа m.

 

- раскладываем на простые сомножители.

 

Теперь надо использовать только различающиеся сомножители. Пример:

 

60 2

 

30 2

 

15 3

 

5 5

 

m= 60 = 2*2*3*5; в каноническом виде - 22*3*5 : p1=2; p2=3; p3=5; Содержательно, Функция Эйлера устанавливает число взаимно простых чисел с заданным числом m.

 

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

Эти две формулы мы и рассмотрим.

 

Пусть разложение число m такое, что все сомножители разные.

 

I) Участвует само число m, затем следует рекуррентное выражение:

 

 

В нашем случае:

 

;

 

Значит, от 1 до 60 находятся 16 взаимно простых чисел с числом 60. II)

 

В нашем случае:

 

 

Отметим приложение функцииЭйлера в криптографии.

 

В криптографии часто надо вычислять, шифровать по некоторому модулю. Модуль может быть как составным так и простым. Когда модуль составное число, тогда и используется функция Эйлера для однозначного шифрования. Там осуществляется ,преобразование с множеством чисел, которые являются взаимно простыми в заданном модулем диапазоне.

Классическое (наиважнейшее) приложение этой функции такое:

 

Заданно некоторое натуральное число aи заданно некоторое число m, пусть m-составное, натуральное, положительное. Если эти два числа взаимно просты, тогда для этой пары чисел справедлива следующая теорема (теорема Эйлера) :