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

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

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

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

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

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

В таблице справа представлены первые 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 году доказал, что если то

Функция Эйлера (n) определяется для всех целых положительных n и представляет собою число чисел ряда

0,1,…n-1(2.1.)

взаимно простых с n

Теорема2.1. пусть n=…(2.2.)

Каноническое разложение числа n, тогда имеем

или также

(n)n=(-) (-)…(-) (2.4.)

в частности будем иметь

(p 2)= p 2 - p -1 , (p)=p-1 (2.5.)

Действительно, применим теорему 1.8. При этом числа?, f определим так: пусть x пробегают числа ряда (2.1) каждому значению x приведен в соответствие число? =(x, n) и числа x=1.

Тогда S / обратится в число значений =(x, n), равных 1 , т.е. в (n). А S d

Обратится в число значений =(x, n) кратных d.

Но (x,n) может быть кратным d, лишь при условии, что d -делитель числа n .При наличии этого условия S d обратится в число значений x, кратных d, т.е. в.

Откуда ввиду (***) следует формула (2.3.), а из последней в виду (2.2.)

Следует формула (2.4.)

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

Теорема 2.2. (n) - мультипликативна, т.е.

(n 1 n 2) = (n 1)(n 2), при (n 1 ,n 2) = 1

Дадим два доказательства этой теореме:

1. Пусть x приобретает значение 1, 2,…, (n2), образующие приведенную систему вычетов по модулю n2, а y приобретает значения S1, S2,…, S(n1), образующие приведенную систему вычетов по n1 модулю. Составим всевозможные числа вида n11 +n2sj, соответствующие размещенным парам j sj, число таких чисел будет равна

С другой стороны поскольку (n 1 ,n 2) = 1 , эти числа образуют приведенную систему вычетов по модулю n 1 n 2 , т.е. число таких чисел должно равняться (n 1 n 2).Произведение (n 1) (n 2) и (n 1 n 2) выражают одну и ту же величину, т.е.

(n 1 n 2)= (n 1) (n 2)

• 2. Составим таблицу:
• 1,2,3,…,

n 2 +1,n 2 +2,n 2 +3,…, 2 n 2

2n 2 +1,2n 2 +2,2n 2 +3,…, 3 n 2 (2.7)

…………………………………………

(n 1 -1) n 2 +1, (n 1 -1) n 2 +2, (n 1 -1) n 2 +3,…, n 1 n 2

и определим число чисел в этой таблице, взаимно простых с n 1 n 2

(kn 2 +, n 2)=1,

тогда и только тогда, когда (, n 2)=1

Таким образом, числа взаимно простые с n 2 , а тем более с n 1 n 2 могут быть только в столбцах номерами, такими что (, n 2)=1, где 1 n 2 число таких столбцов по определению равно (n 2).

Каждый такой столбец состоит из чисел:

N 2 +, 2n 2 +,…, (n 1 -1) n 2 + (2.8.)

т.е. из чисел вида n 2 x+, где пробегает полную систему вычетов по модулю n. Поскольку (n 1 n 2)=1, то числа (2.8.) образуют также полную систему вычетов по модулю n. И следовательно в (2.8.) содержится (n 1) чисел, взаимно простых с n 2 . Мы имеем таким образом, в таблице (2.7.) (n 2) столбцов чисел, взаимно простых с n 2 , причем каждый такой столбец содержит (n 1) чисел, взаимно простых с n 1 . Если число взаимно с n 2 и с n 1 , то оно взаимно просто с n 1 n 2 . Таким образом, таблица (2.7.) содержит (n 1) (n 2) чисел, взаимно простых с n 1 n 2 .

С другой стороны эта таблица содержит все числа от 1 до n 1 n 2 и таким образом в ней (n 1 n 2) чисел, взаимно простых с n 1 n 2 , т.е.

(n 1) (n 2)= (n 1 n 2)

Теорема 2.3. При n1 (n)=n

Знак p означает здесь то, что множители произведения берутся при всевозможных простых делителях числа n. Доказательство: Любое n1

можно представить в канонической форме