Что такое первообразный корень
Первообразный корень
Смотреть что такое «Первообразный корень» в других словарях:
Первообразный корень — Первообразный корень: Первообразный корень (абстрактная алгебра) Первообразный корень (теория чисел) Список значений слова или словосочетан … Википедия
ПЕРВООБРАЗНЫЙ КОРЕНЬ — 1) П. к., примитивный корень, из единицы в поле Кстепени т элемент ноля К такой, что и для любого натурального r Математическая энциклопедия
Первообразный корень (теория чисел) — У этого термина существуют и другие значения, см. Первообразный корень. Первообразный корень по модулю m ― целое число g такое, что и при где ― функция Эйлера. Другими словами, первообразный корень это образующий элемент мультипликативной … Википедия
ИНДЕКС — числа а по модулю т показатель ув сравнении a=gg(mod m), где аи твзаимно просты, а g некоторый фиксированный первообразный корень по модулю т. И. числа апо модулю тобозначается через g=indg а или, более кратко, у=ind а. Первообразные корни… … Математическая энциклопедия
КУММЕРА РАСШИРЕНИЕ — расширение поля kхарактеристики вида где п некоторое натуральное число, причем предполагается, что поле kсодержит первообразный корень из 1 степени п(в частности, пвзаимно просто с рпри ). К. р. названы по имени Э. Куммера (Е. Kummer), впервые… … Математическая энциклопедия
Корни из единицы — Корни пятой степени из единицы (вершины пятиугольника) Корни n й степени из единицы комплексные корни многочлена … Википедия
Индексы (в теории чисел) — Индексы в теории чисел, числа, играющие при решении сравнений роль, аналогичную роли логарифмов при решении показательных уравнений. Если р нечётное простое число, g первообразный корень по модулю р, то И. числа а называется такое число k = ind a … Большая советская энциклопедия
Индексы — I в теории чисел, числа, играющие при решении сравнений (См. Сравнение) роль, аналогичную роли логарифмов при решении показательных уравнений. Если р нечётное простое число, g Первообразный корень по модулю р, то И. числа а называется… … Большая советская энциклопедия
Первообразный корень (теория чисел)
Первообразный корень по модулю m ― целое число g такое, что
при 
где 
― функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю m.
Содержание
Свойства
Существование
Первообразные корни существуют только по модулям m вида
Индекс числа по модулю
Для первообразного корня g его степени g 0 =1, g, …, g φ(m)-1 несравнимы между собой по модулю m и образуют приведенную систему вычетов по модулю m. Поэтому для каждого числа a, взаимно простого с m, найдется показатель ℓ, 0 ⩽ ℓ ⩽ φ(m)-1, такой, что
Количество
История
Первообразные корни для простых модулей 
были введены Эйлером, но существование первообразных корней для любых простых модулей было доказано лишь Гауссом в 1801 году.
Примеры
Число 3 является первообразным корнем по модулю 7. Чтобы в этом убедиться, достаточно каждое число от 1 до 6 представить как некоторую степень тройки по модулю 7:
Примеры наименьших первообразных корней по модулю m (последовательность A046145 в OEIS):
| Модуль m | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Первообразный корень | 1 | 2 | 3 | 2 | 5 | 3 | — | 2 | 3 | 2 | — | 2 | 3 |
См. также
Ссылки
Полезное
Смотреть что такое «Первообразный корень (теория чисел)» в других словарях:
Первообразный корень — Первообразный корень: Первообразный корень (абстрактная алгебра) Первообразный корень (теория чисел) Список значений слова или словосочетан … Википедия
Первообразный корень — по модулю m, такое число g, что положительное наименьшее число k, для которого разность gk 1 делится на m (gk сравнимо с 1 по модулю m), совпадает c φ(m), где φ(m) число натуральных чисел, меньших m и взаимно простых с m. Например, при m … Большая советская энциклопедия
МОДУЛЕЙ ТЕОРИЯ — теория, изучающая непрерывные семейства объектов алгебраич. геометрии. Пусть А класс объектов алгебраич. геометрии (многообразий, схем, векторных расслоений и т. п.), на к ром задано нек рое отношение эквивалентности R. Основная задача… … Математическая энциклопедия
Эйлер, Леонард — В Википедии есть статьи о других людях с такой фамилией, см. Эйлер. Леонард Эйлер Leonhard Euler … Википедия
Л. Эйлер — Леонард Эйлер Leonhard Euler Портрет 1756 года, выполненный Эмануэлем Хандманном Дата рождения: 4 (15) апреля 1707 Место рождения: Базель, Швейцария Дата смерти: 7 (18) сентября … Википедия
Эйлер Леонард — Леонард Эйлер Leonhard Euler Портрет 1756 года, выполненный Эмануэлем Хандманном Дата рождения: 4 (15) апреля 1707 Место рождения: Базель, Швейцария Дата смерти: 7 (18) сентября … Википедия
Эйлер Л. — Леонард Эйлер Leonhard Euler Портрет 1756 года, выполненный Эмануэлем Хандманном Дата рождения: 4 (15) апреля 1707 Место рождения: Базель, Швейцария Дата смерти: 7 (18) сентября … Википедия
КУММЕРА РАСШИРЕНИЕ — расширение поля kхарактеристики вида где п некоторое натуральное число, причем предполагается, что поле kсодержит первообразный корень из 1 степени п(в частности, пвзаимно просто с рпри ). К. р. названы по имени Э. Куммера (Е. Kummer), впервые… … Математическая энциклопедия
СРАВНЕНИЕ — соотношение между целыми числами а и и вида a=b+mk, означающее, что их разность а b делится на заданное целое положительное число т, наз. модулем сравнения; при этом аназ. вычетом целого числа bпо модулю т. Для выражения сравнимости чисел аи bпо… … Математическая энциклопедия
ДИРИХЛЕ ХАРАКТЕР — (mod k) функция c(п)=c(п; k )на множестве целых чисел, удовлетворяющая условиям: Иными словами, Д. х. (mod k) это арифметич. функции, к рые не равны тождественно нулю, вполне мультипликативны и периодичны с периодом k. Понятие Д. х. ввел П.… … Математическая энциклопедия
Национальная библиотека им. Н. Э. Баумана
Bauman National Library
Персональные инструменты
Первообразный корень (теория чисел)
\forall \sigma |(p-1)> является показателем для φ ( σ ) <\displaystyle
\varphi (\sigma )> классов вычетов. В частности, ∃ φ ( p − 1 ) <\displaystyle
\exists \varphi (p-1)> класс первообразных корней ( p − 1 ) | ( p − 1 ) <\displaystyle
ψ ( σ 1 ) + ψ ( σ 2 ) + … + ψ ( σ k ) = p − 1 <\displaystyle
\forall > из них принадлежит какому-либо показателю.
С другой стороны φ ( σ 1 ) + φ ( σ 2 ) + … + φ ( σ k ) = p − 1 <\displaystyle
\varphi (\sigma _<1>)+\varphi (\sigma _<2>)+\ldots +\varphi (\sigma _
ψ ( σ 1 ) + ψ ( σ 2 ) + … + ψ ( σ k ) = φ ( σ 1 ) + φ ( σ 2 ) + … + φ ( σ k ) <\displaystyle
\psi (\sigma _<1>)+\psi (\sigma _<2>)+\ldots +\psi (\sigma _
Докажем, что ∃ φ ( p − 1 ) <\displaystyle
\exists \varphi (p-1)> первообразных корней. Для всех значений m ∃ <\displaystyle
\exists > первообразные корни
m=2,4,p^<\alpha >,2p^<\alpha >\ldots \quad \alpha \geq 1> Кроме того, для любого из этих чисел существует φ ( φ ( m ) ) <\displaystyle
\varphi (\varphi (m))> первообразных корней
m=p:\quad \varphi (\varphi (p))=\varphi (p-1)(g)=\mathbb
\to > первообразные корни совпадают с элементами группы
Нахождение хотя бы одного первообразного корня
Число первообразных корней : φ ( p − 1 ) = φ ( 2 q ) = φ ( 2 ) φ ( q ) = q − 1 <\displaystyle
\varphi (p-1)=\varphi (2q)=\varphi (2)\varphi (q)=q-1>
q = p − 1 2 ⇒ φ ( q ) = q − 1 = p − 3 2 <\displaystyle
\sim > 1/2 (половина всех элементов группы)
\forall g\in \mathbb
(1)\qquad (g)=\mathbb
( 2 ) g m − 1 ≡ 1 ( m o d m ) ∀ p | ( m − 1 ) <\displaystyle
(2)\qquad g^
(1)\Rightarrow (2)\qquad > Если ( g ) ∈ Z m ∗ ⇒ o r d q = φ ( m ) = m − 1 ⇒ <\displaystyle
(g)\in \mathbb
q=\varphi (m)=m-1\Rightarrow > не может быть g ( m − 1 ) | p = 1 ( m o d m ) → g ( m − 1 ) | p ≢ 1 ( m o d m ) <\displaystyle
m)\to g^<(m-1)|p>\not \equiv 1(mod
(2)\Rightarrow (1)> Если бы σ = o r d g m − 1 <\displaystyle
Тогда g m − 1 p = g σ ⋅ u = ( g σ ) u = 1 ⇒ <\displaystyle
Таким образом, надо знать разложение числа (m-1) на множители.
2 гипотезы Артина(Artin)
?\qquad p> 2 вариант: По фиксированному элементу g определить простые p, для которых он будет первообразным по модулю p.
\pi (n)-> число простых p n <\displaystyle
|
