Рішення порівнянь першого ступеня

Порівняння першого ступеня з одним невідомим має вигляд:

Вирішити порівняння - значить знайти всі значення х, йому задовольняють. Два порівняння, яким задовольняють одні й ті ж значення х, називаються рівносильними.

Якщо порівнянні (1) задовольняє будь-яке x = x1, то (згідно 49) того ж порівняно будуть задовольняти і все числа, які можна порівняти з x1. по модулю m. x x1 (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).

Порівняння першого ступеня перенесенням вільного члена (з протилежним знаком) в праву частину можна привести до виду

Розглянемо порівняння, яке задовольняє умові (а. M) = 1.

Згідно 66 наше порівняння має стільки рішень, скільки відрахувань повної системи йому задовольняє. Але коли x пробігає повну систему відрахувань по модулю т, то ах пробігає повну систему відрахувань (з 60). Отже, при одному і тільки одному значенні х, взятому з повної системи, ах буде порівнянно з b. Отже,

67. При (а, m) = 1 порівняння axb (mod m) має одне рішення.

Нехай тепер (a. M) = d> 1. Тоді, щоб порівняння (2) мало рішення, необхідно (з 55), щоб b поділялося на d, інакше порівняння (2) неможливо ні при якому цілому х. Припускаючи, тому b кратним d, покладемо a = a1d. b = b1d. m = m1d. Тоді порівняння (2) буде рівносильно такому (по скороченні на d): a1xb1 (mod m), в якому вже (а1. M1) = 1, і тому воно матиме одне рішення по модулю m1. Нехай х1 - найменший невід'ємні відрахування цього рішення по модулю m1, тоді все числа х, що утворюють це рішення, знайдуться у вигляді

За модулю ж mчісла (3) утворюють не одне рішення, а більше, саме стільки рішень, скільки чисел (3) знайдеться в ряді 0, 1, 2,. m - 1 найменших невід'ємних лишків за модулем m. Але сюди потраплять наступні числа (3):

тобто всього d чисел (3); отже, порівняння (2) має d рішень.

68. Нехай (a, m) = d. Порівняння ax b (mod m) неможливо, якщо b не ділиться на d. При b, кратному d, порівняння має d рішень ..

69.Способ рішення порівняння першого ступеня, заснований на теорії безперервних дробів:

Розкладаючи в безперервну дріб відношення m: а,

і розглядаючи дві останні підходящі дробу:

згідно властивостям безперервних дробів (згідно 30) маємо

Отже, порівняння має рішення

для розвідки, якого достатньо обчислити Pn- 1 згідно способу, зазначеному в 30.

Приклад. вирішимо порівняння

111x = 75 (mod 321). (4)

Тут (111, 321) = 3, причому 75 кратно 3. Тому порівняння має три рішення.

Ділячи обидві частини порівняння і модуль на 3, отримаємо порівняння

37x = 25 (mod 107), (5)

яке нам слід спочатку вирішити. маємо

Значить, в даному випадку n = 4, Pn-1 = 26, b = 25, і ми маємо рішення порівняння (5) у вигляді

x -26 # 8729; 25 99 (mod 107).

Звідси рішення порівняння (4) видаються так:

х 99; 99 + 107; 99 + 2 # 8729; 107 (mod 321),

х º99; 206; 313 (mod 321).

Обчислення зворотного елемента по заданому модулю

70.Еслі цілі числа a і n взаємно прості, то існує число a '. задовольняє порівнянні a # 8729; a '≡ 1 (mod n). Число a 'називається мультиплікативним оберненим до a за модулем n і для нього використовується позначення a - 1 (mod n).

Обчислення зворотних величин по деякому модулю може бути виконано рішенням порівняння першого ступеня з одним невідомим, в якому за x приймається число a '.

Щоб знайти рішення порівняння

можна скористатися алгоритмом Евкліда (69) або теоремою Ферма-Ейлера, яка стверджує, що якщо (a, m) = 1, то

Групи і їх властивості

Групи - один з таксономічних класів, використовуваних при класифікації математичних структур з загальними характерними властивостями. Групи мають дві складові: безліч (G) і операції (), певні на цій множині.

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

Для двох множин A, B записи BA. BA. B ∩ A. BA. B \ A. A × B означають відповідно, що B є підмножиною множини A (тобто будь-який елемент з B міститься також і в A. наприклад, безліч натуральних чисел міститься в множині дійсних чисел, крім того, завжди AA), B є власним підмножиною множини A (тобто BA і B ≠ A), перетин множин B і A (тобто всі такі елементи, які лежать одночасно і в A. і в B. наприклад перетин цілих чисел і позитивних дійсних чисел є безліч натуральних чисел), об'єднання множин B і A (тобто множина, що складається з елементів , Які лежать або в A. або в B), різниця множин B і A (тобто безліч елементів, які лежать в B. але не лежать в A), декартовій твір множин A і B (тобто безліч пар виду (a. b), де aA. bB). Через | A | завжди позначається потужність безлічі A. тобто кількість елементів у множині A.

Операція - це правило, згідно з яким будь-яким двом елементам безлічі G (a і b) ставиться у відповідність третій елемент з G: а b.

Безліч елементів G з операцією називається групою. якщо задовольняються наступні умови:

1. Асоціативність. для будь-яких елементів a, b, cG виконується рівність a (b c) = (a b) c.

2. Одиничний елемент: існує такий елемент е G, що при будь-якому a G виконуються рівності a e = e a = a.

3. Зворотний елемент. для кожного a G знайдеться елемент a 'G. задовольняє співвідношенню a a' = a 'a = e.

Елемент e з G називається нейтральним елементом групи, а елемент a '- зворотним елементом до a. Зворотний елемент позначається a '= a - 1.

Групи, в яких операція коммутативна. тобто для будь-якої пари a. b G виконується рівність a b = b a. називаються комутативними групами, або абелевих груп.

Число елементів в групі називається її порядком.

З точки зору вирішення рівнянь основна властивість групи в тому, що в ній однозначно дозволені рівняння виду:

при будь-яких a, b G.

1. Цілі, раціональні, дійсні, комплексні числа по складанню.

2. Ненульові раціональні, дійсні, комплексні числа по множенню.

Всі ці групи є Абелеві.