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

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

та

при

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

Для первісного кореня його степені непорівнювані між собою за модулем і породжують приведену систему лишків за модулем .

Тому для кожного числа , взаємно простого з , знайдеться показник () такий, що

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

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

де просте число. Тільки в цих випадках мультиплікативна група кільця лишків за модулем є циклічною групою порядку .

Література

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.