Існування їх та кількість за простим модулем

Основні теоретичні відомості

Порядок числа і класу лишків за модулем. Первісні корені,

Нехай , і . Порядком числа а за модулем називається таке найменше натуральне число , що . Число позначають ще як і називають показником, до якого належить число за модулем . Оскільки за теоремою Ейлера , то число завжди існує і . Якщо , то число називають первісним коренем за модулем .

Якщо , то . Ця властивість дає змогу казати про порядок класу лишків, а саме: клас лишків має порядок за модулем . якщо порядок його представника за цим самим модулем дорівнює .

Якщо , то клас лишків називається класом первісних коренів за модулем .

Якщо , то числа попарно не конгруентні між собою за модулем .

Якщо — первісний корінь за модулем , тобто , то числа утворюють зведену систему лишків за модулем .

Якщо , то тоді і тільки тоді, коли . Зокрема, тоді і тільки тоді, коли .

Якщо і , то

Якщо , то .

Якщо , то .

Якщо , то .

Якщо - попарно взаємно прості числа, то . тоді і тільки тоді, коли .

.

Якщо , то класи лишків є різними розв'яз­ками конгруенції .

Якщо — просте число, то зазначені класи лишків вичерпують усі розв'язки даної конгруенції.

За простим модулем кожен дільник числа є порядком для класів лишків. Зокрема, існує класів первісних коренів (теорема Гаусса).

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

Якщо — канонічний розклад числа , то число тоді і тільки тоді є первісним коренем за простим модулем ,коли

для всіх .

Первісні корені існують тільки за модулями ; і , де - просте непарне число, а .

Нехай —первісний корінь за простим модулем . Тоді можна знайти таке число , що число , яке визначається з умови

,

не ділиться на . Відповідне число є первісним коренем за модулем при будь-якому .

Нехай і — первісний корінь за модулем .Непарне з чисел і є також первісним коренем за модулем .

Якщо і - різні прості дільники числа ,то число ,взаємно просте з ,тоді і тільки тоді є первісним коренем за модулем ;коли

для всіх .

Індекси за простим модулем. Двочленні конгруенції за простим модулем; таблиці індексів і застосування їх.

Нехай - первісний корінь за простим модулем , і . Ціле невід’ємне число називається індексом за модулем при основі , якщо

(1)

Взагалі, довільне значення , яке задовольняє конгруенцію

, (2)

називається індексом числа за модулем при основі і позначається

. (3)

При цьому може бути й складним числом, проте

.

Означення індексу можна записати ще так:

. (4)

Користуючись цим означенням, складають таблицю Індексів за даною основою і модулем. Таблиці індексів за кожним простим модулем (не дуже великим) містять дві таблиці: одна — знаходження індексу за числом, а друга — знаходження числа за індексом (таблиця анти індексів).

Дата добавления: 2017-02-01