Курсова робота
АРИФМЕТИЧНІ ЗАСТОСУВАННЯ ТЕОРІЇКОНГРУЕНЦІЙ
Зміст
Вступ
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, 343/>7; отже, 454 111/>7.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, чивірний результат множення 73416/>8539 = 626 899224.
Знаходимо, що сума цифр першого множника 21=3(mod 9), а другого 25 = 7 (mod 9). Сума цифр добутку дорівнює 48 і дійсно відрізняєтьсявід 3/>7 = 21 на число, кратне 9.
2) З допомогою, модуля 11 перевірити результат:
/>.
Сума цифр основи, узятих поперемінно із знаками„плюс" і „мінус", 7-9+1-3 /> 7 (mod 11). Відповідна сума для результату,рівна — 9, відрізняється від 73 = 343 на число, кратне одинадцяти.
3) Перевірити за допомогою модулів 9 і 11, чи вірно,що:
/>
Сума цифр діленого 42/>6 (mod 9), дільника 30 /> 3 (mod9) і частки 32/>5 (mod 9). Добуток 3/>5=15 відрізняєтьсявід 6 на число, кратне 9. Перевіряємо за допомогою модуля 11. Знакозмінна сума цифрділеного, дільника і частки рівні відповідно 22, 2 і 14. Добуток 2/>14 = 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 — первісний корінь по модулю />, а отже і по модулю />.
Отримуємо послідовно:
/>
/> 1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26
/> 11 4 1 14 15 12 17 16 7 8 3 6 5 10 13 2 9
Досить мати таблиці індексів по модулях /> з основами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.
Висновки
Дана курсова робота стосується теорії конгруенцій,зокрема застосуванню конгруенцій: ознаки подільності, перевірка арифметичних дій,перетворення десяткового дробу у звичайний, індекси.