Першаісны корань (тэорыя лікаў)

Першаі́сны корань па модулю m ― цэлы лік g такі, што

$g^{\varphi (m)}\equiv 1{\pmod {m}}$

і

$g^{\ell }\not \equiv 1{\pmod {m}}$ пры $1\leq \ell <\varphi (m),$

дзе $\varphi (m)$ ― функцыя Эйлера.

Іншымі словамі, першаісны корань — гэта ўтваральны элемент мультыплікатыўнай групы колца вылікаў па модулю m.

Уласцівасці

Існаванне

Першаісныя карані існуюць толькі па модулях m віду

m = 2, 4, p^a, 2p^a,

дзе p > 2 ― просты лік. Толькі ў гэтых выпадках мультыплікатыўная група колца вылікаў па модулю m з'яўляецца цыклічнаю групаю парадку φ(m).

Індэкс ліку па модулю

Для першаіснага кораня g яго ступені g⁰=1, g, …, g^φ(m)-1 непараўнальныя паміж сабою па модулю m і ўтвараюць прыведзеную сістэму рэшт па модулю m. Таму для кожнага ліку a, узаемна простага з m, знойдзецца паказчык ℓ, 0 ⩽ ℓ ⩽ φ(m)-1, такі што

$g^{\ell }\equiv a{\pmod {m}}.$

Такі лік ℓ называецца індэксам ліку a па аснове g.

Колькасць

Калі па модулю m існуе першаісны корань g, то ўсяго існуе φ(φ(m)) розных першаісных каранёў па модулю m, прычым усе іх можна атрымаць як g^k, дзе 1 ⩽ k ⩽ φ(m)-1 і лік k узаемна просты з φ(m).

Гісторыя

Першаісныя карані для простых модуляў p былі ўведзены Эйлерам, але існаванне першаісных каранёў для любых простых модуляў p даказаў толькі Гаус у 1801 годзе.

Прыклады

Лік 3 з'яўляецца першаісных коранем па модулю 7. Каб пераканацца ў гэтым, дастаткова кожны лік ад 1 да 6 прадставіць як некаторую ступень тройкі па модулю 7:

$3^{0}\equiv 1\ {\pmod {7}}$

$3^{1}\equiv 3\ {\pmod {7}}$

$3^{2}\equiv 2\ {\pmod {7}}$

$3^{3}\equiv 6\ {\pmod {7}}$

$3^{4}\equiv 4\ {\pmod {7}}$

$3^{5}\equiv 5\ {\pmod {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

Гл. таксама

• Дыскрэтнае лагарыфмаванне
• Паказчык ліку па модулю
• Гіпотэза Арціна

Літаратура

• И. М. Виноградов. Основы теории чисел.. — М.: Наука, 1972.

Спасылкі

• «Першаісныя карані» на сайце MAXimal (руск.)
• Weisstein, Eric W.. Primitive Root (нявызн.). MathWorld.