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

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

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

та

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

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

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

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

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

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

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

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

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