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

Курсова робота

АРІФМЕТІЧНІ ЗАСТОСУВАННЯ Теорії КОНГРУЕНЦІЙ

Зміст

Вступ

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. Наприклад, число 25697058 НЕ діліться на 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 - цифрами, які залиша (приклад: 829296 = 829 1000 + 296).

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

;

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

,

чі

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

Приклади.

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

2. Чі діліться число 454111 на 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, чі Вірний результат множення 734168539 = 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 березня (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, Який відповідає першій дев'ятці.

Теорема 2. ,

доведення.

,

, де - на, У результаті

Приклад. Маємо:

.

.

,

або

;

,

Отже

,

Зауваження. Для

Приклад.

5.

. (1)

Означення 2.

Приклади. , ,

Теорема 1.

.

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

1.

(2)

. (3)

2.

. Тоді

.

3.

. Тоді

(5)

4.

. (6)

Означення 2. ,

5.

.

.

.

.

Зазвічай - 1.

Приклад.

1 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26

0 11 4 1 14 15 12 17 16 7 8 3 6 5 10 13 2 9

Теорема 2. и Теорема 3.

і.

Теорема 4.

.

при назівається

.

Приклад.

.

.

Теорема 5. .

Теорема 6.

.

.

,

Звідсі

.

Приклад.

.

.

.

и

Приклад. .

.

.

.

Висновкиний, Індекси.