Арифметичні застосування теорії конгруенцій (стр. 6 из 6)

Теорема 2. Нехай g-непарний первісний корінь по модулю

; тоді кожен індекс числа а по модулю і основою g є індексом а по модулю і основою g. Теорема 3. При два числа вигляду і порівнянні по модулю тоді і тільки тоді, коли

і .

Теорема 4. При

будь-яке непарне число порівнянне по модулю з одним і тільки одним числом з множини:

.

Означення 3. Індексом непарного числа а по модулю

при називається пара чисел , де , така, що

.

Таку пару ( (u, v)) інколи записуватимемо також у вигляді ind a.

Приклад. Пара ( (0, 0)) є індексом 1 по будь-якому модулю

. Дійсно: .

Означення 4. Дві пари:

і - називаються порівнянними по подвійному модулю , якщо

.

Порівнянність пар:

і - по подвійному модулю записуватимемо у вигляді:

.

Очевидно, що дві пари, порівнянні по подвійному модулю з однією і тією ж третьою, порівнянні між собою.

Теорема 5. При

тоді і тільки тоді, коли індекс а порівнянний з індексом b пo подвійному модулю .

Означення 5. Сумою індексів

називається індекс .

Теорема 6. При

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

Маючи таблицю індексів по модулю

, щоб знайти остачу від ділення на , де всі взаємно прості з , ми шукану остачу позначаємо через і записуємо

.

Індексуючи попереднє рівняння отримуємо:

.

Знаходимо в таблиці індексів

, так що

,

Звідси

.

В частинному випадку, якщо

, ми отримуємо прийом для обчислення остачі від ділення на модуль степеня .

Приклад. Користуючись таблицею індексів, знайти остачу від ділення на 61 числа

.

.

У таблицях по модулю 61 з підставою g=59 або g=-2 знаходимо

і , так що

.

За значенням індексу знаходимо х. Число 24 є індексом 20, так що

.

Якщо

, то для знаходження остачі від ділення на добутку або степеня знаходимо остачі при діленні на модулі потім розв′язуємо систему рівнянь:

При

, остача від ділення на знаходимо іншими методами (без вживання теорії індексів) або розглядаємо індекси по модулю .

При

ми можемо представити у вигляді і знаходимо за допомогою індексів остачі від ділення на .

Приклад. Знайти остачу від ділення на 1242 числа

.

Знаходимо остачу

від ділення по модулю 27 з основою знаходимо

.

так що

.

По модулю 27 знаходимо, що

, так що

.

Знаходимо остачу

від ділення на 23.

Розв’язуючи систему

, знаходимо . Остача рівна 127.

Висновки

Дана курсова робота стосується теорії конгруенцій, зокрема застосуванню конгруенцій: ознаки подільності, перевірка арифметичних дій, перетворення десяткового дробу у звичайний, індекси.