Теория первообразных корней и их применение

Теория первообразных корней и их применение
Высшая математика
курсовая
42
2019
RUB 1500
1500р.

Нажмите, чтобы зарегистрироваться. Работа будет добавлена в личный кабинет.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ 3
1. Теоретические аспекты первообразных корней 5
1.1. Определение первообразных корней и гипотеза Артина 5
1.2. Алгоритм нахождения первообразного корня 8
1.3. Существование и количество первообразных корней 12
1.4. Извлечение корня. Первообразные корни из единицы 15
1.5. Функия Эйлера 16
2. Теоретическое и практическое применение первообразных корней 25
2.1. Методы вычисления первообразных корней 25
2.2. Теорема о существовании первообразных корней по модулям 2, 4, pn, 2⋅pn 33
2.3. Применение первообразных корней в криптографии 36
ЗАКЛЮЧЕНИЕ 41
СПИСОК ЛИТЕРАТУРЫ 42

ВВЕДЕНИЕ
До публикации книги "Disquisitiones" теория чисел состояла из набора изолированных теорем и гипотез. Гаусс привел работы своих предшественников вместе со своими собственными оригинальными работами в систематическую структуру, заполнил пробелы, исправил необоснованные доказательства и расширил тему многочисленными способами.
Логическая структура дискурсов (утверждение теоремы с последующим доказательством, за которым следуют следствия) установила стандарт для более поздних текстов. Признавая первостепенную важность логического доказательства, Гаусс также иллюстрирует многие теоремы численными примерами.
Эти исследования были отправной точкой для работы других европейских математиков XIX века, включая Эрнста Куммера, Питера Густава Лежена Дирихле и Ричарда Дедекинда. Многие аннотации, предоставленные Гауссом, по сути, являются объявлениями о его собственных дальнейших исследованиях, некоторые из которых остались неопубликованными. Они, должно быть, казались особенно загадочными его современникам; теперь они могут быть прочитаны как содержащие зародыши теорий L-функций и сложного умножения, в частности.
В XX веке продолжалось влияние гауссовских изысканий. Например, в разделе V статьи 303 Гаусс обобщил свои вычисления чисел классов собственных примитивных двоичных квадратичных форм и предположил, что он нашел все из них с номерами классов 1, 2 и 3. Это было позже интерпретировано как определение мнимых квадратичных числовых полей с четным дискриминантом и классом номер 1,2 и 3, и распространено на случай нечетного дискриминанта. Иногда называемый проблемой номера класса, этот более общий вопрос был в конечном итоге подтвержден в 1986 году (конкретный вопрос, заданный Гауссом, был подтвержден Ландау в 1902 году для класса номер один). В разделе VII статьи 358 Гаусс доказал то, что можно интерпретировать как первый нетривиальный случай гипотезы Римана для кривых над конечными полями (теорема Хассе-Вейля).
Цель работы: рассмотреть теорию и применение первообразных корней.
Задачи:
1. Теоретические аспекты первообразных корней
1.1. Определение первообразных корней и гипотеза Артина
В модулярной арифметике, ветви теории чисел, число g является примитивным корнем по модулю n, если каждое число a копроме к n конгруэнтно степени g по модулю n . То есть g-примитивный корень mod n , если для каждого целого числа a coprime N существует целое число k такое, что g k ≡ a (mod n ). Такое значение k называется индексом или дискретным логарифмом от a до основания g по модулю n . Заметим, что g является корнем примитива mod n тогда и только тогда, когда g является генератором мультипликативной группы целых чисел по модулю n .
Гаусс определил примитивные корни в статье 57 Disquisitiones Arithmeticae (1801), где он приписал Эйлеру придумывание термина. В статье 56 он заявил, что Ламберт и Эйлер знали о них, но он был первым, кто строго продемонстрировал, что примитивные корни существуют для простого n . На самом деле, Disquisitiones содержит два доказательства: одно в статье 54 является неконструктивным доказательством существования, в то время как другое в статье 55 является конструктивным.
Число 3 является корнем-примитивом по модулю 7, поскольку

Если п - положительное целое число, целые числа между 0 и Н − 1, которые взаимно просты С П (или эквивалентно, конгруэнтность классов, взаимно простых С П) образуют группу с умножением по модулю п , как операция; она обозначается зн× а называется группировка единиц по модулю П или группы примитивных классов по модулю Н. мультипликативная группа целых чисел по модулю n, Эта группа является циклической тогда и только тогда, когда n равно 2, 4 , p k или 2p k, где p k-степень нечетного простого числа. Генератор этой циклической группы называется корнем примитива по модулю n, или элемент примитива Zn × .
Порядок (т.е. количество элементов в) Zn × задается функцией Эйлера φ (n) (последовательность A000010 в OEIS). Теорема Эйлера говорит, что φ ( n ) ≡ 1 (mod n) для каждого a копроме к n; наименьшая степень A, которая конгруэнт к 1 по модулю n называется мультипликативным порядком по модулю n. В частности, чтобы a был примитивным корнем по модулю n, φ(n) должна быть наименьшей степенью a, которая конгруэнтна 1 по модулю n.
Числа, имеющие примитивный корень
1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149, ... (последовательность A033948 в OEIS)
В отличие от большинства современных авторов Гаусс не всегда выбирал самый маленький примитивный корень. Вместо этого он выбрал 10, если это примитивный корень; если это не так, он выбрал тот корень, который дает 10 наименьший индекс, и, если есть более одного, выбрал наименьший из них. Это не только упрощает вычисления вручную, но и используется в § VI, где исследуются периодические десятичные разложения рациональных чисел.
Строки таблицы помечены начальными степенями (за исключением 2, 4 и 8) меньше 100; второй столбец является корнем-примитивом по модулю этого числа. Столбцы помечены простыми числами менее 100. Запись в строке p, столбце q является индексом q по модулю p для данного корня.
Например, в строке 11 в качестве корня-примитива задано 2, а в столбце 5-4. Это означает, что 2 4 = 16 ≡ 5 (mod 11).
Для индекса составного числа добавьте индексы его простых коэффициентов.
Например, в строке 11 индекс 6 представляет собой сумму индексов для 2 и 3: 2 1 + 8 = 512 ≡ 6 (mod 11). Индекс 25 в два раза больше индекса 5: 2 8 = 256 ≡ 25 (mod 11) . (Конечно, с 25 ≡ 3 (mod 11), запись для 3 8).
Таблица прямо вперед для нечетных простых степеней. Но степени 2 (16, 32 и 64) не имеют примитивных корней; вместо этого, степени 5 составляют одну половину нечетных чисел меньше, чем степень 2, и их отрицательные по модулю степени 2 составляют другую половину. Все степени 5 ≡ 5 или 1 (mod 8); столбцы, возглавляемые числами ≡ 3 или 7 (mod 8), содержат индекс его отрицательного значения. (Последовательность A185189 и A185268 в OEIS)
Например, по модулю 32 индекс для 7 равен 2, а 5 2 = 25 ≡ -7 (mod 32), но запись для 17 равна 4, а 5 4 = 625 ≡ 17 (mod 32).
В теории чисел гипотеза Артина о примитивных корнях утверждает, что заданное целое число a, которое не является ни совершенным квадратом, ни -1, является примитивным корнем по модулю бесконечного числа простых чисел p . Гипотеза также приписывает асимптотическую плотность этим простым числам. Эта гипотетическая плотность равна константе Артина или ее рациональному кратному.
Предположение было сделано Эмилем Артином Гельмуту Хассе 27 сентября 1927 года, согласно дневнику последнего. Гипотеза по-прежнему не решена по состоянию на 2012 год. На самом деле, нет ни одного значения a, для которого гипотеза Артина доказана.
Формулировка гипотезы
Пусть a-целое число, которое не является совершенным квадратом и не -1. Напишите a = a 0 b 2 без квадрата. Обозначим через S ( a ) множество простых чисел p такое, что A-примитивный корень по модулю p . Тогда гипотеза состояния S (a) имеет положительную асимптотическую плотность внутри множества простых чисел. В частности, S (a ) бесконечно.
В условиях, что a не является совершенной степенью и что a 0 не конгруэнтно 1 по модулю 4 (последовательность A085397 в OEIS ), эта плотность не зависит от a и равна константе Артина, которая может быть выражена как бесконечное произведение
, (1)
(последовательность A005596 в OEIS).
Подобные гипотетические формулы продукта существует для плотности, когда a не удовлетворяет вышеуказанным условиям. В этих случаях предполагаемая плотность всегда является рациональным кратным C Artin.
Например, возьмем a = 2. Гипотеза утверждает, что множество простых чисел p, для которых 2 является примитивным корнем, имеет вышеуказанную плотность C Artin . Множество таких простых чисел является (последовательность A001122 в OEIS)
S(2) = {3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, ...}.
СПИСОК ЛИТЕРАТУРЫ
2. Акушерство И. Я., Юдицкий Д. И. машинная арифметика в остаточных классах / И. Я. Акушерство - М.: Советское радио, 1968. 429 с.
3. Бухстаб А. А. Теория чисел / А. А. Бухстаб – М.: Просвещение, 1966. – 379 с.
4. Van Der Warden B. L. Алгебра / Ван Дер Уорден-М.: Наука, 1986. – 624 с.
5. Виноградов И. М. Основы теории чисел / И. М. Виноградов – М.: Наука, 1972. – 167 с.
6. Воеводин В. В. линейная алгебра / В. В. Воеводин – М.: Наука, 1980. – 400 С.
7. Калужнин Л. А. Введение в общую алгебру / Л. А. Калужин – М.: Наука, 1973. – 239 с.
8. Кострикин А. И. введение в алгебру / А. И. Кострикин – М.: Наука, 1979. – 495 с.
9. Куликов В. В. Алгебра и теория чисел / В. В. Куликов – М.: Наука, 1980. – 400 с.
10. Курош А. Г. Курс высшей алгебры / А. Г. Курош – М.: Наука, 1976. – 431 с.
11. Ленг С. Алгебра / С. Ленг-М.: Мир, 1968. – 564 С.
12. Скорняков Л. А. элементы алгебры / Л. А. Скорняков – М.: Наука, 1986. – 239 с.
13. Элементарное введение в абстрактную алгебру / E. Fried-M.: мир, 1972. 260 с.