Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Первісний корінь (теорія чисел)



План:


Введення

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

g ^ {\ varphi (m)} \ equiv 1 \ pmod m

і

g ^ {\ ell} \ not \ equiv 1 \ pmod m при 1 \ le \ ell <\ varphi (m),

де φ (m) - функція Ейлера. Іншими словами, первісний корінь - це утворюючий елемент мультиплікативної групи кільця відрахувань по модулю m.


1. Властивості

1.1. Існування

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

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

де p> 2 - просте число. Тільки в цих випадках мультиплікативна група кільця відрахувань по модулю m є циклічної групою порядку φ (m).

1.2. Індекс числа по модулю

Для первісної кореня g його ступеня g 0 = 1, g,..., g φ (m) -1 непорівнянні між собою за модулем m і утворюють наведену систему відрахувань по модулю m. Тому для кожного числа a, взаємно простого з m, знайдеться показник ℓ, 0 ⩽ ℓ ⩽ φ (m) -1, такий, що

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

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


1.3. Кількість

Якщо за модулем m існує первісний корінь g, то всього існує φ (φ (m)) різних первісних коренів за модулем m, причому всі їх можна отримати як g k, де 1 ⩽ k ⩽ φ (m) -1 і k взаємно просто з φ (m).

2. Історія

Первісні корені для простих модулів p були введені Ейлером, але існування первісних коренів для будь-яких простих модулів p було доведено лише Гауссом в 1801.

3. Приклади

Число 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 (послідовність A046145 в OEIS):

Модуль m 2 3 4 5 6 7 8 9 10 11 12 13 14
Первісний корінь 1 2 3 2 5 3 - 2 3 2 - 2 3

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Первісний корінь (теорія полів)
Теорія чисел
Характер (теорія чисел)
Композиція (теорія чисел)
Теорема Ейлера (теорія чисел)
Первісний ліс
Корінь
Корінь брінг
Квадратний корінь з 2
© Усі права захищені
написати до нас