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

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

$g^{\phi (m)}\equiv 1(\mathrm{mod}m)$

і

$g^{\ell }\equiv ̸1(\mathrm{mod}m)$ пры $1\le \ell <\phi (m),$

дзе $\phi (m)$ ― Шаблон:Нп3.

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

Уласцівасці

Існаванне

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

Шаблон:Math = 2, 4, Шаблон:Math, Шаблон:Math,

дзе Шаблон:Math ― просты лік. Толькі ў гэтых выпадках Шаблон:Нп3 па модулю Шаблон:Math з'яўляецца цыклічнаю групаю парадку Шаблон:Math.

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

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

$g^{\ell }\equiv a(\mathrm{mod}m).$

Такі лік ℓ называецца [[індэкс ліку па модулю|індэксам ліку Шаблон:Math па аснове g]].

Колькасць

Калі па модулю Шаблон:Math існуе першаісны корань g, то ўсяго існуе Шаблон:Math розных першаісных каранёў па модулю Шаблон:Math, прычым усе іх можна атрымаць як g^k, дзе Шаблон:Math і лік Шаблон:Math узаемна просты з Шаблон:Math.

Гісторыя

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

Прыклады

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

$3^0\equiv 1(\mathrm{mod}7)$

$3^1\equiv 3(\mathrm{mod}7)$

$3^2\equiv 2(\mathrm{mod}7)$

$3^3\equiv 6(\mathrm{mod}7)$

$3^4\equiv 4(\mathrm{mod}7)$

$3^5\equiv 5(\mathrm{mod}7)$

Прыклады найменшых першаісных каранёў па модулю Шаблон:Math (Шаблон:OEIS):

Модуль Шаблон:Math	2	3	4	5	6	7	8	9	10	11	12	13	14
Першаісны корань	1	2	3	2	5	3	—	2	3	2	—	2	3

Гл. таксама

• Шаблон:Нп3
• Шаблон:Нп3
• Шаблон:Нп3

Літаратура

• Шаблон:Кніга

Спасылкі

• «Першаісныя карані» на сайце MAXimal Шаблон:Ref-ru
• Шаблон:MathWorld