Первісний корінь

Пе́рвісний ко́рінь за модулем $\ m$ ― ціле число $\ g$ таке, що

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

та

$g^{\ell }\not \equiv 1\mod m$ при $1\leq \ell \leq \phi (m)-1,$

де $\ \phi (m)$ ― функція Ейлера. Іншими словами, первісний корінь — це породжуючий елемент мультиплікативної групи кільця лишків за модулем $\ m$.

Для первісного кореня $\ g$ його степені $\ g^{0}=1,g,\ldots ,g^{\phi (m)-1}$ непорівнювані між собою за модулем $m$ і породжують приведену систему лишків за модулем $m$.

Тому для кожного числа $\ a$, взаємно простого з $\ m$, знайдеться показник $\ell$ ($0\leq \ell \leq \phi (m)-1$) такий, що

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

Таке число $\ell$ називається індексом числа $\ a$ за основою $\ g$.

Первісні корені існують не для всіх модулів, а тільки для модулів $\ m$ виду

$\ m=2,4,p^{a},2p^{a},$

де $p>2$ ― просте число. Тільки в цих випадках мультиплікативна група кільця лишків за модулем $\ m$ є циклічною групою порядку $\ \phi (m)$.

Література

• Ван дер Варден Б. Л. Алгебра. — Москва : Наука, 1975. — 623 с. — ISBN 5-8114-0552-9.(рос.)
• Ленг С. Алгебра. — Москва : Мир, 1968. — 564 с. — ISBN 5458320840.(рос.)