Леонард Эйлер швейцарский, немецкий и российский математик и механик, внёсший фундаментальный вклад в развитие этих наук, а также физики, астрономии и других. Эйлер - автор более чем 850 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, и математической физике. Он глубоко изучал медицину, химию, ботанику, воздухоплавание, теорию музыки, множество европейских и древних языков. Решение уравнений Эйлера является весьма нетривиальной задачей и требует определенных знаний. Уравнения данного рода имеют средний уровень сложности и изучаются в старших классах школы.

Уравнение Эйлера имеет следующий вид:

\ - постоянные числа.

Благодаря замене \ данное уравнение преобразуется к уравнению с постоянными коэффициентами:

Получаем:

Подставив эти значения, мы получим уравнение с постоянными коэффициентами относительно функции \

Допустим, дано такое уравнение Эйлера:

Решение данного уравнения будем искать в виде \ поэтому:

Вставив эти значения производных получим:

\=0\]

Соответственно, если \ Поскольку \ второй кратности, то\[ y = \frac{1}{x}\] является решением уравнения Эйлера. Другое решение \. В этом можно убедиться, поскольку \[\frac {1}{x}\] и \[ \frac {(ln x)}{x}\] линейно независимые, то:

Это и есть общее решение данного вида уравнения Эйлера.

Где можно решить уравнение Эйлера онлайн?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.

Дзета-функция Римана - одна из самых известных формул чистой математики, с которой связана знаменитая неразрешенная математическая проблема - гипотеза Римана. Калькулятор дзета-функции позволяет вычислить ее значения для аргументов, лежащих в пределах от нуля до 1.

Историческая справка

История дзета-функции Римана начинается с гармонического ряда, открытого еще пифагорейцами, который выглядит как:

1 + 1/2 + 1/3 + 1/4 + 1/5 ... 1/n

Ряд получил свое название благодаря утверждению, что струна, разделенная надвое, натрое или более, издает звуки, советующие математической гармонии. Чем большее количество членов гармонического ряда, тем больше его значение. Говоря строгим математическим языком, это означает, что ряд расходится и стремится к бесконечности.

Известный математик Леонард Эйлер работал с гармоническим рядом и вывел формулу для определения суммы заданного количества членов последовательности. В процессе работы он заинтересовался другим рядом, который был известен с древних времен, однако сегодня носит имя Эйлера. Дроби эйлерового ряда в знаменателях содержат квадраты, а первые члены последовательности выглядят так:

1 + 1/4 + 1/9 + 1/16 + 1/25... 1/n 2

Удивительно, однако, при увеличении количества членов ряда, сумма выражения асимптотически приближается к определенному значению. Следовательно, ряд сходится, а его значение стремится к константе, равной (Pi 2)/6 или 1,64488. Если в знаменатели поставить кубы:

1 + 1/8 + 1/27 + 1/64 + 1/125... 1/n 3

то ряд вновь сходится, но уже к значению 1,20205. В общем виде мы можем представить степенной ряд как дзета-функцию вида:

Z(s) = 1 + 1/2 s + 1/3 s + 1/4 s + 1/5 s

С увеличением степени и количества членов ряда значение функции будет стремиться к единице и для степеней выше 30 выражение Z(s) = 1, следовательно, такой ряд сходится. Вычисление значения ряда при 0>s>1 показывает, что во всех этих случаях функция имеет различные значения, а сумма членов ряда при стремлении к бесконечности постоянно увеличивается, соответственно, ряд расходится.

В гармоническом ряду показатель степени равен единице и ряд также расходится. Однако как только s принимает значение больше единицы, то ряд сходится. Если же меньше - то расходится. Из этого следует, что гармонический ряд находится строго на границе сходимости.

Дзета-функция Римана

Эйлер работал с целыми степенями, однако Бернхард Риман расширил свое понимание функции на действительные и комплексные числа. Комплексный анализ показывает, что дзета-функция имеет бесконечное количество нулей, то есть бесконечное количество значений s, при которых Z(s) = 0. Все нетривиальные нули представляют собой комплексные числа вида a + bi, где i - мнимая единица. Наш онлайн-калькулятор позволяет оперировать только с действительными аргументами, поэтому значение Z(s) всегда будет больше нуля.

Например, Z(2) = (Pi 2)/6, и этот результат рассчитал сам Эйлер. Все значения функции для четных аргументов содержат число Пи, однако расчет для нечетных чисел слишком сложен для представления результата в замкнутом виде.

Гипотеза Римана

Леонард Эйлер использовал функцию Z(s) при работе с теоремой о распределении простых чисел. Риман также ввел эту функцию в своей диссертационной работе. Труд содержал метод, позволяющий подсчитать количество простых чисел (делящихся только на себя и на единицу), которые встречаются в ряду до определенного предела. По ходу работы Риман сделал замечание, что все нетривиальные (то есть, комплексные) нули дзета-функции имеют действительную часть, равную 1/2. Ученый так и не смог вывести строгое доказательство данного утверждения, которое со временем превратилось в Священный Грааль чистой математики.

Строгое доказательство гипотезы Римана обещает пролить свет на распределение простых чисел, над которым математическое сообщество бьется с античных времен. На сегодняшний день рассчитано более полутора миллиардов нетривиальных нулей дзета-функции, и они действительно располагаются на линии x = 1/2. Однако, ни теория о распределении неделимых чисел, ни гипотеза Римана на данный момент не разрешены.

Наш калькулятор позволяет рассчитывать значение Z(s) для любых действительных s. Вы можете использовать целые и дробные, положительные и отрицательные значения аргумента. При этом целые положительные s всегда будут давать результат близкий или равный единице. Значения 0>s>1 всегда приводят к тому, что дзета-функция принимает разные значения. Отрицательные значения s обращают ряд в:

1 + 1 s + 2 s + 3 s + 4 s ...

Очевидно, что при любом отрицательном s ряд расходится и резко устремляется в бесконечность. Рассмотрим численные примеры значения Z(s).

Примеры вычислений

Давайте проверим наши выкладки. В вычислениях программа использует 20 тысяч членов ряда. Определим при помощи калькулятора значения Z(s) для положительных аргументов больше единицы:

• при s = 1 выражение Z(s) = 10,48;
• при s = 1,5 выражение Z(s) = 2,59;
• при s = 5 выражение Z(s) = 1,03.

Рассчитаем значения дзета-функции для 0>s>1:

• при s = 0,9 выражение Z(s) = 17,49.
• при s = 0,5 выражение Z(s) = 281,37;
• при s = 0,1 выражение Z(s) = 8 253,59.

Рассчитаем значения Z(s) для s<0:

• при s = -0,5 выражение Z(s) = 1 885 547.
• при s = -1 выражение Z(s) = 199 999 000;
• при s = -3 выражение Z(s) = 39 996 000 100 000 010;

Очевидно, что при небольшом изменении s от единицы в большую сторону функция начинает медленное, но неуклонное движение к Z(s) = 1. При изменении аргумента от единицы в меньшую сторону функция принимает все большие и большие значения и устремляется в бесконечность.

Заключение

Дзета-функция Римана и связанная с ней гипотеза - одна из наиболее популярных открытых проблем современной математики, над решением которой ученые бьются уже более 150 лет. Доказательство гипотезы Римана позволит математикам сделать большой прорыв в теории чисел, что, несомненно, приведет научное сообщество к еще большим открытиям.

Числовые функции

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

Имеется целое, положительное число 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.

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

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

m= 60 = 2*2*3*5; в каноническом виде - 2 2 *3*5: p 1 =2; p 2 =3; p 3 =5;

Справка: Любое составное число раскладывается однозначно.

Есть формула которая учитывает кратность сомножителей, а некоторые не учитывают.

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

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

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

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

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

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

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

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

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

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

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

Берем число a, возводим в ,берем модуль от

т.е. остаток будет равен всегда единице.

Это мы рассматривали нахождением обратных элементов. К этой теореме мы вернемся позже.

Частный случай: m- простое(p), то:

Это теорема малая Ферма, а Эйлер усилил, распространил на все функции Эйлера.

Ограничений у этого частного случая меньше, чем у теореме Эйлера. т.к. тут автоматически m и р – взаимно просты.

Допустим если а вне диапазона (a>m),

если а и m – взаимно просты то будет справедливо и для этого случая.

А если m – простое(р), то а не должно делится на р. Т.е. если а делится на р, то это уже не соответствует определению взаимно простых чисел.

Функция Эйлера, это функция, которая равна количеству натуральных чисел, меньших m и взаимно простых с m . Предполагается, что число 1 взаимно просто со всеми натуральными числами (и с единицею). Обозначается функция Эйлера греческой буквой φ .

m

Сформулируем следующие задачи.

Задача 1. Пусть a 1 , a 2 , a 3 , ...все отличные друг от друга простые множители числа m . Найти число тех чисел, которые не делятся ни на одно из чисел a 1 , a 2 , a 3 , ... .

Более общая задача имеет следующий вид:

Задача 2. Пусть a 1 , a 2 , a 3 , ...взаимно простые числа, которые входят множителями в m . Найти число всех чисел, которые не делятся ни на одно из чисел a 1 , a 2 , a 3 , ... .

Возьмем ряд натуральных чисел до m :

Их число равно . Исключим эти числа из ряда (1). Тогда останутся

Их количество равно .

Эти числа можно представить в виде ka 2 , где k пробегает натуральные числа

.

(3)

Для того, чтобы ka 2 не делился на a 1 необходимо и достаточно, чтобы k не делился на a 1 (т.к. a 1 и a 2 взаимно простые числа). Нужно найти количество чисел из ряда (1), которые делятся на a 1 и исключить их из ряда (3). делится на a 1 т.к. m делится на a 1 , m делится на a 2 и m делится на a 1 a 2 (a 1 , a 2 входят множителями в m m , которое мы решили с помощью формулы (2). Из ряда A 1 нужно исключить числа, которые делятся на a 1 . Тогда взяв вместо m число получим

A 2 . Далее удалим из A 2 те числа, которые делятся на a 3 . Это те числа из ряда (1), которые делятся на a 3 и не делятся на a 1 и a 2 .

Числа ряда (1), которые делятся на a 3 следующие:

Для того, чтобы ka 3 не делился на a 1 и a 2 необходимо и достаточно, чтобы k не делился на a 1 и a 2 (т.к. a 3 и a 1 а также a 3 и a 2 числа взаимно простые). Нужно найти количество чисел из ряда (1), которые делятся на a 1 и a 2 и исключить из ряда (6). делится на a 1 и a 2 , так как m делится на a 1 , m делится на a 2 и m делится на a 1 a 2 a 3 (a 1 , a 2 , a 3 входят множителями в m ). Задача по отношению числа та же, что и задача по отношению числа m , которое мы решили с помощью уравнения (5). Число тех чисел ряда (6), которые не делятся ни на a 1 ни на a 2 (или число тех чисел ряда (1), которые делятся на a 3 и не делятся ни на a 1 , ни на a 2):

Обозначим множество этих чисел через A 3 . Рассуждая таким образом, заключим, что число A i тех чисел ряда (1), которые не делятся на a 1 , a 2 , ..., a i равно

.

(7)

Мы получили число тех чисел ряда (1), которые не делятся на числа a 1 , a 2 , ..., a i . Получим формулу для чисел a 1 , a 2 , ..., a i , a i+1 , где a i+1 также входит множителем в m и взаимно простое с a 1 , a 2 , ..., a i .

Чтобы найти число тех чисел ряда (1), которые не делятся на a 1 , a 2 , ..., a i+1 , нужно из множества (7) исключить числа кратные a i+1 . Это те числа ряда (1), которые не делятся на a 1 , a 2 , ..., a i и делятся на a i+1 .

Все числа ряда (1), которые делятся на a i+1 , следующие:

чисел, которые не делятся на a 1 , a 2 , ..., a i , т.е.

Мы доказали следующую теорему:

Теорема 1. Если a 1 , a 2 , ..., a q , все различные взаимно простые числа, входящие в m , то число чисел, которые не делятся ни на одно из чисел a 1 , a 2 , ..., a q и входящих в ряд m равно:

определяется формулой (8).

Действительно. Всякое число, которое не делится ни на один из простых множителей, входящих в состав m является взаимно простым с m . Тогда учитывая теорему 1, получаем доказательство данной теоремы.

Найденная формула можно переписать и в другом виде. Если a 1 , a 2 , a 3 , ... все различные простые числа, входящие множителями в m , то

Таких чисел 24. Учитывая, что 90=2·3 2 ·5, для φ(m) мы находим

Доказательство. Если a 1 , a 2 , a 3 ,... различные простые числа, входящие в состав m 1 и b 1 , b 2 , b 2 , ... различные простые числа, входящие в состав m 2 , то

a 1 , a 2 , a 3 , ... b 1 , b 2 , b 3 , ...

(9)

различные простые числа, входящие в состав m 1 m 2 , так как m 1 и m 2 взаимно простые числа, т.е. они не имеют общих делителей.

Справедливо и обратное. Всякое простое число входящее в произведение m 1 m 2 должно совпадать с числом из ряда (9), так как это простое число входит множителем или в m 1 , или в m 2 .

Таким образом числа ряда (9) представляют множество всех простых чисел, входящих в произведение m 1 m 2 . Следовательно

С другой стороны

Эта теорема справедлива и для любого числа сомножителей, если эти сомножители взаимно простые числа.

Действительно.

чисел взаимно простых с m .

Более общая задача состоит в следующем:

Задача 3. Дан ряд (10) и требуется найти число тех чисел, этого ряда, которые имеют с m наибольший общий делитель λ , причем m=nλ , т.е. λ является одним из делителей числа m .

Очевидно, что искомые числа находятся среди чисел

Для того, чтобы λ было наибольшим общим делителем чисел m=nλ и kλ из ряда (11), необходимо и достаточно, чтобы k и n были числами взаимно простыми. Следовательно, т.к. k принимает значения

и разобьем ряд

Рассмотрим пример.

Пример . Пусть m =90. Делители числа m следующие:

1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90

φ (1)=1, φ (2)=1, φ (3)=2, φ (5)=4, φ (6)=2, φ (9)=6, φ (10)=4, φ (15)=8, φ (18)=6, φ (30)=8, φ (45)=24, φ (90)=24

φ (1)+ φ (2)+ φ (3)+ φ (5)+...+ φ (90)=90

И значения ее лежат в множестве натуральных чисел.

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

В таблице справа представлены первые 99 значений функции Эйлера. Анализируя эти данные, можно заметить, что значение не превосходит , и в точности ему равно, если - простое. Таким образом, если в координатах провести прямую то значения будут лежать либо на этой прямой, либо ниже её. Также, глядя на график, приведенный в начале статьи, и на значения в таблице, можно предположить, что существует прямая, проходящая через ноль, которая ограничивает значения снизу. Однако, оказывается, такой прямой не существует. То есть, какую бы пологую прямую мы ни провели, всегда найдется натуральное число такое что лежит ниже этой прямой. Еще одной интересной особенностью графика, является наличие некоторых прямых, вдоль которых концентрируются значения функции Эйлера. Так, например, помимо прямой на которой лежат значения где - простое, выделяется прямая, примерно соответствующая на которую попадают значения где - простое.

Более подробно поведение функции Эйлера рассматривается в разделе .

Первые 99 значений функции Эйлера (последовательность A000010 в OEIS)

	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Мультипликативность функции Эйлера

Одним из основных свойств функции Эйлера является её мультипликативность . Это свойство было установлено еще Эйлером и формулируется оно следующим образом: для любых взаимно простых чисел и

Доказательство мультипликативности

Для доказательства мультипликативности функции Эйлера потребуется следующая вспомогательная теорема.

Теорема 1. Пусть и пробегает приведенную систему вычетов по модулю в то время как пробегает приведенную систему вычетов по модулю Тогда пробегает приведенную систему вычетов по модулю Доказательство. Если тогда поэтому аналогично Поэтому существует несравнимых по модулю чисел, которые образуют приведенную систему вычетов по модулю

Теперь можно доказать основное утверждение.

Теорема 2. Функция Эйлера мультипликативна. Доказательство. Если то по Теореме 1 пробегает приведенную систему вычетов по модулю когда и пробегают приведенные системы вычетов по модулям и соответственно. Также: Поэтому чисел, которые меньше числа и взаимно просты с ним, являются наименьшими положительными вычетами среди значений для которых взаимно просто с и взаимно просто с Отсюда следует, что

Функция Эйлера от простого числа

которая следует из определения. Действительно, если - простое, то все числа, меньшие , взаимно просты с ним, а их ровно штук.

Для вычисления функции Эйлера от степени простого числа используют следующую формулу:

Это равенство обосновывается следующим образом. Подсчитаем количество чисел от до , которые не взаимно просты с . Все они, очевидно, кратны то есть, имеют вид: Всего таких чисел Поэтому количество чисел, взаимно простых с равно

Функция Эйлера от натурального числа

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

где - простое число и пробегает все значения, участвующие в разложении на простые сомножители.

Доказательство

где - наибольший общий делитель и Это свойство является естественным обобщением мультипликативности.

Доказательство обобщённой мультипликативности

Пусть тогда причем в общем случае и Поэтому можно записать:

Здесь первые делителей являются также делителями а последние делителей являются делителями Распишем:

В силу мультипликативности функции Эйлера, а также с учетом формулы

где - простое, получаем:

В первой строке записано во второй - а третью можно представить, как Поэтому:

Некоторые частные случаи:

Теорема Эйлера

Наиболее часто на практике используется свойство, установленное Эйлером :

если и взаимно просты .
Это свойство, которое называют теоремой Эйлера , вытекает из Теоремы Лагранжа и того факта, что φ(m ) равна порядку группы обратимых элементов кольца вычетов по модулю m .
В качестве следствия теоремы Эйлера можно получить малую теорему Ферма . Для этого нужно взять не произвольное а простое. Тогда:

Последняя формула находит применение в различных тестах простоты .

Другие свойства

Исходя из представимости произведением Эйлера, несложно получить следующее полезное утверждение:

Всякое натуральное число представимо в виде суммы значений функции Эйлера от его делителей:

Сумма всех чисел, меньших данного, и взаимно простых с ним, выражается через функцию Эйлера:

Множество значений

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

Доказательство (функция Эйлера принимает только чётные значения при n > 2)

Действительно, если - простое нечётное и то - чётное. Из равенства следует утверждение.

В действительном анализе часто возникает задача нахождения значения аргумента по заданному значению функции, или, другими словами, задача нахождения обратной функции . Подобную задачу можно поставить и для функции Эйлера. Однако, надо иметь в виду, что

В связи с этим нужны особые методы анализа. Полезным инструментом для исследования прообраза является следующая теорема:

Если то

Доказательство теоремы

Очевидно, если то С другой стороны, если и то Однако, если то Поэтому Следовательно

Эта теорема показывает, что прообраз элемента всегда представляет собой конечное множество. Также она дает практический способ нахождения прообраза. Для этого нужно

Может оказаться, что в указанном промежутке нет такого числа что в этом случае прообраз является пустым множеством .
Стоит отметить, что для вычисления нужно знать разложение на простые сомножители, что для больших является вычислительно сложной задачей. Затем, нужно раз вычислить функцию Эйлера, что для больших чисел также весьма трудоёмко. Поэтому нахождение прообраза в целом является вычислительно сложной задачей.

Пример 1 (Вычисление прообраза)

Найдем прообраз 4. Делителями 4 являются числа 1, 2 и 4. Добавляя по единице к каждому из них, получаем 2, 3, 5 - простые числа. Вычисляем

Чтобы найти прообраз 4, достаточно рассмотреть числа от 5 до 15. Проделав выкладки, получим:

Пример 2 (Не все чётные числа являются значениями функции Эйлера)

Не существует, например, такого числа что То есть:

В самом деле, делители 14 суть 1, 2, 7 и 14. Добавив по единице, получим 2, 3, 8, 15. Из них только первые два числа - простые. Поэтому

Перебрав все числа от 15 до 42, несложно убедиться, что

Асимптотические соотношения

Простейшие неравенства

для всех кроме и для всякого составного

Сравнение φ(n ) с n

Отношение последовательных значений

плотно в множестве действительных положительных чисел. плотно на интервале

Асимптотики для сумм

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

Порядок функции Эйлера

где - постоянная Эйлера-Маскерони . для всех , с одним исключением в указанном случае следует заменить на Это одна из наиболее точных оценок снизу для Как отмечает Paulo Ribenboim (англ. ) по поводу доказательства этого неравенства: "Способ доказательства интересен тем, что неравенство сначала устанавливается в предположении, что гипотеза Римана верна, а затем в предположении, что она не верна".

Связь с другими функциями

Функция Мёбиуса

где - функция Мёбиуса .

Ряд Дирихле

Ряд Ламберта

Наибольший общий делитель

Действительная часть: В отличие от произведения Эйлера, вычисления по этим формулам не требуют знания делителей

Приложения и примеры

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

На основе алгоритма, предложенного в 1978 году Рональдом Ривестом , Ади Шамиром и Леонардом Адлеманом была построена первая система шифрования с открытым ключом, получившая название по первым буквам фамилий авторов - система RSA . Криптостойкость этой системы определяется сложностью разложения на сомножители целого n -разрядного числа. Ключевую роль в алгоритме RSA играет функция Эйлера, свойства которой и позволяют построить криптографическую систему с открытым ключом .

На этапе создания пары из секретного и открытого ключей, вычисляется

где и - простые. Затем выбираются случайные числа так, чтобы

Затем сообщение шифруется открытым ключом адресата:

После этого расшифровать сообщение может только обладатель секретного ключа

Корректность последнего утверждения основывается на теореме Эйлера и китайской теореме об остатках .

Доказательство корректности расшифрования

В силу выбора чисел на этапе создания ключей

Если то, с учетом теоремы Эйлера,

В общем случае и могут иметь общие делители, но расшифрование все равно оказывается верным. Пусть По китайской теореме об остатках:

Подставляя получаем тождество

Следовательно,

Вычисление обратного элемента

Функция Эйлера может быть использована для вычисления обратного по умножению элемента по модулю , а именно:

если

Пример (Вычисление обратного элемента)

Найдем , то есть такое число , что

Очевидно, и не имеют общих делителей кроме единицы, , при этом число простое и

поэтому удобно воспользоваться формулой, приведенной выше:

Легко проверить, что в самом деле

Замечание 1 (Оценка сложности вычисления)

В общем случае для вычисления обратных значений алгоритм Эвклида быстрее, чем использование теоремы Эйлера, так как битовая сложность вычисления по алгоритму Эвклида имеет порядок в то время как вычисление по теореме Эйлера требует порядка битовых операций, где Однако, в случае, когда известно разложение на простые сомножители, сложность вычислений можно уменьшить, используя алгоритмы быстрого возведения в степень: Алгоритм Монтгомери или алгоритм "возводи в квадрат и перемножай" .

Замечание 2 (Отсутствие решения в случае (a, n) ≠ 1)

Если то обратного к элемента не существует, или, иначе говоря, уравнение

не имеет решения на множестве натуральных чисел.
Доказательство. В самом деле, допустим

и решение существует. Тогда по определению наибольшего общего делителя

причем

поэтому можно записать:

где

или, перегруппировав слагаемые,

Слева стоит целое отличное от нуля число, значит и справа должно быть целое отличное от нуля число, поэтому с необходимостью

что противоречит предположению.

Решение линейного сравнения

Метод вычисления обратного элемента можно использовать для решения сравнения

если

Пример (Решение линейного сравнения)

Рассмотрим сравнение

Так как можно воспользоваться указанной формулой:

Подстановкой убеждаемся, что

Замечание (Неединственность решения или отсутствие решения в случае (a, n) ≠ 1)

Если , сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение

не имеет решения на множестве натуральных чисел. В то же время сравнение

имеет два решения

Вычисление остатка от деления

Функции Эйлера позволяет вычислять остатки от деления больших чисел.

Пример 1 (Последние три цифры в десятичной записи числа)

Найдем последние три цифры в десятичной записи числа Замечая, что

получаем

Переходя теперь от модуля к модулю имеем:

Следовательно, десятичная запись числа оканчивается на

Пример 2 (Остаток от деления на 1001)

Найдем остаток от деления на Легко видеть, что

Поэтому, воспользовавшись мультипликативностью функции Эйлера и равенством

для всякого простого

получаем

Нахождение порядка мультипликативной группы кольца вычетов

Мультипликативная группа кольца вычетов по модулю состоит из классов вычетов .
Пример. Приведённая система вычетов по модулю 14 состоит из классов вычетов:

Приложения в теории групп

Число порождающих элементов в конечной циклической группе равно . В частности, если мультипликативная группа кольца вычетов по модулю является циклической группой - что возможно только при , где - простое нечетное, - натуральное, - то существует генераторов группы (первообразных корней по модулю ).
Пример. Группа рассмотренная в примере выше, имеет генератора: и

Нерешенные вопросы

Задача Лемера

Как известно, если - простое, то В 1932 Лемер (англ. ) задался вопросом, существует ли такое составное число что является делителем Лемер рассматривал уравнение

где - целое. Ему удалось доказать, что если - решение уравнения, то либо - простое, либо оно является произведением семи или более различных простых чисел. Позже были доказаны и другие сильные утверждения. Так в 1980 году Cohen и Hagis показали, что если составное и делит то и где - количество простых делителей. В 1970 году Lieuwens установил, что если то и Wall в 1980 году доказал, что если то