Порівняння за модулем натурального числа. Рішення порівнянь першого ступеня Рішення системи порівнянь за модулем
![Порівняння за модулем натурального числа. Рішення порівнянь першого ступеня Рішення системи порівнянь за модулем](https://i1.wp.com/helpiks.org/helpiksorg/baza6/90407071027.files/image574.gif)
Розглянемо порівняння вигляду x 2 ≡a(mod pα), де p- Просте непарне число. Як було показано в п.4 §4, рішення цього порівняння можна знайти, вирішивши порівняння x 2 ≡a(mod p). Причому порівняння x 2 ≡a(mod pα) матиме два рішення, якщо aє квадратичним вирахуванням за модулем p.
Приклад:
Вирішити квадратичне порівняння x 2 ≡86(mod 125).
125 = 5 3,5 - просте число. Перевіримо, чи є 86 квадратом за модулем 5.
Початкове порівняння має 2 рішення.
Знайдемо рішення порівняння x 2 ≡86(mod 5).
x 2 ≡1(mod 5).
Це порівняння можна було б вирішити способом, зазначеним у попередньому пункті, але ми скористаємося тим, що квадратний корінь з 1 за будь-яким модулем є ±1, а порівняння має рівно два рішення. Таким чином, рішення порівняння за модулем 5 є
x≡±1(mod 5) або, інакше, x=±(1+5 t 1).
Підставимо рішення, що вийшло в порівняння по модулю 5 2 =25:
x 2 ≡86(mod 25)
x 2 ≡11(mod 25)
(1+5t 1) 2 ≡11(mod 25)
1+10t 1 +25t 1 2 ≡11(mod 25)
10t 1 ≡10(mod 25)
2t 1 ≡2(mod 5)
t 1 ≡1(mod 5), або, що те саме, t 1 =1+5t 2 .
Тоді рішення порівняння за модулем 25 є x=±(1+5(1+5) t 2))=±(6+25) t 2). Підставимо рішення, що вийшло в порівняння по модулю 5 3 =125:
x 2 ≡86(mod 125)
(6+25t 2) 2 ≡86(mod 125)
36+12·25 t 2 +625t 2 2 ≡86(mod 125)
12·25 t 2 ≡50(mod 125)
12t 2 ≡2(mod 5)
2t 2 ≡2(mod 5)
t 2 ≡1(mod 5), або t 2 =1+5t 3 .
Тоді рішення порівняння за модулем 125 є x=±(6+25(1+5) t 3))=±(31+125) t 3).
Відповідь: x≡±31(mod 125).
Розглянемо тепер порівняння вигляду x 2 ≡a(Mod 2 α). Таке порівняння не завжди має два рішення. Для такого модуля можливі випадки:
1) α=1. Тоді порівняння має рішення лише тоді, коли a≡1(mod 2), і рішенням буде x≡1(mod 2) (одне рішення).
2) α=2. Порівняння має рішення лише тоді, коли a≡1(mod 4), і рішенням буде x≡±1(mod 4) (два рішення).
3) α≥3. Порівняння має рішення лише тоді, коли a≡1(mod 8), і таких рішень буде чотири. Порівняння x 2 ≡a(mod 2 α) при α≥3 вирішується так само, як порівняння виду x 2 ≡a(mod pα), тільки як початкове рішення виступають рішення за модулем 8: x≡±1(mod 8) та x≡±3(mod 8). Їх слід підставити порівняння за модулем 16, потім за модулем 32 і т. д. аж до модуля 2 α .
Приклад:
Вирішити порівняння x 2 ≡33(mod 64)
64 = 2 6 . Перевіримо, чи має вихідне порівняння рішення. 33≡1(mod 8), отже порівняння має 4 рішення.
За модулем 8 ці рішення будуть: x≡±1(mod 8) та x≡±3(mod 8), що можна уявити як x=±(1+4 t 1). Підставимо цей вираз порівняння за модулем 16
x 2 ≡33(mod 16)
(1+4t 1) 2 ≡1(mod 16)
1+8t 1 +16t 1 2 ≡1(mod 16)
8t 1 ≡0 (mod 16)
t 1 ≡0 (mod 2)
Тоді рішення набуде вигляду x=±(1+4 t 1)=±(1+4(0+2) t 2))=±(1+8 t 2). Підставимо рішення, що вийшло в порівняння по модулю 32:
x 2 ≡33(mod 32)
(1+8t 2) 2 ≡1(mod 32)
1+16t 2 +64t 2 2 ≡1(mod 32)
16t 2 ≡0 (mod 32)
t 2 ≡0 (mod 2)
Тоді рішення набуде вигляду x=±(1+8 t 2) =±(1+8(0+2t 3)) =±(1+16) t 3). Підставимо рішення, що вийшло в порівняння по модулю 64:
x 2 ≡33(mod 64)
(1+16t 3) 2 ≡33(mod 64)
1+32t 3 +256t 3 2 ≡33(mod 64)
32t 3 ≡32 (mod 64)
t 3 ≡1 (mod 2)
Тоді рішення набуде вигляду x=±(1+16) t 3) =±(1+16(1+2t 4)) =±(17+32) t 4). Отже, за модулем 64 вихідне порівняння має чотири рішення: x≡±17(mod 64)і x≡±49(mod 64).
Тепер розглянемо порівняння загального вигляду: x 2 ≡a(mod m), (a,m)=1, - канонічне розкладання модуля m. Відповідно до Теореми з п.4 §4, даному порівнянню рівносильна система
Якщо кожне порівняння цієї системи можна розв'язати, то можна розв'язати і всю систему. Знайшовши рішення кожного порівняння цієї системи, ми отримаємо систему порівнянь першого ступеня, вирішивши яку за китайською теоремою про залишки, отримаємо вихідне рішення. При цьому кількість різних рішень вихідного порівняння (якщо воно можна розв'язати) є 2 kякщо α=1, 2 k+1 якщо α=2, 2 k+2 якщо α≥3.
Приклад:
Вирішити порівняння x 2 ≡4(mod 21).
Проект з математики на тему
«Порівняння по модулю»
Заріпова Айсилу
Радянський район міста Казані
МБОУ «ЗОШ №166», 7а клас
Науковий керівник: Антонова Н.А.
Зміст
Вступ____________________________________________________3
Що таке порівняння________________________________________4
Поняття порівнянь по модулю__________________________4
Історія виникнення поняття порівнянь за модулем_____4
Властивості порівнянь___________________________________4
Найпростішим застосуванням порівнянь за модулем є визначення ділимості чисел___________________________6
Одне завдання на порівняння_______________________________8
Застосування порівнянь по модулю у професійній діяльності
Застосування порівнянь до розв'язання задач______________________6
Заключение__________________________________________________10
Список використаної литературы_____________________________11
Вступ.
Тема роботи: Порівняння за модулем.
Проблема: Багато учнів стикаються із завданнями при підготовці до олімпіад, вирішення яких ґрунтується на знанні залишків від поділу цілих чисел на натуральне число. Нас зацікавили такого роду завдання та можливі методи їх вирішення. Виявляється, вирішити їх можна за допомогою порівнянь щодо модуля.
Ціль: З'ясувати суть порівнянь по модулю, основні методи роботи з порівняннями по модулю.
Завдання: знайти теоретичний матеріал з цієї теми, розглянути завдання, які вирішуються з допомогою порівнянь по модулю, показати найпоширеніші методи розв'язання таких завдань, зробити висновки.
Об'єкт дослідження: теорія чисел.
Предмет дослідження: теорія порівнянь за модулем.
Робота стосується теоретичних досліджень і може бути використана при підготовці до олімпіад з математики. У її змісті розкриваються основні поняття порівнянь по модулю та його основні властивості, наводяться приклади розв'язання завдань з цієї теми.
I . Що таке порівняння |
Поняття порівнянь за модулем.
Числа і називаються порівнянними по модулю, якщо ділиться на, тобто а і мають однакові залишки при розподілі на.
Позначення
Приклади:
12 і 32 можна порівняти за модулем 5, так як 12 при розподілі на 5 має залишок 2 і 32 при розподілі на 2 має залишок 2. Записується12 ;
101 і 17 можна порівняти за модулем 21;
Історія виникнення поняття порівнянь за модулем.
Значною мірою теорія ділимості була створена Ейлером. Визначення порівняння було сформульовано у книзі К.Ф.Гаусса «Арифметичні дослідження». Цю роботу, написану латинською мовою, почали друкувати в 1797 році, але книга вийшла друком лише в 1801 році через те, що процес друкарства на той час був надзвичайно трудомістким і тривалим. Перший розділ книги Гауса так і називається: «Про порівняння чисел». Саме Гаус запропонував утверджену в математиці символіку порівнянь по модулю.
Властивості порівнянь.
Якщо
Доведення:
Якщо до першої рівності додати другу, то вийде
це сума двох цілих чисел, отже, є цілим числом, отже.
Якщо з першої рівності відняти другу, то вийде
це різниця двох цілих чисел, отже, є цілим числом, отже.
Розглянемо вираз:
це різниця творів цілих чисел, отже, є цілим числом, отже.
Це наслідок третьої якості порівнянь.
Що і потрібно було довести.
5) Якщо.
Доведення: Знайдемо суму двох цих виразів:
це сума двох цілих чисел, отже, є цілим числом, отже, .
Що і потрібно було довести.
6) Якщо - ціле число, то
Доказ: , деp– ціле число, помножимо цю рівність на, отримаємо: . Так як - добуток цілих чисел, то Що і потрібно довести.
7) Якщо
Доведення: міркування аналогічні доказу якості 6.
8) Якщо - взаємно прості числа, то
Доведення: , Поділимо цей вираз на, отримаємо: - взаємно прості числа, отже, ділиться на ціле, тобто. =. А це означає, що Що й потрібно було довести.
II . Застосування порівнянь до розв'язання задач.
2.1. Найпростішим застосуванням порівнянь за модулем є визначення подільності чисел.
приклад. Знайдіть залишок від розподілу 2 2009 на 7.
Рішення: Розглянемо ступеня числа 2:
зводячи порівняння у ступінь 668 і множачи на, отримуємо: .
Відповідь: 4.
приклад. Доведіть, що 7+7 2 +7 3 +…+7 4 n ділиться на 100 за будь-якогоnз множини цілих чисел.
Рішення: Розглянемо порівняння
і т.д. Циклічність залишків пояснюється правилами множення чисел стовпчиком. Складаючи перші чотири порівняння, отримуємо:
Значить, ця сума ділиться на 100 без залишку. Аналогічно, складаючи наступні порівняння про чотири, отримаємо, що кожна така сума ділиться на 100 без решти. Значить, вся сума, що складається з 4nдоданків, ділиться на 100 без залишку. Що і потрібно було довести.
приклад. Визначте, за якого значенняnвираз ділиться на 19 без залишку.
Рішення: .
Помножимо це порівняння на 20. Отримаємо.
Складемо порівняння, тоді. . Таким чином, права частина порівняння ділиться на 19 завжди за будь-якого натуральногоn, а, отже, вихідний вираз ділиться на 19 при натуральномуn.
Відповідь n - Будь-яке натуральне число.
приклад. Якою цифрою закінчується число.
Рішення. Для вирішення цього завдання слідкуватимемо лише за останньою цифрою. Розглянемо ступеня числа 14:
Можна помітити, що з непарному показнику значення ступеня закінчується на 4, а при парному – на 6. Тоді закінчується на 6, тобто. є парним числом. Значить, закінчуватиметься на 6.
Відповідь 6.
2.2. Одне завдання порівняння.
У статті М. Віленкіна «Порівняння та класи відрахувань» наводиться завдання, яке вирішив знаменитий англійський фізик Дірак у студентські роки.
Там же наводиться короткий розв'язок цього завдання з використанням порівнянь по модулю. Але ми зустрілися з низкою схожих завдань. Наприклад.
Один перехожий виявив купу яблук біля дерева, на якому сиділа мавпа. Перерахувавши їх, він зрозумів, що якщо 1 яблуко віддати мавпі, то кількість яблук, що залишилися, розділиться на n без залишку. Віддавши зайве яблуко мавпі, він узяв собі 1/ n решти яблук і пішов. До купи пізніше підійшов наступний перехожий, потім наступний і т.д. Кожен наступний перехожий, перерахувавши яблука, помічав, що їхня кількість при розподілі на n дає залишок 1 і, віддавши мавпі зайве яблуко, він забирав собі 1/ n решти яблук і йшов далі. Після того як пішов останній, n -й перехожий, кількість яблук, що залишилися в купі, поділялося на n без залишку. Скільки яблук було в купі спершу?
Провівши ті ж міркування, що і Дірак ми отримали загальну формулу для вирішення класу подібних завдань: , деn- натуральне число.
2.3. Застосування порівнянь за модулем у професійній діяльності.
Теорія порівнянь застосовується в теорії кодування, тому всі люди, які вибрали професію, пов'язану з комп'ютерами, вивчатимуть, а можливо, і застосовуватимуть порівняння у професійній діяльності. Наприклад, розробки алгоритмів шифрування з відкритим ключем використовується низку понять теорії чисел, зокрема і порівняння по модулю.
Висновок.
У роботі викладено основні поняття та властивості порівнянь за модулем, на прикладах проілюстровано застосування порівнянь за модулем. Матеріал може бути використаний при підготовці до олімпіад з математики та ЄДІ.
Наведений список літератури дозволяє за необхідності розглянути деякі складніші моменти теорії порівнянь по модулю та її застосування.
Список використаної литературы.
Алфутова Н.Б. Алгебра і теорія чисел. / Н. Б. Алфутова, А. В. Устінов. М: МЦНМО, 2002, 466 с.
Бухштаб О.О. Теорія чисел. / А.А.Бухштаб. М: Просвітництво, 1960.
Віленкін Н. Порівняння та класи відрахувань. / Н. Віленкін. / / Квант. - 1978. - 10.
Федорова Н.Є. Вивчення алгебри та математичного аналізу. 10 клас.http:// www. prosv. ru/ ebooks/ Fedorova_ Algebra_10 kl/1/ xht
ru. wikipedia. org/ wiki/Порівняння_по_модулю.
На n вони дають однакові залишки.
Еквівалентні формулювання: a та b можна порівняти за модулем n , якщо їхня різниця a - bділиться на n або якщо a може бути представлено у вигляді a = b + kn , де k- Деяке ціле число. Наприклад: 32 і −10 можна порівняти за модулем 7, оскільки
Твердження «a та b можна порівняти за модулем n» записується у вигляді:
Властивості рівності за модулем
Відношення порівняння по модулю має властивості
Будь-які два цілих числа aі bможна порівняти за модулем 1.
Для того, щоб числа aі bбули порівняні за модулем n, необхідно і достатньо, щоб їхня різниця ділилася на n.
Якщо числа і попарно можна порівняти за модулем n, то їх суми і , а також твори і теж можна порівняти за модулем n.
Якщо числа aі bможна порівняти за модулем n, то їхнього ступеня a kі b kтеж можна порівняти за модулем nпри будь-якому натуральному k.
Якщо числа aі bможна порівняти за модулем n, і nділиться на m, то aі bможна порівняти за модулем m.
Для того, щоб числа aі bбули порівняні за модулем nпредставленому у вигляді його канонічного розкладання на прості співмножники p i
необхідно і достатньо, щоб
Відношення порівняння є ставленням еквівалентності і має багато властивостей звичайних рівностей. Наприклад, їх можна складати та перемножувати: якщо
Порівняння, однак, не можна, взагалі кажучи, ділити один на одного чи інші числа. Приклад: однак, скоротивши на 2, ми отримуємо помилкове порівняння: . Правила скорочення порівнянь такі.
Не можна виконувати операції з порівняннями, якщо їх модулі не збігаються.
Інші властивості:
Пов'язані визначення
Класи відрахувань
Безліч всіх чисел, порівнянних з aза модулем nназивається класом відрахувань aза модулем n , і зазвичай позначається [ a] nабо . Таким чином, порівняння рівносильне рівності класів відрахувань [a] n = [b] n .
Оскільки порівняння за модулем nє відношенням еквівалентності на безлічі цілих чисел, то класи відрахувань за модулем nє класи еквівалентності; їх кількість дорівнює n. Безліч всіх класів відрахувань за модулем nпозначається або .
Операції складання та множення на індукують відповідні операції на множині:
[a] n + [b] n = [a + b] nЩодо цих операцій безліч є кінцевим кільцем, а якщо nпросте - кінцевим полем.
Системи відрахувань
Система вирахувань дозволяє здійснювати арифметичні операції над кінцевим набором чисел, не виходячи за його межі. Повна система відрахуваньза модулем n ― будь-який набір із n незрівнянних між собою за модулем n цілих чисел. Зазвичай як повна система відрахувань по модулю n беруться найменші невід'ємні відрахування
0,1,...,n − 1або абсолютно найменші відрахування, що складаються з чисел
,у разі непарного nта чисел
у разі парного n .
Вирішення порівнянь
Порівняння першого ступеня
Теоретично чисел , криптографії та інших галузях науки часто виникає завдання пошуку рішень порівняння першого ступеня виду:
Рішення такого порівняння починається з обчислення НОД (a, m) = d. При цьому можливі 2 випадки:
- Якщо bне кратно d, то порівняння немає рішень.
- Якщо bкратно d, то порівняння існує єдине рішення по модулю m / d, або, що те саме, dрішень по модулю m. В цьому випадку в результаті скорочення вихідного порівняння на dвиходить порівняння:
де a 1 = a / d , b 1 = b / d і m 1 = m / d є цілими числами, причому a 1 і m 1 взаємно прості. Тому число a 1 можна звернути за модулем m 1 , тобто знайти таке число c, Що (іншими словами, ). Тепер рішення є множенням отриманого порівняння на c:
Практичне обчислення значення cможна здійснити різними способами: за допомогою теореми Ейлера, алгоритму Евкліда, теорії ланцюгових дробів (див. алгоритм) та ін. Зокрема, теорема Ейлера дозволяє записати значення cу вигляді:
приклад
Для порівняння маємо d= 2 тому по модулю 22 порівняння має два рішення. Замінимо 26 на 4, порівнянне з ним за модулем 22, і потім скоротимо всі 3 числа на 2:
Оскільки 2 взаємно просто з модулем 11, можна скоротити ліву та праву частини на 2. У результаті отримуємо одне рішення за модулем 11: , еквівалентне двом рішенням по модулю 22: .
Порівняння другого ступеня
Рішення порівнянь другого ступеня зводиться до з'ясування, чи є дане число квадратичним відрахуванням (за допомогою квадратичного закону взаємності) та подальшого обчислення квадратного кореня за цим модулем.
Історія
Китайська теорема про залишки, відома вже багато століть, стверджує (сучасною математичною мовою), що кільце відрахувань за модулем твору кількох взаємно простих чисел є
Порівняння з одним невідомим xмає вигляд
Де. Якщо a n не ділиться на m, то й називається ступенемпорівняння.
Рішеннямпорівняння називається всяке ціле число x 0 , для котрого
Якщо х 0 задовольняє порівнянню, то, згідно з властивістю 9 порівнянь, цього порівняння будуть задовольняти всі цілі числа, порівняні з x 0 за модулем m. Тому всі рішення порівняння, що належать одному класу відрахувань за модулем т, розглядатимемо як одне рішення. Отже, порівняння має стільки рішень, скільки елементів повної системи відрахувань йому задовольняє.
Порівняння, множини рішень яких збігаються, називаються рівносильними.
2.2.1 Порівняння першого ступеня
Порівняння першого ступеня з одним невідомим хмає вигляд
(2.2)
Теорема2.4. Для того, щоб порівняння мало хоча б одне рішення, необхідно і достатньо, щоб число b ділилося на НОД( a, m).
Доведення.Спочатку доведемо потребу. Нехай d
=
НОД( a,
m)
і х 0
- Рішення порівняння. Тоді тобто різниця ах 0
−
b
ділиться на т.Отже, існує таке ціле число q,
що ах 0
−
b
=
qm.
Звідси b= ах 0
−
qm.
А оскільки d,
як спільний дільник, ділить числа аі т,то зменшуване і віднімається діляться на d,
а значить і b
ділиться на d.
Тепер доведемо достатність. Нехай d- найбільший спільний дільник чисел аі т,і b ділиться на d. Тоді за визначенням ділимості існують такі цілі числа a 1 , b 1 ,т 1 , що .
Розширеним алгоритмом Евкліда знайдемо лінійне уявлення числа 1 = НОД( a 1 , m 1 ):
для деяких x 0 , y 0 . Домножимо обидві частини останньої рівності на b 1 d:
або, що те саме,
,
тобто , і - рішення порівняння. □
Приклад2.10. Порівняння 9 х= 6 (mod 12) має рішення, оскільки НОД(9, 12) = 3 та 6 ділиться на 3. □
Приклад2.11. Порівняння 6х= 9 (mod 12) немає рішень, оскільки НОД(6, 12) = 6, а 9 не ділиться на 6. □
Теорема 2.5. Нехай порівняння (2.2) можна і d = НОД( a, m). Тоді безліч рішень порівняння (2.2) складається з d класів відрахувань за модулем т,а саме, якщо х 0 - одне з рішень, то всі інші рішення – це
Доведення.Нехай х 0
- Рішення порівняння (2.2), тобто і ,
.
Отже, існує таке q, що ах 0
−
b
=
qm.
Підставляючи тепер останню рівність замість х 0
довільне рішення виду, де, отримуємо вираз
, ділиться на m. □
Приклад 2.12. Порівняння 9 х=6 (mod 12) має три рішення, оскільки НОД(9, 12)=3. Ці рішення: х 0 = 2, х 0 + 4 = 6, х 0 + 2∙4=10.□
Приклад2.13. Порівняння 11 х=2 (mod 15) має єдине рішення х 0 = 7, так як НОД (11,15) = 1.□
Покажемо, як вирішувати порівняння першого ступеня. Не применшуючи спільності, вважатимемо, що НОД( a, т) = 1. Тоді рішення порівняння (2.2) можна шукати, наприклад, за алгоритмом Евкліда. Дійсно, використовуючи розширений алгоритм Евкліда, представимо число 1 у вигляді лінійної комбінації чисел aі т:
Помножимо обидві частини цієї рівності на b, отримаємо: b = abq + mrb, звідки abq - b = - mrb, тобто a ∙ (bq) = b(mod m) та bq- Рішення порівняння (2.2).
Ще один шлях вирішення – використовувати теорему Ейлера. Знову вважаємо, що НОД(а, т)= 1. Застосовуємо теорему Ейлера: . Помножимо обидві частини порівняння на b:
.
Переписуючи останній вираз у вигляді
, Отримуємо, що- рішення порівняння (2.2).
Нехай тепер НОД( a, m) = d>1. Тоді a = atd, m = mtd, де НОД( а 1 , m 1) = 1. Крім того, необхідно b = b 1 d, щоб порівняння можна було розв'язати. Якщо х 0 - Рішення порівняння а 1 x = b 1 (mod m 1), причому єдине, оскільки НОД( а 1 , m 1) = 1, то х 0 буде рішенням та порівняння а 1 xd = db 1 (mod m 1), тобто вихідного порівняння (2.2). Інші d- 1 рішень знаходимо за теоремою 2.5.
Порівняння першого ступеня з одним невідомим має вигляд:
f(x) 0 (mod m); f(х) = ах + а n. (1)
Вирішити порівняння- Значить знайти всі значення х, йому задовольняють. Два порівняння, яким задовольняють ті самі значення х, називаються рівносильними.
Якщо порівняння (1) задовольняє будь-яке x = x 1, то (згідно 49) тому ж порівнянні будуть задовольняти і всі числа, які можна порівняти з x 1 , за модулем m: x x 1 (mod m). Весь цей клас чисел вважається за одне рішення. За такої угоди можна зробити такий висновок.
66.С рівняння (1) матиме стільки рішень, скільки відрахувань повної системи йому задовольняє.
приклад. Порівняння
6x- 4 0 (mod 8)
серед чисел 0, 1,2, 3, 4, 5, 6, 7 повної системи відрахувань за модулем 8 задовольняють два числа: х= 2 і х= 6. Тому вказане порівняння має два рішення:
x 2 (mod 8), х 6 (mod 8).
Порівняння першого ступеня перенесенням вільного члена (зі зворотним знаком) у праву частину можна привести до вигляду
ax b(mod m). (2)
Розглянемо порівняння, що задовольняє умову ( а, m) = 1.
Відповідно до нашого порівняння має стільки рішень, скільки відрахувань повної системи йому задовольняє. Але коли xпробігає повну систему відрахувань по модулю т,то ахпробігає повну систему відрахувань (з 60). Отже, за одного і лише одного значення х,взятому з повної системи, ахбуде порівняно з b.Отже,
67. При (а, m) = 1 порівняння ax b(mod m)має одне рішення.
Нехай тепер ( a, m) = d> 1. Тоді, щоб порівняння (2) мало рішення, необхідно (з 55), щоб bділилося на d,інакше порівняння (2) неможливе ні при якому цілому х . Припускаючи, тому bкратним d,покладемо a = a 1 d, b = b 1 d, m = m 1 d.Тоді порівняння (2) буде рівносильним такому (за скороченням на d): a 1 x b 1 (mod m), в якому вже ( а 1 , m 1) = 1, і тому воно матиме одне рішення щодо модуля m 1 . Нехай х 1 – найменше невід'ємне відрахування цього рішення за модулем m 1 , тоді всі числа х , які утворюють це рішення, знайдуться у вигляді
x x 1 (mod m 1). (3)
По модулю ж m числа (3) утворюють не одне рішення, а більше, саме стільки рішень, скільки чисел (3) знайдеться в ряді 0, 1, 2, ..., m – 1 найменших невід'ємних відрахувань по модулю m.Але сюди потраплять такі числа (3):
x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,
тобто. всього dчисел (3); отже, порівняння (2) має dрішень.
Отримуємо теорему:
68. Нехай (a, m) = d. Порівняння ax b ( mod m) неможливо, якщо b не поділяється на d. При b, кратному d, порівняння має d рішень.
69.Спосіб вирішення порівняння першого ступеня, заснований на теорії безперервних дробів:
Розкладаючи у безперервний дріб ставлення m:а,
і розглядаючи два останні відповідні дроби:
згідно з властивостями безперервних дробів (згідно з 30 ) маємо
Отже, порівняння має рішення
для розшуку, якого достатньо вирахувати P n– 1 згідно з способом, зазначеним у 30.
приклад. Вирішимо порівняння
111x= 75 (mod 321). (4)
Тут (111, 321) = 3, причому 75 разів 3. Тому порівняння має три рішення.
Ділячи обидві частини порівняння та модуль на 3, отримаємо порівняння
37x= 25 (mod 107), (5)
яке нам слід спочатку вирішити. Маємо
q | |||||
P 3 |
Отже, у разі n = 4, P n – 1 = 26, b= 25, і ми маємо рішення порівняння (5) у вигляді
x-26 ∙ 25 99 (mod 107).
Звідси рішення порівняння (4) видаються так:
х 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),
хº99; 206; 313 (mod 321).
Обчислення зворотного елемента за заданим модулем
70. Якщо цілі числа aі nвзаємно прості, існує число a′, що задовольняє порівнянні a ∙ a′ ≡ 1(mod n). Число a′називається мультиплікативним зворотним до a за модулем nі для нього використовується позначення a - 1 (mod n).
Обчислення зворотних величин за деяким модулем може бути виконано рішенням порівняння першого ступеня з одним невідомим, у якому xприймається число a′.
Щоб знайти рішення порівняння
a ∙x≡ 1(mod m),
де ( a,m)= 1,
можна скористатися алгоритмом Евкліда (69) або теоремою Ферма-Ейлера, яка стверджує, що якщо ( a,m) = 1, то
a φ( m) ≡ 1(mod m).
x ≡ a φ( m)-1 (mod m).
Групи та їх властивості
Групи – один із таксономічних класів, які використовуються при класифікації математичних структур із загальними характерними властивостями. Групи мають дві складові: безліч (G) та операції(), визначені на цій множині.
Поняття множини, елемента та приналежності є базисними невизначеними поняттями сучасної математики. Будь-яка множина визначається елементами, що входять до нього (які, у свою чергу, теж можуть бути множинами). Таким чином, ми говоримо, що множина визначена або задана, якщо для будь-якого елемента ми можемо сказати, належить він цій множині чи ні.
Для двох множин A, Bзаписи B A, B A, B∩ A, B A, B \ A, A × Bозначають відповідно, що Bє підмножиною безлічі A(тобто будь-який елемент з Bміститься також і в Aнаприклад, безліч натуральних чисел міститься в безлічі дійсних чисел; крім того, завжди A A), Bє власним підмножиною множини A(Тобто. B Aі B ≠ A), перетин множин Bі A(тобто всі такі елементи, які лежать одночасно і в A, і в B, наприклад перетин цілих чисел і позитивних дійсних чисел є безліч натуральних чисел), об'єднання множин Bі A(тобто безліч, що складається з елементів, які лежать або в A, або в B), різниця множин Bі A(тобто безліч елементів, які лежать у B, але не лежать у A), декартове твір множин Aі B(тобто безліч пар виду ( a, b), де a A, b B). Через | A| завжди позначається потужність множини A, тобто. кількість елементів у множині A.
Операція – це правило, згідно з яким будь-яким двом елементам множини G(aі b) ставиться у відповідність третій елемент з G: а b.
Безліч елементів Gз операцією називається групою, якщо задовольняються такі умови.