Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

и

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

Где \phi(m)функция Эйлера.

Иначе говоря, первообразный корень — порождающая мультипликативной группы кольца вычетов по модулю m.

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

g^{\ell} \equiv a \mod m.

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

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

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

ИсторияПравить

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

Пример Править

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

3^0 \equiv 1\ \pmod 7
3^1 \equiv 3\ \pmod 7
3^2 \equiv 2\ \pmod 7
3^3 \equiv 6\ \pmod 7
3^4 \equiv 4\ \pmod 7
3^5 \equiv 5\ \pmod 7

Примеры наименьших первообразных корней по модулю m:

m 2 3 4 5 6 7 8 9 10 11 12
первообразный корнь mod m 1 2 3 2 5 3 -- 2 3 2 --
hu:Primitív gyökpl:Pierwiastek pierwotny

ta:ஏது மூலம், மாடுலோ p vi:Căn nguyên thủy modulo n

Викия-сеть

Случайная вики