Первообразный корень (теория чисел)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:27, 27 марта 2015.
TemplateDifinitionIcon.svg Определение «Первообразный корень»
Первообразный корень - корень, который имеет порядок
TemplateTheoremIcon.svg Теорема Утверждение
Для простого p любой делитель является показателем для классов вычетов. В частности, класс первообразных корней
Доказательство
Пусть - все делители числа (p-1). Тогда можем записать:

.

Всего классов (p-1), из них принадлежит какому-либо показателю.

С другой стороны (из свойства )

По лемме: из или \varphi(\sigma - 1)</math> если хотя бы 1 равен нулю, то равенство не выполняется. Таким образом, .

Докажем, что первообразных корней. Для всех значений m первообразные корни


TemplateTheoremIcon.svg Теорема Теорема (Гаусса)
Первообразные корни существуют только для чисел вида Кроме того, для любого из этих чисел существует первообразных корней
Доказательство
При порождает всю мультипликативную группу первообразные корни совпадают с элементами группы


TemplateTheoremIcon.svg Теорема Теорема
Группа кольца вычетов является циклической тогда и только тогда, когда . в остальных случаях группа не циклическая
Доказательство
Без доказательства


TemplateLemmaIcon.svg Лемма «Утверждение»
Если g- первообразный корень по модулю m, то все остальные первообразные корни имеют , в том числе


TemplateLemmaIcon.svg Лемма «Утверждение»
Если g является первообразным корнем по mod p, и , то g-первообразный и по


Нахождение хотя бы одного первообразного корня

Замечание: Часто р ищут в следующем виде:  простые.

Число первообразных корней :

Если p - огромно, то количество первообразных корней 1/2 (половина всех элементов группы)

TemplateLemmaIcon.svg Лемма «Утверждение (Чебышев П.Л.)»
  1. Если , то 2 является первообразным корнем по модулю
  2. Если , то -2 является первообразным корнем


Замечание: Тест Люка(Lucas) для простых чисел. Следующие утверждения эквивалентны:
1 m - простое
2

{детерминированный (невероятностный тест на простоту}
TemplateTheoremIcon.svg Теорема Утверждение
Для простого эквивалентны утверждения:

(является первообразным корнем)

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

Если не может быть

Если бы , то тогда (p - некоторое простое число)

Тогда противоречие с (2)


Таким образом, надо знать разложение числа (m-1) на множители.

2 гипотезы Артина(Artin)

1 вариант: 2 вариант: По фиксированному элементу g определить простые p, для которых он будет первообразным по модулю p.

- число простых ,math>~ p \leq n</math>, в том числе g - первообразный корень по модулю p.

число простых .

Таблица 1
g
2 470 0.356
3 476 0.387
5 492 0.480
6 470 0.382
7 465 0.378
TemplateLemmaIcon.svg Лемма «Гипотеза 1»
и не являющегося полным квадратом является первообразным для бесконечного числа простых чисел


TemplateLemmaIcon.svg Лемма «Гипотеза 2»
удовлетворяет соотношению:


TemplateLemmaIcon.svg Лемма «Утверждение (Keaines, 1984)»
Для любых целых положительных m существует бесконечно много простых p, в том чисте первообразный корень заключен в границах


TemplateLemmaIcon.svg Лемма «Утверждение (Burges, 1962)»
Наименьший первообразный корень