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

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

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

та

$g^{\ell }\equiv ̸1modm$ при $1\le \ell \le \varphi (m)-1,$

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

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

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

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

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

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

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

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

Література

• Шаблон:Ван.дер.Варден.Алгебра
• Шаблон:Ленг.Алгебра