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

Курсова робота АРИФМЕТИЧНІ ЗАСТОСУВАННЯ ТЕОРІЇ КОНГРУЕНЦІЙ

Зміст

• Вступ
• 1. Конгруенції та їх основні властивості
• 2. Ознаки подільності
• 3. Перевірка арифметичних дій
• 4. Визначення члена цифр періоду при перетворенні звичайного дробу в десятковий
• 5. Індекси. Загальні властивості
• Висновки

Вступ

Важливе місце в курсі теорії чисел посідають конгруенції та, зокрема, застосування конгруенцій. Цим питанням займалися такі видатні вчені як, Ейлер, Ферма, Б. Паскаль.

П'єр Ферма (1601−1665) — відомий свого часу юрист і радник судового парламенту в Тулузі - інтенсивно і з великим успіхом займався різними математичними питаннями. П. Ферма є одним з творців диференціального числення і теорії ймовірності, але особливо велике значення мають його роботи по теорії чисел. Більшість теоретико-числових результатів П. Ферма записувалися ним на полях екземпляра твору Діофанта «Арифметика»; Ферма зазвичай не записував доведення, а давав тільки короткі вказівки про метод, який він застосовував для отримання свого результату. Твір Ферма під назвою «Opera Varia» були видані вперше в 1679 р.

Теорема Ферма, викладена в цій главі, була висловлена в одному з листів, посланому їм в 1640 р. Френіклу. У цьому листі Ферма пише, що він отримав доведення цієї теореми; проте саме доведення не було ним опубліковане.

Перше з відомих доведень теореми Ферма належить Лейбніцу (1646−1716). Доведення Лейбніца було засноване на розгляді порівняння:

.

Ейлер дав декілька різних доведень теореми Ферма, з яких перше відноситься до 1736 р. У 1760 р. Ейлер узагальнив теорему, надавши їй вигляду теореми 120, що носить його ім'я. Треба при цьому мати на увазі, що термінологія і позначення у Ферма і у Ейлера абсолютно відмінні від сучасних.

Блез Паскаль (1623−1662) — видатний французький математик, фізик і філософ. Математичні інтереси Паскаля дуже різноманітні: він зробив істотний внесок у розвиток аналізу нескінченно малих; разом з Ферма Паскаль є основоположником теорії ймовірностей; йому належать загальна ознака подільності будь-якого цілого числа на будь-яке інше ціле число, яка ґрунтується на знанні суми цифр числа, а також спосіб обчислення біноміальних коефіцієнтів («Арифметичний трикутник ?); він вперше точно визначив і застосував для доведення метод повної математичної індукції

Дана курсова робота складається з 5 параграфів:

1. Конгруенції та їх основні властивості: вводяться означення конгруенції, основні властивості, основні теоремами в теорії конгруенцій — Ейлера і Ферма.

2. Ознаки подільності. В цьому параграфі розглядаються основні ознаки подільності цілих чисел, при використанні конгруенцій; метод Паскаля — загальна ознака подільності будь-якого цілого числа на будь-яке інше ціле число.

3. Перевірка арифметичних дій. В даному параграфі наведено два способи перевірки арифметичних дій: «перевірки за допомогою дев’ятки», «перевірки за допомогою одинадцяти» .

4. Визначення члена цифр періоду при перетворенні звичайного дробу в десятковий. Використовуючи конгруенції можна перетворити десятковий дріб у звичайний і визначити період даного дробу.

5. Індекси. В цьому параграфі розглядають основні властивості індексів, їх загальна характеристика. Індекси по простому і складеному модулю розглядаються в окремих підпунктах.

Кожен параграф проілюстровано прикладами.

1. Конгруенції та їх основні властивості

Припустимо, що т є натуральне число; розглядатимемо цілі числа у зв’язку з остачами від ділення їх на це натуральне яке називають модулем. Згідно з теоремою про ділення з остачею кожному числу, а відповідатиме певна остача і від ділення, а на т:

.

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

(1)

читається: а конгруентне з за модулем т.

Деякі автори позначають це коротше:

(1')

Співвідношення (1) [або (1')] між числами називають конгруенцією, або порівнянням.

Приклади.;; .

Теорема 1. Конгруентність чисел і за модулем рівнозначна:

а) можливості подати, а у формі, де — ціле;

б) подільності - на .

Властивості:

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

a) ;

б) з конгруенції випливає, що ;

в) якщо і, то .

2. Конгруенції за одним і тим самим модулем можна почленно додавати (або віднімати).

Висновок 1. Доданок, що стоїть у якій-небудь частині конгруенції, можна переносити в іншу частину, змінивши знак на протилежний.

Висновок 2. Можна додати до обох частин або відняти від обох частин конгруенції одне й те саме число.

Висновок 3. До кожної частини конгруенції можна додати (або відняти від неї) довільне число, кратне модулю.

3. Конгруенції за одним і тим самим модулем можна почленно перемножати.

Висновок 1. Обидві частини конгруенції можна помножити на одне й те саме ціле число.

Висновок 2. Обидві частини конгруенції можна підносити до одного й того самого цілого невід'ємного степеня, тобто якщо., то, де — ціле.

4. Обидві частини конгруенції можна поділити на їхній спільний дільник, якщо він взаємно простий з модулем.

5. Обидві частини конгруенції і модуль можна помножити на одне й те саме натуральне число.

6. Обидві частини конгруенції і модуль можна поділити на будь-який їхній спільний дільник.

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

теорія конгруенція ейлер ферм

8. Якщо конгруенція має місце за модулем, то вона матиме місце і за будь-яким дільником цього модуля.

9. Якщо одна частина конгруенції і модуль діляться на яке-небудь ціле число, то і друга частина конгруенції ділиться на це число.

10. Числа і, конгруентні між собою за модулем, мають з ним один і той самий найбільший спільний дільник.

Візьмемо деяке натуральне число, взаємно просте з модулем, розглянемо послідовні степені:. Всі числа цієї нескінченної множини розподілені в класах, отже, принаймні один з цих класів повинен містити нескінченну множину степенів. Узявши з цього класу два степені і позначивши їх і, де, матимемо. Оскільки з слідує, то. Таким чином, для деякого маємо, причому оскільки то. Тоді і при будь-якому натуральному матимемо, що доводить існування нескінченної множини степенів, що належать класу .

П. Ферма для простого модуля, а Л. Ейлеру для будь-якого модуля вдалося вказати значення, при яких має місце рівність. Відповідні теореми, ми їх називатимемо теоремами Ферма — Ейлера, є основою всієї теорії порівнянь і широко використовуються як в теоретичних дослідженнях, так і в арифметичних застосуваннях.

Теорема Ферма. Для будь-якого простого і будь-якого, що не ділиться на, справедливе порівняння

.

Теорема Ейлера. Для будь-якого модуля і будь-якого, взаємно простого з, справедливе порівняння

.

2. Ознаки подільності

Розрізняють загальні ознаки, що мають силу для будь-якого m і власні - для окремих значень m.

Загальну ознаку подільності виражає правило, за допомогою якого по цифрах числа N записаного в системі числення з основою g, можна судити про подільність його на інше число m.

Французький математик Блез Паскаль (1623−1662) знайшов загальну ознаку подільності. Її можна сформулювати наступним чином:

Теорема 7 (загальна ознака подільності Паскаля). Для того, щоб число N, записане в довільній g-ітій системі числення у вигляді:

ділилося на число m, необхідно і достатньо, щоб число ділилося на m (де — цифри числа N, а — абсолютно найменші вирахування відповідних степенів по модулю m, і = 1, 2., n). Доведення. Нехай, де — абсолютно найменше вирахування числа по модулю m, (i = 1, 2., n). Тоді

(1)

Число N ділиться на m тоді і тільки тоді, коли

(2)

З рівнянь (1) і (2) і їх транзитивності отримуємо умову, рівносильну умові (2):

. (3)

З доведеного випливає: для того, щоб N ділилося на т, необхідно і достатньо, щоб Q ділилося на m.

Теорема доведена.

Як наслідок із загальної ознаки Паскаля витікають різні ознаки подільності. Розглянемо деякі з них (найчастіше використовувані на практиці).

Наслідок 1. Нехай m — дільник числа g — 1. Для того, щоб число, записане в g-ітій системі числення, ділилося на m, необхідно і достатньо, щоб сума його цифр ділилася на m.

Доведення. В даному випадку, а; тоді, тобто, а тому:

.

Таким чином, для того, щоб N ділилося на m, необхідно і достатньо, щоб сума цифр цього числа ділилася на m.

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

Наслідок 2. Нехай m — дільник числа g + I. Для того, щоб число, записане в g-ітій системі числення, ділилося на m, необхідно і достатньо, щоб різниця між сумами цифр на парних і непарних місцях ділилася на m.

Доведення. В даному випадку Звідси витікає затвердження слідства. Для чисел, записаних в десятковій системі, отримуємо, а; тоді, тобто, а тому .

Для чисел, записаних в десятковій системі, отримуємо відому ознаку подільності на 11: для того, щоб число ділилося на 11, необхідно і достатньо, щоб різниця між сумами цифр на парних і непарних місцях ділилася на 11. Наприклад, число 25 697 058 не ділиться на 11, оскільки різниця (2 + 6 + 7 + 5) — (5 + 9 + 0 + 8) = 20−22 == - 2 не ділиться на 11.

Число 905 784 ділиться на 11.

Наслідок 3. Нехай m — дільник числа. Для того, щоб число, записане в g-ітій системі числення, ділилося на m, необхідно і достатньо, щоб число, записане останніми k цифрами даного числа, ділилося на m.

Доведення. В даному випадку для до, а тому

.

Або

. (*)

З (*) витікає твердження наслідку.

Для чисел, записаних в десятковій системі, із наслідку 3 випливає цілий ряд ознак подільності.

1) Основа (де) ділиться на 2, 5, 10.

В цьому випадку отримаємо ознаки подільності на 2, 5, 10.

а) Для подільності числа на 2 необхідно і достатньо, щоб остання цифра була парною.

б) Для подільності числа на 5 необхідно і достатньо, щоб остання цифра ділилася на 5 (остання цифра 0 або 5).

в) Для подільності числа на 10 необхідно і достатньо, щоб воно закінчувалося нулем.

2) Дільником числа (де) є числа 4, 25, 50, 100.

Застосовуючи наслідок 3, отримуємо ознаки подільності на 4, 25, 50, 100.

Зокрема, для того, щоб число ділилося на 4, необхідно і достатньо, щоб число, записане останніми двома () цифрами, ділилося на 4.

3) Аналогічно можна вивести ознаки подільності на дільників числа, тобто на числа 8, 125,. Тут потрібно розглядати число, записане останніми трьома цифрами даного числа.

Теорема 8. Для того, щоб число ділилося на 7, або на 11, або на 13, необхідно і достатньо, щоб різниця між числом записаним останніми трьома цифрами, і числом, записаним цифрами, які залишилися даного числа (або навпаки), ділилася на 7, або на 11, або на 13.

Доведення. Будь-яке число N можна представити у вигляді де — число, записане останніми трьома цифрами числа N, а n — цифрами, які залишилися (приклад: 829 296 = 829 1000 + 296).

Запишемо N так:

;

звідси отримаємо:

чи

З (4) слідує висновок: для того, щоб число N ділилося на 7, або на 11, або на 13, необхідно і достатньо, щоб число n — Q (або Q — n) ділилося на 7, або на 11, або на 13.

Приклади.

1. Чи ділиться число 56 704 на одне з чисел: 7, 11, 13? Знаходимо: Q — n = 704 — 56 = 648. Але число 648 не ділиться ні на 7, ні на 11, ні на 13; отже, і дане число не ділиться ні на одне з чисел: 7, 11, 13.

2. Чи ділиться число 454 111 на 7?

454 — 111 = 343, 3437; отже, 454 1117.

3. Перевірка арифметичних дій

Теорія порівнянь дає наступний спосіб перевірки арифметичних дій. Вибираємо деякий модуль m і замінюємо великі числа а, b, c, над якими нам треба виконуємо дії (додавання, віднімання, множення, піднесення до степеня), невеликими числами а', b', с' порівнянними з ними по модулю m. Виконавши дії над а, b, c ми такі ж дії виконуємо над а', b', с', якщо дії виконані правильно, то результати цих дій над а, b, c,. і над а', b', с',. мають бути порівнянні по модулю m.

Дійсно, згідно за властивостями якщо

…,

то

.

Для перевірки співвідношення представляємо його у вигляді. Використання цього способу перевірки, звичайно, має сенс лише тоді, коли знаходження таких чисел а', b', с' може бути здійснено легко і швидко. Для цього зазвичай як модуль m вибирають m=9 або m=11. Кожне число, записане в десятковій системі числення, порівнюємо з сумою його цифр по модулю 9, так що ми можемо сформулювати наступний спосіб «перевірки за допомогою дев’ятки» .

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

Звичайно, якщо помилка така, що різниця між знайденою і дійсною величинами кратна 9, то вона при цьому способі перевірки не буде помічена. По модулю m = 11 кожне число, записане в десятковій системі числення, буде порівнянне з сумою цифр, узятих справа. наліво поперемінно із знаками «плюс» і «мінус»; тому ми можемо сформулювати наступний спосіб «перевірки за допомогою одинадцяти». Для кожного числа обчислюється остача від ділення на 11 суми цифр, узятих поперемінно справа наліво зі знаками «плюс» і «мінує». Результат даних дій над цими остачами повинен відрізнятися від суми узятих поперемінно зі знаками «плюс» і «мінус» справа наліво цифр шуканого: результату на число, кратне 11. Якщо помилка буде кратна 11, вона не буде помічена при цьому способі.

При складних обчисленнях має сенс проводити дві перевірки: одну за допомогою модуля 9, а іншу за допомогою модуля 11. В цьому випадку помилка не буде помічена лише, якщо вона кратна 99, що, звичайно, буває дуже рідко.

Приклади.1) Перевірити за допомогою модуля 9, чи вірний результат множення 734 168 539 = 626 899 224.

Знаходимо, що сума цифр першого множника 21=3 (mod 9), а другого 25 = 7 (mod 9). Сума цифр добутку дорівнює 48 і дійсно відрізняється від 37 = 21 на число, кратне 9.

2) З допомогою, модуля 11 перевірити результат:

.

Сума цифр основи, узятих поперемінно із знаками «плюс» і «мінус», 7−9+1−3 7 (mod 11). Відповідна сума для результату, рівна — 9, відрізняється від 73 = 343 на число, кратне одинадцяти.

3) Перевірити за допомогою модулів 9 і 11, чи вірно, що:

Сума цифр діленого 426 (mod 9), дільника 30 3 (mod 9) і частки 325 (mod 9). Добуток 35=15 відрізняється від 6 на число, кратне 9. Перевіряємо за допомогою модуля 11. Знакозмінна сума цифр діленого, дільника і частки рівні відповідно 22, 2 і 14. Добуток 214 = 28 відрізняється від 22 на число, не кратне 11, так що результат не вірний.

4. Визначення члена цифр періоду при перетворенні звичайного дробу в десятковий

З елементарної арифметики відомо, що звичайний нескоротний дріб у перетворюється в скінченний десятковий дріб тоді і тільки тоді, коли канонічний розклад знаменника не містить простих множників відмінних від 2 і 5.

Нехай нескоротний дріб і канонічний розклад знаменника містить прості числа, відмінні від 2 і 5; перетворюватимемо такий дріб у десятковий.

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

Теорема 1. Якщо нескоротний дріб і (,

10) = 1, то цей дріб перетворюється у чистий періодичний десятковий дріб; число цифр у періоді дробу дорівнює , де - показник, до - якого належить число 10 за модулем .

Доведення. Справді, не порушуючи загальності міркувань, можна нескоротний дріб вважати правильним (якщо він неправильний, тобто

то. ми спочатку виділимо цілу частину); отже, можна вважати рівним одному з чисел, менших і взаємно простих з .

Перетворюватимемо дріб у десятковий за загальними правилами:

для цього поділимо спочатку 10 на позначаючи через частку і через — остачу від цього ділення, отримаємо:

Тепер поділимо на :

;

далі ділимо на :

і т.д. Такий процес нескінченний, бо щоразу будуть остачі, менші від і взаємно прості з. Справді,, за умовою, тому і; аналогічно, а тому і т.д.

Звідси випливає, що різних остач при зазначеному діленні буде не більш, як. Це означає, що не пізніш як через кроків ми дістанемо повторення остач, а отже, й повторення цифр частки.

Для доведення теореми залишається показати, що перше повторення настане після ділень, де — показник, до якого належить 10 за модулем причому перша остача, яка повторюється, саме и буде. Тому знайдений дріб буде чистим періодичним з числом цифр у періоді, яке дорівнює .

Але для доведення цих тверджень досить встановити, що коли — найменший показник, для якого

(1)

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

Справді, конгруенція (1) еквівалентна конгруенції:

. (2)

Ця конгруенція саме й показує, що приписавши до числа нулів, що відповідає визначенню послідовних цифр частки, дістанемо при діленні на остачу. Через те щонайменше невід'ємне число, для якого мають місце конгруенції (1) і (2), то жодна остача не може повторитись раніш як через ділень. Зокрема, при діленні на перша остача, що повторюється, саме й буде причому вона повториться точно через ділень. Цим теорему доведено.

Бачимо, залежить тільки від знаменника нашого дробу і, звичайно, від основи нашої системи числення, тобто від числа g = 10. Тому два дроби і, які задовольняють умову теореми 1, матимуть одну й ту саму довжину періоду при перетворенні їх у десяткові дроби.

Приклад. Знайти довжину періоду, який утворюється при перетворенні дробів, де — будь-яке ціле, взаємно-просте з 21 у десяткові. Тут; ділимо:

У частці маємо 6 цифр, беручи до уваги й 0, який відповідає першій дев? ятці. Отже,, тобто шуканий період складається з 6 цифр.

Теорема 2. Якщо нескоротний дріб і , де , то цей дріб перетворюється у мішаний періодичний десятковий дріб; число цифр у періоді дробу дорівнює де - показник, якому належить 10 за модулем ; число цифр до періоду дорівнює де - найбільше з чисел або .

Доведення. Справді, нехай дріб — нескоротний, причому

Помножимо на; після скорочення в знаменнику множників 2 і 5 отримаємо:

де дріб — нескоротний і. За теоремою 1, цей дріб перетворюється у чистий періодичний з числом цифр у періоді, яке дорівнює, де — показник, до якого належить 10 за модулем. Щоб з нього дістати дріб, треба поділити на, тобто перенести кому в знайденому періодичному дробі на знаків ліворуч. У результаті отримаємо мішаний періодичний дріб з числом цифр до періоду, що дорівнює. Цим теорему доведено.

Приклад.; маємо. Знайдемо, тобто показник, до якого належить 10 за модулем 7. Маємо:

.

Отже, (можна знайти згідно з зауваженням зробленим вище). Таким способом усі дроби виду, де, перетворюються в мішані періодичні дроби з числом цифр у періоді, яке дорівнює 6, і з числом цифр до періоду яке дорівнює 2. Так наприклад, безпосередньо переконуємось, що

.

Розглянемо обернену задачу: знайти звичайний дріб, який відповідає заданому періодичному дробу.

Нехай дано чистий періодичний дріб: де — ціла частина, тобто

або

;

але

де число зображається дев’ятками. Отже отримаємо:

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

Його можна подати так:

Звідси виводимо таке правило: щоб перетворити мішаний періодичний дріб у звичайний, треба від числа, що стоїть між комою і другим періодом (тобто від числа), відняти число, яке стоїть між комою і першим періодом (тобто число), і цю різницю зробити чисельником; у знаменнику треба написати стільки дев’яток, скільки цифр у періоді, й після них — стільки нулів, скільки цифр між комою й першим періодом, і цей дріб додати до цілої частини N.

Зауваження. Можна відразу перетворити періодичний дріб у звичайний неправильний дріб (не виділяючи цілої частини). Для цього треба цифри цілої частини вважати цифрами, що стоять до періоду, й застосувати правило для перетворення мішаного періодичного дробу в звичайний. При такій побудові знаменника цифри цілої частини враховувати не слід.

Приклад.

або .

5. Індекси. Загальні властивості

Загальновідомо, яке велике значення в різних розділах математики і особливо в обчислювальній практиці мають логарифми. У теорії чисел вводиться схожий з логарифмами апарат, який ми називатимемо індексами. Логарифмом b за основою а, як відомо, називається показник степеня а, рівний b. У теорії чисел аналогічно цьому розглядають показник степеня а, порівнянною з b по даному модулю m, і такий показник називають індексом b по модулю m і основою а.

Означення 1. Нехай (а, m) = l, (b, m) = 1; число s називається індексом b по модулю m і основою а, якщо

Таким чином, згідно з означенням:

. (1)

Якщо, то з слідує також, тобто індекс числа b є також індексом і всіх чисел з, і ми можемо таке число s називати індексом класу .

Означення 2. Нехай (а, m) =l, (b, m) = 1. s називається індексом класу пo модулю m і основою а, якщо по цьому модулю .

Приклади. Нехай модуль m =13, основа, а = 2, тоді, тобто, і для будь-якого буде також, тобто, і в той же час, оскільки, маємо також .

Нехай модуль m = 21, основа, а = 5. Тоді, , тобто по модулю 21,. По цьому модулю не існує, оскільки не існує s такого, що .

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

Теорема 1. Нехай g-будь-який первісний корінь по модулю m. Для кожного числа b, взаємно простого з модулем m, існують індекси за основою g, тобто існують s такі, що

.

Безліч всіх таких індексів s для даного фіксованого b збігається з не від?ємними числами деякого класу по модулю .

Властивості:

1. Нехай g — первісний корінь по модулю m, (b, m) = 1; порівняння

(2)

має місце тоді і лише тоді, коли

. (3)

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

. Тоді

.

3. Нехай g — первісний корінь по модулю m,

. Тоді

(5)

4. Нехай g — первісний корінь по модулю m, (а, m) = l,; тоді

. (6)

Означення 2. Якщо, , то під розумітимемо, тобто індекс будь-якого числа з класу пo модулю m.

5. Нехай g — первісний корінь по модулю; тоді

.

Індекси по простому модулю.

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

Індекси кожного такого числа згідно з теоремою 1 є невід?ємні числа деякого класу по модулю р-1, а теореми, а теореми 2−5 дають наступні правила операцій з індексами по модулю р.:

якщо,

то, і, навпаки,

з виходить .

.

.

.

Скорочено тут скрізь опущений знак g, який вказує основу, яка передбачається однаковою в лівій і правою частинах. Всі індексовані числа передбачаються що діляться на р.

По простому модулю р для кожного числа існує безліч індексів, порівнянних по модулю р — 1, і як індекс можна брати будь-яке з них. Зазвичай зі всіх можливих значень індексів по даній основі беруть найменше; при такому виборі індексів вони мають значення менші ніж р — 1.

Таблиці індексів для простих модулів р містять індекси чисел від 1 до р — 1. Для кожного такого числа і всіх порівнянних з ним по модулю р в таблиці вказується індекс, який являє собою одне з чисел: 0,1., р — 1. У деяких таблицях як індекс одиниці вказується не 0, а р — 1. Таблиці індексів складалися багатьма авторами. У 1839 р. таблиці індексів для простих чисел, менших чим 1000, були опубліковані Якобі.

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

Для складених модулів вигляду і, де р — просте число (р>2), існують первісні корені, і тому для будь-якого числа, взаємно простого з таким модулем, існують індекси.

Приклад. Скласти таблицю індексів по модулю 27 з основою g = 5.

Власні дільники числа рівні 1, 2,3. Оскільки незрівнянні з 1 по модулю 9, то 5 — первісний корінь по модулю, а отже і по модулю .

Отримуємо послідовно:

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

Теорема 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.

Висновки

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