Навигация
1.2. Класи за даним модулем
Візьмемо деяке натуральне число т; при діленні на т, будь-яких цілих чисел можна дістати тільки т різних невід'ємних остач, а саме: 0, 1,2, ... , т-1. Отже, множина всіх цілих чисел розіб'ється на т класів чисел, що не перетинаються; при цьому числа, які при діленні на т, даватимуть одну і ту саму остачу r (0 ≤ r < т), тобто числа, конгруентні за модулем т, утворюють клас чисел за модулем т.
Із сказаного випливає, що всім числам даного класу відповідає одна і та сама остача r; отже, дістанемо всі числа цього класу, якщо в формі mq+r, де r — стале, припустимо, що q набирає значення всіх цілих чисел.
З означення конгруентності двох чисел а і b за модулем т із щойно сказаного відразу ж випливає таке твердження.
Два цілих числа а і b тоді і тільки тоді належать до одного класу за модулем т, коли вони конгруентні за цим модулем..
Позначимо через C0 клас чисел, які діляться на т; через C1— клас чисел, які при діленні на т дають в остачі 1, і т. д. і нарешті, через Cm-1 — клас чисел, які при діленні на т дають в остачі т-1.
Будь-яке число даного класу називається лишком, або представником цього класу. Отже, якщо число a є представником деякого класу за модулем т, то будь-яке інше число b цього класу задовольняє умову: b≡a(mod m), або b=а + тt, де t — деяке ціле число, тобто, інакше кажучи, b = а + тt є загальний вигляд цілих чисел, які належать до того самого класу, що й а.
2. Конгруенції з невідомою величиною
Як видно з наведеного нижче малюнку, конгруенції в теорії чисел поділяються на конгруенції за простим та за складеним модулями.
| Види конгруенцій Рисунок |
2.1. Класи розв'язків конгруенції довільного степеня
Припустимо, що т — натуральне число. Конгруенція виду
f (x) ≡ 0(mod m), (1)
де f (х)= а0хп + а1хп-1 + . . . + аn-1x + an, є многочлен степеня n з цілими коефіцієнтами і а0 ≠ 0 (mod m) називається алгебраїчною конгруенцією п-го степеня з одним невідомим x.
Цілі значення х, що задовольняють конгруенцію (1), називаються коренями або розв'язками цієї конгруенції.
Розв'язати конгруенцію — це означає знайти всі значення невідомих, які її задовольняють.
Дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий розв'язок однієї конгруенції є розв’язком іншої.
Теорема 1. Якщо x = x1 задовольняє конгруенцію (1), то всяке число, яке належить до того самого класу лишків за модулем т , що й число x1, також задовольняє цю конгруенцію, тобто розв'язком буде весь клас чисел
х ≡ х1(mod т).
Це твердження безпосередньо випливає з властивостей конгруенцій. Справді, нехай х2 — будь-яке число, яке належить до того самого класу лишків за модулем т, що й х1; тоді х2 ≡ x1(mod m). За умовою х1 є розв'язок конгруенції (1), тобто має місце тотожна конгруенція f(x1) ≡ 0 (mod т), але тоді матиме місце й конгруенція f(x1) ≡ 0 (mod т), тобто x2 також буде розв'язком конгруенції. Оскільки x2 — будь-яке число класу х ≡ х1(mod т), то весь цей клас задовольнятиме дану конгруенцію.
Розв'язки конгруенції (1), що належать до одного класу чисел за модулем т, приймають за один розв'язок даної конгруенції. При цьому конгруенція (1) має стільки розв'язків, скільки класів чисел її задовольняють.
Приклад. Конгруенція
8x5 — 12x3 — 13x2 — 15x + 6 ≡ 0 (mod 5)
є еквівалентною конгруенції
Зх5 — 2x3 — Зx2 +1 ≡ 0 (mod 5),
або конгруенції
Зх5 + 3x3 + 2x2 +1 ≡ 0 (mod 5).
Щоб знайти розв'язки останньої конгруенції, випробуємо, приклад, абсолютно найменші лишки за модулем 5: 0, 1, 2, -2, -1. Безпосередньо видно, що 0, 1, -1 задану конгруенцію не задовольняють. При дальшому випробуванні можна скористатись схемою Горнера ( Див. Додаток) з тією тільки відмінністю, що для полегшення кожного разу можна відкидати числа, кратні модулю.
| 3 | 0 | 3 | 2 | 0 | 1 | |
| 2 | 3 | 6≡1 | 5≡0 | 2 | 4 | 9≡4 |
| -2 | 3 | 6≡ -1 | 5≡0 | 2 | -4 | 9≡4 |
Отже, конгруенція Зх5 + 3x3 + 2x2 +1 ≡ 0 (mod 5) не має розв'язків, а тому не має розв'язків і конгруенція
8x5 — 12x3 — 13x2 — 15x + 6 ≡ 0 (mod 5).
При розв'язуванні конгруенції з невідомою величиною іноді доводиться множити обидві частини конгруенції на ціле число. Для тотожних конгруенцій ця операція, як раніш було показано, завжди законна. Для конгруенцій з невідомою величиною таке перетворення не завжди законне, тобто, інакше кажучи, при такому перетворенні конгруенції може порушитись еквівалентність даної і добутої конгруенцій.
Приклад. Конгруенція
x4 + х3 + х2 + х + 1 ≡ 0 (mod 5),
як ми вище бачили, має один розв'язок: x ≡ 1 (mod 5). Але, якщо обидві частини цієї конгруенції помножити на 5, то дістанемо конгруенцію:
5x4 + 5х3 + 5х2 + 5х + 5 ≡ 0 (mod 5),
розв'язком якої буде вже будь-яке ціле число. Вона, по суті, перетворюється в конгруенцію 0 ≡ 0 (mod 5).
Конгруенції виду 0 ≡ 0 (mod 5) мають очевидно розв'язком будь-яке ціле значення невідомого х, тобто є тотожною конгруенцією.
Після наведеного щойно прикладу виникає питання, коли множення обох частин конгруенції з невідомою величиною на ціле число є законним? Відповідь на це дає теорема 2.
Теорема 2. Якщо обидві частини конгруенції (1) помножити на ціле число k, взаємно просте з модулем т, то дістанемо конгруенцію, еквівалентну даній.
Справді, припустимо, що
х = α (mod т)
є який-небудь розв'язок конгруенції (1), тоді
f (α) ≡ 0 (mod m).
Помножаючи обидві частини цієї конгруенції на k, дістанемо:
k∙f (α) ≡ 0 (mod m). (2)
Отже, ми бачимо, що α є розв'язком конгруенції
k∙f (x) ≡ 0 (mod m). (3)
Навпаки, якщо α — розв'язок конгруенції (3), тобто k∙f (α) ≡ 0 (mod m), тоді обидві частини конгруенції (2) можна скоротити на k, не змінюючи модуля, бо (k, m) = 1, (див. властивість 4, п.1.1), отже,
f (α) ≡ 0 (mod m),
тобто α є розв'язком конгруенції (1), що і доводить наше твердження.
Зауважимо, що при розв'язуванні конгруенцій з невідомою величиною можна, не змінюючи модуля, скорочувати обидві частини конгруенції тільки на такий їх спільний дільник, який є взаємно простий з модулем (див. властивість 4, п.1.1).
Похожие работы
оэта - это произведение, в котором "отразился век и современный человек". "Энциклопедией русской жизни" назвал В. Г. Белинский роман Пушкина. В этом романе, как в энциклопедии, можно узнать все об эпохе: о культуре того времени, о том, как одевались и что было в моде ("широкий боливар", фрак, жилет Онегина, малиновый берет Татьяны), меню престижных ресторанов ("бифштекс окровавленный", сыр, ...
... – Plantago lanceolata L. (2n = 12, рис. 1Б) и Подорожник средний – Plantago media L. (2n = 24, рис. 1В, оба из семейства Подорожниковые) [13]. Семена всех видов растений были собраны на территории Восточно-Уральского радиоактивного следа как с контрольных участков, так и с загрязнённых радионуклидами 90Sr–90Y и 137Cs. В местах сбора материала первоначальное загрязнение составляло 1500-2000 Ки[IV]/ ...
... . / Под ред. В.Н. Телия. – М.: Наука, 1991. – 214 с.Приложение В «Приложении» представлены наиболее характерные для научно-популярных лингвистических текстов примеры предложений и микротекстов, в которых авторы – лингвисты используют образное сравнение с целью объяснения, разъяснения, уточнения лингвистических понятий и явлений. Все перечисленные здесь научно-популярные книги указаны в списке ...
... ...) III Превосходная степень 1.Значение Превосходная степень указывает, что какой-то признак проявляется в данном предмете в наибольшей степен , по сравнению или без сравнения с тем же признаком в других однородных предметах. Превосходная степень бывает: Простой Сложной Превосходная степень прилагательного изменяется по родам, числам и падежам.( Мы подходили к высочайшим горам ). В ...
0 комментариев