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

З елементарної арифметики відомо, що звичайний нескоротний дріб у перетворюється в скінченний десятковий дріб тоді і тільки тоді, коли канонічний розклад знаменника не містить простих множників відмінних від 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.

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

Приклад.

, або .

Загальновідомо, яке велике значення в різних розділах математики і особливо в обчислювальній практиці мають логарифми. У теорії чисел вводиться схожий з логарифмами апарат, який ми називатимемо індексами. Логарифмом 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.

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