Первообразный корень (теория чисел)

Материал из Википедии — свободной энциклопедии

Первообразный корень по модулю $m$ ― целое число $g$ такое, что

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

и

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

где $φ(m)$ ― функция Эйлера. Другими словами, первообразный корень — это образующий элемент мультипликативной группы кольца вычетов по модулю $m$ .

Для первообразного корня $g$ его степени $g 0 = 1, g,..., g φ(m) - 1$ несравнимы между собой по модулю $m$ и образуют приведенную систему вычетов по модулю $m$ . Таким образом, для каждого числа $a$ , взаимно простого с $m$ , найдется показатель $\ell$ ( $0\le\ell\le\phi(m)-1$ ), для которого

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

При этом число $\ell$ называется индексом числа a по модулю m.

Первообразные корни существуют не для всех модулей, а только для модулей $m$ вида

m = 2,4, p a,2 p a,

где $p > 2$ ― простое число. В этих случаях мультипликативные группы приведенных классов вычетов по модулю $m$ устроены наиболее просто: они являются циклическими группами порядка $φ(m)$ .

[править] История

Первообразные корни для простых модулей $p$ были введены Эйлером, но существование первообразных корней для любых простых модулей $p$ было доказано лишь Гауссом в 1801.

[править] Пример

Проверим, является ли число 3 первообразным корнем по модулю 7. Если это так, то каждое число от 1 до 6 должно быть представлено остатком от деления некоторой степени тройки на 7, действительно, перебором убеждаемся:

$3^0 \equiv 1\ \pmod 7$