АНОТАЦІЯ
Стор. 24, рис. 1, табл. 1,бібліогр. 4
КОНГРУЕНЦІЯ, ВЛАСТИВІСТЬ, КЛАС, МОДУЛЬ, СТЕПІНЬ, РОЗВ’ЯЗОК
В роботі розглянуто означення, основні відомості про конгруенції n-гостепеня, їх властивості і дії над ними, та зроблено відповідні висновки. Такожрозглядаються класи чисел за даним модулем та класи розв’язків конгруенціїдовільного степеня. Вводиться поняття системи конгруенцій та доводиться теоремапро зведення конгруенцій за складним модулем до системи конгруенцій за простимимодулями.
Матеріал роботи може бути використаний при вивченні курсу алгебри вшколі на факультативних заняттях.
ЗМІСТ
TOCo «1-3» ВСТУП… PAGEREF _Toc533760419 h 4
1.КОНГРУЕНЦІЇ І КЛАСИ… PAGEREF _Toc533760420 h 6
1.1. Конгруенції та їхосновні властивості… -
1.2. Класи за даниммодулем… PAGEREF _Toc533760422 h 8
2.КОНГРУЕНЦІЇ ЗНЕВІДОМОЮ ВЕЛИЧИНОЮ… PAGEREF _Toc533760423 h 10
2.1. Класирозв'язків конгруенції довільногостепеня… -
2.2. Конгруенції n-го степеня за простим модулем.… PAGEREF _Toc533760425 h 13
2.2.1.Maкcимaльнe числорозв'язків… PAGEREF _Toc533760426 h 18
2.3. Системиконгруенцій… PAGEREF _Toc533760427 h 19
2.4. Зведенняконгруенцій за складеним модулем до системи конгруенцій за простими модулями… PAGEREF _Toc533760428 h 20
ВИСНОВКИ… PAGEREF _Toc533760429 h 23
ЛІТЕРАТУРА… PAGEREF _Toc533760430 h 24
ДОДАТОК. СХЕМА ГОРНЕРА… PAGEREF _Toc533760431 h 25
ВСТУП
Важливе місце в курсі теорії чиселпосідають конгруенції та, зокрема, конгруенції вищих степенів. Але до того яквони почали розглядатися, математики різних країн, протягом століть розглядалиневизначені рівняння 1-го степеня.
Невизначені рівняння 1-го степеня почалирозглядатися ще індуськими математиками приблизно з V століття. Деякі такі рівняння з двома і трьома невідомимиз'явилися в зв'язку з проблемами, що виникли в астрономії, наприклад, прирозгляді питань, зв'язаних з визначенням періодичного повторення небесних явищ.
У другому виданні книги французького математика Баше де Мезір’яка “Problemisplaisans et delectables que se font par les nombres”, що вийшли в 1624 р.,зважується невизначене рівняння ax+by=c.Баше де Мезір’як фактично застосовує процес, що зводить до послідовногообчислення не повних часток і розгляду придатних дробів; однак він не розглядавнеперервних дробів як таких. Популярний твір Баше де Мезір’яка дуже вплинув нарозвиток теорії чисел, так як сприяв виникненню інтересу до цієї областіматематики.
Ланцюгові дроби до рішення таких рівняньбули застосовані Лагранжем, котрий, однак, зауважує, що фактично це той жеспосіб, що був даний Баше де Мезір’яком і іншими математиками, що розглядалиневизначені рівняння до нього.
Невизначені рівняння 1-го степенястали записуватися й розв'язуватися у формі порівняння значно пізніше,починаючи з Гауса. Він вперше систематизував теорію та визначив поняттяконгруенції, в своїй книзі “Disquisitionesarithmeticae” (“Дослідження з арифметики”).
Задачі, що зводяться до розгляду системипорівнянь 1-го степеня, розглядалися в арифметиці китайського математика Сун Тзу, що жив приблизно напочатку нашої ери. У нього як у цілого ряду китайських, індуських, арабських ієвропейських учених, що вирішували такі задачі після нього, питання ставився внаступній формі: знайти число, що дає задані остачі від ділення на заданічисла. Робота Сун Тзу стала відомою в Європі в 1852 р. Незалежно відкитайських математиків спосіб рішення задач такого роду був даний індуськимматематиком Брамегупта (588-660).
Система n порівнянь із nневідомими вивчалася Гаусом. Повне дослідження систем лінійних конгруенцій булоподано в роботах Фробеніуса й Стейніца наприкінці XIX століття.
І так конгруенції вищих степенів були покладені в основу модулярногопредставлення числа, яке широко використовується в сучасній криптографії, щодосить актуальна в наш час високих технологій. Велику увагу цьому питаннюприділили такі вчені-дослідники як Ріверс, Адельман та Ширман.
1.КОНГРУЕНЦІЇ І КЛАСИ
Ряд чисел при діленні наодне і те саме число дають одну і ту ж саму остачу. Постає питання про те, якможна використати цю особливість і які властивості вона має. Відповідь на нього– конгруенції.1.1. Конгруенції таїх основні властивості
Припустимо, що mє натуральне число; розглядатимемоцілі числа в зв'язку з остачами від ділення їх на дане натуральне т, яке називають модулем. Згідно з теоремоюпро ділення з остачею кожному числу а відповідатимепевна остача rвід ділення а на r :
a=mq+r, 0 ≤ r
Якщо двом цілим числам a і b відповідаєодна і та сама остача r від ділення їхна m, то вони називаються конгруентними за модулем m. Це позначається символом:
a≡b(modm) (1)
і читається: а конгруентнез bза модулем m.
Деякі автори позначають це коротше:
a≡b(m). (1′)
Співвідношення (1) або(1′) між числами називаються порівнянням, або конгруенцією.
Приклади. 48 ≡ 84 (mod18);
131 ≡ 1 (mod 13);
10 ≡ –1 (mod 11).
Конгруенції мають багато властивостей,подібних до властивостей рівностей.
Властивість1. Для конгруенцій справджуються три основнізакони рівностей: рефлексивності, симетрії і транзитивності, тобто відповідно:
а) a≡a(mod m),
б) з конгруенції a≡b(mod m)випливає, що b≡a(mod m);
в) якщо a≡b(mod m) іb≡c(modm), то a≡c(mod m).
Властивість2. Конгруенціїза одним і тим же модулем можна почленно додавати (або віднімати).
Висновок1. Доданок,що стоїть в якій-небудь частині конгруенції, можна переносити в іншу частину, змінившизнак на протилежний.
Висновок2. Можнадодати до обох частин або відняти від обох частин конгруенції одне і те саме число.
Висновок3. До кожноїчастини конгруенції можна додати (або відняти від неї) довільне число, кратне модулеві.
Властивість3. Конгруенції за одним і тим самим модулем можна почленно перемножувати.
Висновок1. Обидвічастини конгруенції можна помножити на одне й те саме ціле число.
Висновок2. Обидвічастини конгруенції можна підносити до одного і того самого цілого невід'ємногостепеня, тобто, якщо a≡b(mod m), то an≡bn(mod m), де n— ціле ≥0.
Властивість4. Обидвічистини конгруенції можна поділити на їх спільний дільник, якщо він є взаємно простийз модулем.
Властивість5. Обидвічастини конгруенції і модуль можна помножити на одне і те саме натуральне число.
Властивість6. Обидвічастини конгруенції і модуль можна поділити на будь-якого їх спільного дільника.
Властивість7. Якщоконгруенція має місце за кількома модулями, то вона матиме місце і за модулем,що дорівнює їх найменшому спільному кратному.
Властивість8. Якщоконгруенція має місце за модулем –m,то вона матиме місце і за будь-яким дільником d цьогомодуля..
Властивість9. Якщоодна частина конгруенції і модуль ділятьсяна яке-небудь ціле число, то і друга частина конгруенції має ділитись на це число.
Властивість10. Числаа і b, конгруентніміж собою за модулем т, мають з ним одного і того самого найбільшого спільного дільника.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(modm),або b=а+ тt, де t — деяке ціле число, тобто, інакшекажучи, b= а + тt є загальний виглядцілих чисел, які належать до того самого класу, що й а.
2.КОНГРУЕНЦІЇ З НЕВІДОМОЮ ВЕЛИЧИНОЮ
Як видно з наведеного нижче малюнку,конгруенції в теорії чисел поділяються на конгруенції за простим та заскладеним модулями.
Види конгруенційЗА ПРОСТИМ МОДУЛЕМ
ЗА СКЛАДЕНИМ МОДУЛЕМ
КОНГРУЕНЦІЇ
Рисунок
2.1. Класирозв'язків конгруенції довільногостепеня
Припустимо, що т — натуральне число. Конгруенція виду
f(x)≡ 0(mod m), (1)
де f(х)= а0хп + а1хп-1 +... + аn-1x +an, є многочлен степеня n з цілими коефіцієнтами і а0≠ 0 (modm) називається алгебраїчноюконгруенцією п-гостепеня з одним невідомим 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
3
2
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 (mod5),
як ми вище бачили, має один розв'язок: x ≡ 1 (mod5). Але, якщо обидві частиницієї конгруенції помножити на 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 (modm).
Помножаючи обидві частини цієї конгруенції на k, дістанемо:
k∙f(α)≡ 0 (modm). (2)
Отже, ми бачимо, що α є розв'язком конгруенції
k∙f(x)≡ 0 (modm). (3)
Навпаки, якщо α — розв'язок конгруенції(3), тобто k∙f(α)≡ 0 (modm), тоді обидві частини конгруенції(2) можна скоротити на k, не змінюючи модуля, бо (k, m) = 1, (див. властивість 4, п.1.1), отже,
f(α)≡ 0 (modm),
тобто α є розв'язком конгруенції (1), що і доводить нашетвердження.
Зауважимо, що при розв'язуванніконгруенцій з невідомою величиною можна, не змінюючи модуля, скорочувати обидвічастини конгруенції тільки на такий їх спільний дільник, який є взаємно простийз модулем (див. властивість 4, п.1.1).2.2. Конгруенції n-го степеня за простим модулем.
У попередньому параграфі мибачили, що дослідження й розв'язання конгруенції п-го степеня (п≥1)зводиться кінець кінцем до дослідження і розв'язання відповідних конгруенцій запростими модулями. Тому зараз доведемо деякі загальні теореми, що стосуютьсяконгруенцій n-го степеня за простим модулем р.
Припустимо, що заданоконгруенцію[1]:
f(х)= а0хп + а1хп-1 +... + аn-1x +an ≡ 0 (mod p), n≥1, (1)
де a0≠0 (mod p) і р — простечисло.
Теорема 1. Конгруенцію (1) завжди можна так перетворитищо її старший коефіцієнт дорівнюватиме одиниці.
Справді, через те що р — просте і a0не ділиться на р, то завжди існує єдине число α, що а0α ≡ 1 (modp). Помножившитепер конгруенцію (1) на α і замінивши а0x одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, щодорівнює одиниці:
xn+ b1xn-1+… + bn-1x + bn ≡0 (mod p); (1')
тут bi ≡ aiα (modp).
Теорема 2. Якщо степінь конгруенції (1) не менший відмодуля конгруенції, то вона еквівалентна деякій конгруенції степеня, не вище зар—1 (за тим самим модулем).
Справді, поділимо f(х)на хр-х; і частку від ділення позначимо через q(x), а остачу через r(х). Тоді на підставі алгоритму ділення з остачею дістанемо:
f(x) = (xp—x)q(x) + r(x),
де частка q(х) іостача r(х) будуть многочленами зцілими коефіцієнтами, причому степінь r(х)буде не вище р—1. За теоремоюФерма xp—-x ≡ 0 (mod p) при будь-якому цілому х,тому дістанемо тотожну конгруенцію:
f(х)≡ r(x) (modр).
Ця тотожна конгруенція показує, що корені конгруенції (1)і конгруенції r(х)≡0 (mod р)однакові. Оскільки хр — х завжди ділиться на p, то f(x) і r(x)можуть ділитись на p тількиодночасно; отже, конгруенції
f(х)≡ 0 (modр) і r(х)≡ 0 (modр)
еквівалентні. Через те що степінь r(x)менше за p,то теорему доведено.
Зокрема, може статись, що f(x)ділиться на xp—-x , тобто r(х)≡ 0 (modр) – тотожна конгруенція замодулем p, тобто остача при діленні конгруентна з нулемі дана конгруенція еквівалентна конгруенції 0 ≡ 0 (mod p)та справедлива при будь-якому цілому x. Далі, нехай остачавід ділення f(х)на xp—-x є многочлен нульового степеня, що дорівнює bp-1. Якщо bp-1не ділиться на p, то дана конгруенція не має розв’язків, бовона зводиться до невірної конгруенції :
bp-1≡ 0 (modp).
Приклад. Якій конгруенціїнижче від 5-го степеня еквівалентна конгруенція:
f(х) = х17 + 2x11 + Зx8— 4x7 + 2x — 3 ≡ 0 (mod5).
Поділивши f (х)на х5 — х ізамінивши всі коефіцієнти остачі найменшими невід'ємними лишками за модулем 5,дістанемо, що дана конгруенція еквівалентна конгруенції
r(х) =Зx4 + Зx3 + Зx + 2 ≡ 0 (mod 5).
Зауваження.Можна вказане ділення на хp — х фактично і невиконувати, а просто замінити хnна хr, де r > 0 є остача від ділення п на р— 1. Справді, за теоремою Ферма хр ≡ х (modр), звідси xp+1≡ x2, xp+2 ≡ x3, … і взагалі:
Через те що в нашомуприкладі x17 можназамінити через х, а 2x11через 2x3, Зx8 через Зx4,—4x7замінити через —4x3≡ x3, тому відразудістанемо:
f(x) ≡ Зx4 + Зx3+ Зx + 2 ≡ 0 (mod 5).
У свою чергу, останнюконгруенцію можна спростити так: х ≠ 0 (mod5), тому x5-1 ≡ 1 (mod 5) і
f(x) ≡ Зх3 + Зх ≡ 0 (mod5),
або
f(x) ≡ х2 + 1 ≡ 0 (mod 5).
Очевидні розв'язки останньоїконгруенції x ≡ 2, 3 (mod 5) будуть також ірозв'язками даної конгруенції:
f(x) ≡ 0 (mod5).
Теорема 3. Якщо α1—який-небудь розв'язок конгруенції (1), то має місце тотожна конгруенція:
f(х) ≡ (х — α1)f1(х)(mod р), (2)
деf1(х)— многочлен степеня, на одиницю нижчий від степеня многочлена f(x). Старшийкоефіцієнт многочлена f1(x)збігаєтьсяз старшим коефіцієнтом даного многочлена fix).
Справді, поділимо f(x) на х —α1 і частку позначимо через f1(х),а остачу через r. За теоремою Безу r = f(α1),але
f(α1) ≡ 0(mod p)
за умовою, тоді конгруенцію
f(x) = (x – α1) f1(x) + f(α1)≡ 0 (mod р)
можна переписати так:
f(x)≡ (x-α1)f1(x) (modp).
При цьому кажуть, що f(х) ділиться на х — α1 за модулем р. Очевидно, що й навпаки: з конгруенції (2) випливає, що f(α1)≡ 0 (mod p)тобто α1 —корінь конгруенції (1); отже, маємо такий висновок.
Висновок.Конгруенція(1) має корінь х = α1тоді і тільки тоді, коли ліва її частина f(x) ділитьсяна х — α1за даним модулем р.
Зауважимо, що теорема 3 івисновок з неї справедливі і для складеного модуля т.
Теорема 4. Якщо α1, α2,.., αk(k ≤n)є різнірозв'язкиконгруенції (1), то має місце тотожна конгруенція:
f(х) ≡(х – α1) (х — α2)... (х — αk)fk (x) (mod p), (3)
де степінь f (х) дорівнює п — k і старші коефіцієнти у f(x) і fk(x) однакові.
Справді, згідно, з теоремою3 конгруенція (1) еквівалентна конгруенції
(x — α1)f1(x)≡ 0 (mod p). (21)
Через те що α2 є розв'язок конгруенції (1), то, підставляючийого в еквівалентну конгруенцію (2'), дістанемо тотожну конгруенцію:
(α2 —α1)f1(α2)≡ 0 (mod р).
Але добуток двох чи кількох чисел ділиться на простечисло р тоді і тільки тоді, коли на р ділиться принаймні один зспівмножників. За умовою α1 і α2 різні, тобто
α1≠α2 (mod p),
отже, α2 — α1 не ділитьсяна р, а тому f1(α2) ділиться на р, тобто f1(α2) ≡ 0 (mod p);останнє означає, що α2— розв'язок конгруенції f1(x)≡0(mod p). За теоремою 3 дістанемо:
f1(х)≡(x-α2)f2(x) (mod p);
звідки
f(x)≡(x-α1)(x-α2)f2(x) (mod p).
Аналогічно міркуючи, кінецькінцем прийдемо до тотожної конгруенції (3). З самого процесу одержаннямногочленів f1(x),f2(x),… fk (x) видно, що старші коефіцієнти цих многочленів однакові ідорівнюють старшому коефіцієнтові a0многочлена f(x).
В и с но в о к. Якщо конгруенція (1) п-го степеня за простим модулем р (п можна вважатине більшим за р — 1) має п різнихрозв'язків α1,α2,.., αn, то має місце тотожна конгруенція:
f(x)≡ а0(х — α1)(х — α2)… (х — αn) (mod p). (4)
Справді, тут k= п, отже,степінь многочлена fn(x) дорівнюватиме п-n=0, тобто fn (х) = а0.2.2.1.Maкcимaльнe число розв'язків
Теорема 5. Конгруенція п-го степеня за простим модулемне може мати більш як п різних розв'язків.
Справді, нехай β – який-небудь іншийрозв'язок, відмінний від α1,α2,.., αn,тобто
β≠αi(mod p) (i = 1, 2, …, n);
покладаючи тепер в тотожній конгруенції (4) х=β, знайдемо, що
a0(β – α1)(β – α2) … (β — αn) ≡ 0 (mod p), (4′)
але різниці β — αi за умовою не діляться на р, тобто взаємно прості з р,а в такому разі і їх добуток буде взаємно простим з р. Звідси випливає, що має місце конгруенція (4'), тобто f(β)≡ 0 (mod p), тому а0має ділитись на р, що суперечить умові, бо в нас a0≠ 0 (mod p).
Слід зауважити, по-перше, щоця теорема не підтверджує, взагалі, наявності розв'язків конгруенції n-го степеня за простим модулем р і, по-друге, для складених модуліввона зовсім несправедлива; наприклад, конгруенція першого степеня 16 x ≡32 (mod48), де (16, 48) = 16 і 32ділиться на 16, має шістнадцять розв'язків.
Висновок.Конгруенція
f(х)= а0хп + а1хп-1 +... + аn-1x +an ≡ 0 (mod p)
має більш як п-розв'язків тоді і тільки тоді, коли вона тотожна, тобто коли всі її коефіцієнтиділяться на р.
Справді, якщо коефіцієнтиданої конгруенції діляться на р, товона задовольняється будь-яким значенням х,тобто вона, тотожна, і число її розв'язків (яке дорівнює р) буде більш як п (бо ми скрізь передбачаємо степінь конгруенції не більший за р — 1).
Якщо а0не ділиться на р,то це конгруенція п-го степеня і затеоремою 5 вона має не більш як п розв'язків.Якщо ж а0ділиться на р, але a1 не ділиться на р,то степінь цієї конгруенції дорівнюватиме n— 1 і вона за тією самою теоремою має не більше п — 1, а тому й не більш як п,розв'язків. Так можна продовжувати далі, і якщо тільки не всі коефіцієнтиданої конгруенції діляться на р, точисло її розв'язків, очевидно, не може перевищувати п.2.3. Системиконгруенцій
Обмежимося системою конгруенцій:
a1x ≡b1 (mod m1); (a1, m1) = 1,
a2x ≡b2 (mod m2); (a2, m2) = 1,
………………………… (1)
akx≡bk (mod mk);(ak, mk) = 1,
з одним невідомим, але різними модулями.
Розв'язати яку-небудь систему конгруенцій з одним невідомим— це означає знайти такі цілі значенняневідомого х, які задовольняли б усіконгруенції даної системи. Якщо х ≡α за деяким модулем є розв'язком системи (1), то весь цей клас чиселприйматимемо за один розв'язок. Якщо дана система має хоч би один розв'язок, товона називається сумісною.
Насамперед, зауважимо, щорозв'язуючи окремо кожну з конгруенцій (1), врешті матимемо систему,еквівалентну даній:
x ≡ c1(mod m1),
x ≡ c2(mod m2),
……………. (2)
x ≡ ck(mod mk).
Отже, досить уміти розв'язувати систему конгруенцій (2).
Неважко показати, що коли система (2) сумісна, то вона має єдинийрозв'язок за модулем М, що дорівнює найменшому спільному кратному чисел m1,m2,…,mk.2.4. Зведенняконгруенцій за складеним модулем до системи конгруенцій за простими модулями
Теорема1. Якщо m1, m2, …, тk — попарно взаємно прості числа,то конгруенція
f(х)= а0хп + а1хп-1 +... + аn-1x +an ≡ 0 (mod m1 m2 ... mk) (1) еквівалентна системі конгруенцій:
f(x)≡ 0 (mod m1),
f(x)≡ 0 (mod m2), (2)
………………..
f(x)≡ 0 (mod m