Уравнения эйлера по математике. Калькулятор дзета-функции римана и тождества эйлера Найти функцию эйлера

Функция Эйлера, это функция, которая равна количеству натуральных чисел, меньших 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

Дзета-функция Римана - одна из самых известных формул чистой математики, с которой связана знаменитая неразрешенная математическая проблема - гипотеза Римана. Калькулятор дзета-функции позволяет вычислить ее значения для аргументов, лежащих в пределах от нуля до 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 – простое(р), то а не должно делится на р. Т.е. если а делится на р, то это уже не соответствует определению взаимно простых чисел.

Условие

В теории чисел известна функция Эйлера $latex \varphi(n)$ — количество чисел, меньших $latex n$ и взаимно простых с ним. Напомним, два числа взаимно просты, если у них нет общих делителей, кроме единицы.

Расширим понятие функции Эйлера на строки. Пусть $latex s$ — непустая строка над алфавитом {$latex a$ .. $latex z$}, а $latex k$ — целое положительное число. Тогда $latex s \cdot k$ по определению — строка $latex t = \underbrace{s \circ s \circ \ldots \circ s}_{\text{k}}$ (конкатенация $latex s$ самой с собой $latex k$ раз). В таком случае будем говорить, что строка $latex s$ — делитель строки $latex t$. Например, «ab» — делитель строки «ababab».

Две непустые строки $latex s$ и $latex t$ будем называть взаимно простыми, если не существует строки $latex u$ такой, что она — делитель и для $latex s$, и для $latex t$. Тогда функция Эйлера $latex \varphi(s)$ для строки $latex s$ по определению — количество непустых строк над тем же алфавитом {$latex a$ .. $latex z$}, меньших $latex s$ по длине, и взаимно простых с ней.

Входные данные

Во входном файле дана строка $latex s$ длиной от $latex 1$ до $latex 10^5$ символов включительно, состоящая из маленьких латинских букв.

Выходные данные

Вычислите значение $latex \varphi(s)$ и выведите единственное число — остаток от его деления на $latex 1000000007 (10^9 + 7)$.

Решение

Очевидно, что когда строка $latex s$ длины $latex n$ не имеет делителей, кроме самой себя, любая строка длины меньшей, чем $latex n$, будет взаимно простой с $latex s$. Тогда достаточно посчитать количество всех возможных строк длины от $latex 1$ до $latex n-1$ включительно. Для некоторого $latex k$ количество строк этой длины будет равно $latex 26^k$. Тогда количество $latex m$ всех возможных строк длины от $latex 1$ до $latex n-1$ будет вычисляться по следующей формуле: $latex m=\sum\limits_{k=1}^{n-1} 26^k$.

Теперь рассмотрим случай, когда строка имеет делители. Поскольку строка $latex s$ в таком случае является конкатенацией некоторого количества одинаковых строк меньшей длины, найдём эту самую подстроку, кторая является минимальным (кратчайшим) делителем строки $latex s$. Для этого воспользуемся префикс-функцией. Она возвращает вектор $latex pi$ значений для всех подстрок строки $latex s$, которые являются префиксами $latex s$, где значение — максимальная длина префикса строки, совпадающего с её суффиксом. Тогда на $latex n-1$-ом месте вектора $latex pi$ будет стоять длина наибольшего префикса строки $latex s$, а оставшийся «кусочек» строки $latex s$ будет представлять собой минимальный делитель.

Осталось вычислить количество строк, которые не взаимно просты с $latex s$. Пусть k — длина минимального делителя $latex s$. Тогда все строки, являющиеся конкатенациями этого делителя, не будут взаимно простыми с $latex s$. Для подсчёта их количества достаточно поделить длину исходной строки на k, но ответ будет на единицу меньше, поскольку в этой формуле учитывается и сама строка $latex s$, как собственный делитель.

Для окончательного ответа на задачу остаётся вычесть из общего количества строк количество не взаимно простых с $latex s$.

Тесты

№	Входные данные	Выходные данные
1	aa	25
2	abab	18277
3	abcdefgh	353082526
4	aaaaaab	321272406
5	aaaaaaa	321272406

Программный код

#include #include using namespace std ; const int MOD = 1e9 + 7 ; vector < int > prefix_function (string s ) { int n = s . length () ; vector < int > pi (n ) ; pi [ 0 ] = 0 ; for (int i = 1 ; i < n ; i ++ ) { int j = pi [ i - 1 ] ; while (j > 0 && s [ i ] != s [ j ] ) j = pi [ j - 1 ] ; if (s [ i ] == s [ j ] ) j ++ ; pi [ i ] = j ; return pi ; int main () { string s ; cin >> s ; int n = s . length () ; long long mul = 26 , ans = 0 ; for (int i = 1 ; i < n ; i ++ , mul *= 26 , mul %= MOD )