Першаісны корань (тэорыя лікаў)
Першаі́сны корань па модулю m ― цэлы лік g такі, што
і
- пры
дзе ― функцыя Эйлера .
Іншымі словамі, першаісны корань — гэта ўтваральны элемент мультыплікатыўнай групы колца вылікаў па модулю m.
Уласцівасці[правіць | правіць зыходнік]
Існаванне[правіць | правіць зыходнік]
Першаісныя карані існуюць толькі па модулях m віду
- m = 2, 4, pa, 2pa,
дзе p > 2 ― просты лік. Толькі ў гэтых выпадках мультыплікатыўная група колца вылікаў па модулю m з'яўляецца цыклічнаю групаю парадку φ(m).
Індэкс ліку па модулю[правіць | правіць зыходнік]
Для першаіснага кораня g яго ступені g0=1, g, …, gφ(m)-1 непараўнальныя паміж сабою па модулю m і ўтвараюць прыведзеную сістэму рэшт па модулю m. Таму для кожнага ліку a, узаемна простага з m, знойдзецца паказчык ℓ, 0 ⩽ ℓ ⩽ φ(m)-1, такі што
Такі лік ℓ называецца індэксам ліку a па аснове g.
Колькасць[правіць | правіць зыходнік]
Калі па модулю m існуе першаісны корань g, то ўсяго існуе φ(φ(m)) розных першаісных каранёў па модулю m, прычым усе іх можна атрымаць як gk, дзе 1 ⩽ k ⩽ φ(m)-1 і лік k узаемна просты з φ(m).
Гісторыя[правіць | правіць зыходнік]
Першаісныя карані для простых модуляў p былі ўведзены Эйлерам, але існаванне першаісных каранёў для любых простых модуляў p даказаў толькі Гаус у 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 |
Гл. таксама[правіць | правіць зыходнік]
Літаратура[правіць | правіць зыходнік]
- И. М. Виноградов. Основы теории чисел.. — М.: Наука, 1972.
Спасылкі[правіць | правіць зыходнік]
- «Першаісныя карані» на сайце MAXimal (руск.)
- Weisstein, Eric W.. Primitive Root . MathWorld.