Сравнения высших степеней

Шевчук М.Б. Конгруенц вищих степенв Кровоград 2001 МНСТЕРСТВО ОСВТИ НАУКИ УКРАНИ МОНУ КРОВОГРАДСЬКИЙ ДЕРЖАВНИЙ ПЕДАГОГЧНИЙ УНВЕРСИТЕТ м. В.ВИННИЧЕНКА КДПУ Кафедра математики Узгоджено Затверджено УДК 511.2 нв. 24.33.Р.М.2001 РЕФЕРАТ з математики студента 33 групи фзико-математичного факультету

Шевчука Максима Борисовича на темуКОНГРУЕНЦ ВИЩИХ СТЕПЕНВ Науковий кервникдоцент кафедри Ганжеланформатики, кандидат ванфзико-математичних наукПилипович Кровоград 2001 ЗВТ студента 33 групи Шевчука М.Б. про вдвдування семнару Математика, застосування та викладання, який вдбувся 6 грудня 2001 року о 14.00 в аудитор 204. Семнар вдвдали студенти 33, 36, 37 груп фзико-математичного факультету

КДПУ м. В.Винниченка 30 чоловк прослухали доповдь професора Волкова Ю Розподли степеневих рядв з полномальними коварацями, який розпочав свою доповдь з сторично довдки про походження абсолютно монотонних функцй. Псля цього доповдач познайомив аудиторю з такими поняттями, як випадков величини, ймоврнсть значень, арифметичний та визначений розподли ряду. Розповв про те, що розподл потрбен для визначення тих чи

нших подй та х характеристики , вперше ввв це поняття вчений Noak у 1950р. Дал розмова пшла про бномальний розподл, генератрису, математичне сподвання, рзн розгляди параметризац, дисперсю, тврну функц, параметричн смейства та н. Завершенням виступу Волкова Ю було демонстрування його робт та публкац. По завершенню доповд, професор, Флер З.Ю задав деклька питань, на як доповдач сформулював конкретн

грунтовн вдповд. Роботу виконано успшно, слд вдзначити високу теоретичну та практичну пдготовку. 11 грудня 2001 року студент 33 групи фзико-математичного факультету Шевчук М.Б. АНОТАЦЯ Стор. 24 , рис. 1 , табл. 1 , бблогр. 4 КОНГРУЕНЦЯ, ВЛАСТИВСТЬ, КЛАС, МОДУЛЬ , СТЕПНЬ, РОЗВ ЯЗОК В робот розглянуто означення, основн вдомост про конгруенц n-го степеня, х властивост д над ними,

та зроблено вдповдн висновки. Також розглядаються класи чисел за даним модулем та класи розв язкв конгруенц довльного степеня. Вводиться поняття системи конгруенцй та доводиться теорема про зведення конгруенцй за складним модулем до системи конгруенцй за простими модулями. Матерал роботи може бути використаний при вивченн курсу алгебри в школ на факультативних заняттях. ЗМСТ ВСТУП 1.КОНГРУЕНЦ КЛАСИ 1. Конгруенц та х основн властивост -

2. Класи за даним модулем 2.КОНГРУЕНЦ З НЕВДОМОЮ ВЕЛИЧИНОЮ 1. Класи розвязкв конгруенц довльного степеня - 2. Конгруенц n-го степеня за простим модулем. 1.Maкcимaльнe число розвязкв 3. Системи конгруенцй 4. Зведення конгруенцй за складеним модулем до системи конгруенцй за простими модулями 20 ВИСНОВКИ 23 ЛТЕРАТУРА 24 ДОДАТОК. СХЕМА

ГОРНЕРА 25 ВСТУП Важливе мсце в курс теор чисел посдають конгруенц та, зокрема, конгруенц вищих степенв. Але до того як вони почали розглядатися, математики рзних кран, протягом столть розглядали невизначен рвняння 1-го степеня. Невизначен рвняння 1-го степеня почали розглядатися ще ндуськими математиками приблизно з V столття. Деяк так рвняння з двома трьома невдомими зявилися в звязку з проблемами, що виникли в астроном, наприклад, при розгляд питань, звязаних з визначенням перодичного повторення небесних

явищ. У другому виданн книги французького математика Баше де Мезр яка Problemis plaisans et delectables que se font par les nombres, що вийшли в 1624 р зважуться невизначене рвняння axbyc. Баше де Мезр як фактично застосову процес, що зводить до послдовного обчислення не повних часток розгляду придатних дробв однак вн не розглядав неперервних дробв як таких. Популярний твр Баше де Мезр яка дуже вплинув на розвиток теор чисел, так як сприяв виникненню нтересу

до ц област математики. Ланцюгов дроби до ршення таких рвнянь були застосован Лагранжем, котрий, однак, зауважу, що фактично це той же спосб, що був даний Баше де Мезр яком ншими математиками, що розглядали невизначен рвняння до нього. Невизначен рвняння 1-го степеня стали записуватися й розвязуватися у форм порвняння значно пзнше, починаючи з Гауса. Вн вперше систематизував теорю та визначив поняття конгруенц, в свой книз

Disquisitiones arithmeticae Дослдження з арифметики. Задач, що зводяться до розгляду системи порвнянь 1-го степеня, розглядалися в арифметиц китайського математика Сун Тзу, що жив приблизно на початку нашо ери. У нього як у цлого ряду китайських, ндуських, арабських вропейських учених, що виршували так задач псля нього, питання ставився в наступнй форм знайти число, що да задан остач вд длення на задан числа.

Робота Сун Тзу стала вдомою в вроп в 1852 р. Незалежно вд китайських математикв спосб ршення задач такого роду був даний ндуським математиком Брамегупта 588-660. Система n порвнянь з n невдомими вивчалася Гаусом. Повне дослдження систем лнйних конгруенцй було подано в роботах Фробенуса й Стейнца наприкнц XIX столття. так конгруенц вищих степенв були покладен в основу модулярного

представлення числа, яке широко використовуться в сучаснй криптограф, що досить актуальна в наш час високих технологй. Велику увагу цьому питанню придлили так вчен-дослдники як Рверс, Адельман та Ширман. 1.КОНГРУЕНЦ КЛАСИ Ряд чисел при дленн на одне те саме число дають одну ту ж саму остачу. Поста питання про те, як можна використати цю особливсть як властивост вона ма. Вдповдь на нього конгруенц. 1. Конгруенц та х основн властивост

Припустимо, що m натуральне число розглядатимемо цл числа в звязку з остачами вд длення х на дане натуральне т, яке називають модулем. Згдно з теоремою про длення з остачею кожному числу а вдповдатиме певна остача r вд длення а на r amqr, 0 r m. Якщо двом цлим числам a b вдповда одна та сама остача r вд длення х на m, то вони називаються конгруентними за модулем m. Це позначаться символом abmod m 1 читаться а конгруентне з b за модулем m.

Деяк автори позначають це коротше abm. 1 Спввдношення 1 або 1 мж числами називаються порвнянням, або конгруенцю. Приклади. 48 84 mod 18 131 1 mod 13 10 1 mod 11. Конгруенц мають багато властивостей, подбних до властивостей рвностей. Властивсть 1. Для конгруенцй справджуються три основн закони рвностей рефлексивност, симетр транзитивност, тобто вдповдно а aamod m, б з конгруенц abmod m виплива, що bamod m в якщо abmod m bcmod m, то acmod

m. Властивсть 2. Конгруенц за одним тим же модулем можна почленно додавати або вднмати. Висновок 1. Доданок, що стоть в якй-небудь частин конгруенц, можна переносити в ншу частину, змнивши знак на протилежний. Висновок 2. Можна додати до обох частин або вдняти вд обох частин конгруенц одне те саме число. Висновок 3. До кожно частини конгруенц можна додати або вдняти вд не довльне число, кратне модулев. Властивсть 3. Конгруенц за одним тим самим модулем можна почленно перемножувати.

Висновок 1. Обидв частини конгруенц можна помножити на одне й те саме цле число. Висновок 2. Обидв частини конгруенц можна пдносити до одного того самого цлого невдмного степеня, тобто, якщо abmod m, то anbnmod m, де n цле 0. Властивсть 4. Обидв чистини конгруенц можна подлити на х спльний дльник, якщо вн взамно простий з модулем. Властивсть 5. Обидв частини конгруенц модуль можна помножити на одне те саме натуральне число.

Властивсть 6. Обидв частини конгруенц модуль можна подлити на будь-якого х спльного дльника. Властивсть 7. Якщо конгруенця ма мсце за клькома модулями, то вона матиме мсце за модулем, що дорвню х найменшому спльному кратному. Властивсть 8. Якщо конгруенця ма мсце за модулем m, то вона матиме мсце за будь-яким дльником d цього модуля Властивсть 9. Якщо одна частина конгруенц модуль дляться на яке-небудь цле число, то друга частина конгруенц ма длитись

на це число. Властивсть 10. Числа а b, конгруентн мж собою за модулем т, мають з ним одного того самого найбльшого спльного дльника. 1.2. Класи за даним модулем Взьмемо деяке натуральне число т при дленн на т, будь-яких цлих чисел можна дстати тльки т рзних невдмних остач, а саме 0, 1,2, , т-1. Отже, множина всх цлих чисел розбться на т класв чисел, що не перетинаються при цьому числа, як при дленн на т, даватимуть одну ту саму остачу r 0 r т, тобто числа, конгруентн

за модулем т, утворюють клас чисел за модулем т. з сказаного виплива, що всм числам даного класу вдповда одна та сама остача r отже, дстанемо вс числа цього класу, якщо в форм mqr, де r стале, припустимо, що q набира значення всх цлих чисел. З означення конгруентност двох чисел а b за модулем т з щойно сказаного вдразу ж виплива таке твердження. Два цлих числа а b тод тльки тод належать до одного класу за модулем т, коли вони конгруентн за цим модулем Позначимо через

C0 клас чисел, як дляться на т через C1 клас чисел, як при дленн на т дають в остач 1, т. д. нарешт, через Cm-1 клас чисел, як при дленн на т дають в остач т-1. Будь-яке число даного класу називаться лишком, або представником цього класу. Отже, якщо число a представником деякого класу за модулем т, то будь-яке нше число b цього класу задовольня умову bamod m, або bа тt, де t деяке цле число, тобто, накше кажучи, b а тt загальний вигляд цлих чисел,

як належать до того самого класу, що й а. 2.КОНГРУЕНЦ З НЕВДОМОЮ ВЕЛИЧИНОЮ Як видно з наведеного нижче малюнку, конгруенц в теор чисел подляються на конгруенц за простим та за складеним модулями. Види конгруенцй Рисунок 2.1. Класи розвязкв конгруенц довльного степеня Припустимо, що т натуральне число. Конгруенця виду f x 0mod m,

1 де f х а0хп а1хп-1 аn-1x an, многочлен степеня n з цлими коефцнтами а0 0 mod m називаться алгебрачною конгруенцю п-го степеня з одним невдомим x. Цл значення х, що задовольняють конгруенцю 1, називаються коренями або розвязками ц конгруенц. Розвязати конгруенцю це означа знайти вс значення невдомих, як задовольняють. Дв конгруенц з одним невдомим називаються екввалентними, якщо всякий розвязок одн конгруенц розв язком ншо. Теорема 1. Якщо x x1 задовольня конгруенцю 1, то всяке число, яке належить до того самого

класу лишкв за модулем т , що й число x1, також задовольня цю конгруенцю, тобто розвязком буде весь клас чисел х х1mod т. Це твердження безпосередньо виплива з властивостей конгруенцй. Справд, нехай х2 будь-яке число, яке належить до того самого класу лишкв за модулем т, що й х1 тод х2 x1mod m. За умовою х1 розвязок конгруенц 1, тобто ма мсце тотожна конгруенця fx1 0 mod т, але тод матиме мсце й конгруенця fx1 0 mod т, тобто x2 також буде розвязком конгруенц.

Оскльки x2 будь-яке число класу х х1mod т, то весь цей клас задовольнятиме дану конгруенцю. Розвязки конгруенц 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 задану конгруенцю не задовольняють. При дальшому випробуванн можна скористатись схемою Горнера Див. Додаток з тю тльки вдмннстю, що для полегшення кожного разу можна вдкидати числа, кратн модулю. 3032012361502494-236 -1502-494 Отже, конгруенця

Зх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, дстанемо kf б 0 mod m. 2 Отже, ми бачимо, що б розвязком конгруенц kf x 0 mod m.

3 Навпаки, якщо б розвязок конгруенц 3, тобто kf б 0 mod m, тод обидв частини конгруенц 2 можна скоротити на k, не змнюючи модуля, бо k, m 1, див. властивсть 4, п.1.1, отже, f б 0 mod m, тобто б розвязком конгруенц 1, що доводить наше твердження. Зауважимо, що при розвязуванн конгруенцй з невдомою величиною можна, не змнюючи модуля, скорочувати обидв частини конгруенц тльки на такий х спльний дльник, який взамно простий з модулем див. властивсть 4, п.1.1. 2.2. Конгруенц n-го степеня за простим модулем.

У попередньому параграф ми бачили, що дослдження й розвязання конгруенц п-го степеня п1 зводиться кнець кнцем до дослдження розвязання вдповдних конгруенцй за простими модулями. Тому зараз доведемо деяк загальн теореми, що стосуються конгруенцй n-го степеня за простим модулем р. Припустимо, що задано конгруенцю Рвняння a0xna1xn-1an-1xanpt з цлими коефцнтами p 1 екввалентне конгруенц 1. Внаслдок тако залежност задачу на розв язання рвняння в цлих числах можна замнити задачею про розв язання

конгруенц 1, що застосовуться в теор чисел. f х а0хп а1хп-1 аn-1x an 0 mod p, n1, 1 де a00 mod p р просте число. Теорема 1. Конгруенцю 1 завжди можна так перетворити що старший коефцнт дорвнюватиме одиниц. Справд, через те що р просте a0 не длиться на р, то завжди сну дине число б, що а0б 1 mod p. Помноживши тепер конгруенцю 1 на б замнивши а0x одиницею, дстанемо екввалентну конгруенцю з старшим коефцнтом, що дорвню одиниц xn b1xn-1 bn-1x bn 0 mod p 1 тут bi aiб mod p.

Теорема 2. Якщо степнь конгруенц 1 не менший вд модуля конгруенц, то вона екввалентна деякй конгруенц степеня, не вище за р 1 за тим самим модулем. Справд, подлимо fх на хр-х частку вд длення позначимо через qx, а остачу через rх. Тод на пдстав алгоритму длення з остачею дстанемо fx xp xqx rx, де частка qх остача rх будуть многочленами з цлими коефцнтами, причому степнь rх буде не вище р 1. За теоремою Ферма xp -x 0 mod p при будь-якому цлому х, тому дстанемо тотожну конгруенцю fх rx mod р.

Ця тотожна конгруенця показу, що корен конгруенц 1 конгруенц rх0 mod р однаков. Оскльки хр х завжди длиться на p, то fx rx можуть длитись на p тльки одночасно отже, конгруенц fх 0 mod р rх 0 mod р екввалентн. Через те що степнь rx менше за p, то теорему доведено. Зокрема, може статись, що fx длиться на xp -x , тобто rх 0 mod р тотожна конгруенця за модулем p, тобто остача при дленн конгруентна з нулем дана конгруенця екввалентна конгруенц 0 0 mod p та справедлива

при будь-якому цлому x. Дал, нехай остача вд длення fх на xp -x многочлен нульового степеня, що дорвню bp-1. Якщо bp-1 не длиться на p, то дана конгруенця не ма розв язкв, бо вона зводиться до неврно конгруенц bp-1 0 mod p. Приклад. Якй конгруенц нижче вд 5-го степеня екввалентна конгруенця fх х17 2x11 Зx8 4x7 2x 3 0 mod 5. Подливши f х на х5 х замнивши вс коефцнти остач найменшими невдмними лишками за модулем 5, дстанемо, що дана конгруенця екввалентна конгруенц rх

Зx4 Зx3 Зx 2 0 mod 5. Зауваження. Можна вказане длення на хp х фактично не виконувати, а просто замнити хn на хr, де r 0 остача вд длення п на р 1. Справд, за теоремою Ферма хр х mod р, звдси xp1 x2, xp2 x3, взагал Через те що в нашому приклад x17 можна замнити через х, а 2x11 через 2x3, Зx8 через Зx4, 4x7 замнити через 4x3 x3 , тому вдразу дстанемо fx Зx4 Зx3 Зx 2 0 mod 5. У свою чергу, останню конгруенцю можна спростити так х 0 mod 5, тому x5-1 1 mod 5

fx Зх3 Зх 0 mod 5, або fx х2 1 0 mod 5. Очевидн розвязки останньо конгруенц x 2, 3 mod 5 будуть також розвязками дано конгруенц fx 0 mod 5. Теорема 3. Якщо б1 який-небудь розвязок конгруенц 1, то ма мсце тотожна конгруенця f х х б1 f1 х mod р, 2 де f1х многочлен степеня, на одиницю нижчий вд степеня многочлена fx. Старший коефцнт многочлена f1x збгаться з старшим коефцнтом даного многочлена fix. Справд, подлимо fx на х б1 частку позначимо через f1х, а остачу через r.

За теоремою Безу r fб1, але fб1 0 mod p за умовою, тод конгруенцю fx x б1 f1x fб1 0 mod р можна переписати так fx x-б1f1x mod p. При цьому кажуть, що fх длиться на х б1 за модулем р. Очевидно, що й навпаки з конгруенц 2 виплива, що fб1 0 mod p тобто б1 корнь конгруенц 1 отже, мамо такий висновок. Висновок. Конгруенця 1 ма корнь х б1 тод тльки тод, коли лва частина fx длиться на х б1 за даним модулем р. Зауважимо, що теорема 3 висновок з не справедлив для складеного модуля т.

Теорема 4. Якщо б1, б2 бk k n рзн розвязки конгруенц 1, то ма мсце тотожна конгруенця f х х б1 х - б2 х - бk fk x mod p, 3 де степнь f х дорвню п k старш коефцнти у fx fkx однаков. Справд, згдно, з теоремою 3 конгруенця 1 екввалентна конгруенц x - б1f1x 0 mod p. 21 Через те що б2 розвязок конгруенц 1, то, пдставляючи його в екввалентну конгруенцю 2, дстанемо тотожну конгруенцю б2 б1f1б2 0 mod р. Але добуток двох чи клькох чисел длиться на просте число р тод тльки тод,

коли на р длиться принаймн один з спвмножникв. За умовою б1 б2 рзн, тобто б1б2 mod p, отже, б2 б1 не длиться на р, а тому f1б2 длиться на р, тобто f1б2 0 mod p останн означа, що б2 розвязок конгруенц f1x0 mod p. За теоремою 3 дстанемо f1х x-б2f 2x mod p звдки fxx-б1x-б2f2x mod p. Аналогчно мркуючи, кнець кнцем прийдемо до тотожно конгруенц 3. З самого процесу одержання многочленв f1x, f2x, fk x видно, що старш коефцнти цих многочленв однаков

дорвнюють старшому коефцнтов a0 многочлена fx. В и с н о в о к. Якщо конгруенця 1 п-го степеня за простим модулем р п можна вважати не бльшим за р 1 ма п рзних розвязкв б1, б2 бn, то ма мсце тотожна конгруенця fx а0 х б1 х б2 х бn mod p. 4 Справд, тут k п, отже, степнь многочлена fnx дорвнюватиме п-n0, тобто 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 mod 48, де 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 екввалентна систем конгруенцй fx 0 mod m1, fx 0 mod m2, 2 fx 0 mod mk. При цьому, позначаючи через S1, S2 Sk числа розвязкв окремих конгруенцй 2 за вдповдними модулями через S число розвязкв конгруенц 1, матимемо S S1S2 Sk .

Перша частина твердження безпосередньо виплива з властивостей 8 7, п.1.1. Справд, припустимо б розвязок конгруенц 1, тобто fб 0 mod m1 m2 mk, а звдси поготв fб 0 mod т, тобто б розвязок будь-яко конгруенц системи 2. Навпаки, якщо в розвязок системи конгруенцй 2, то матимуть мсце тотожн конгруенц fв 0 mod т i 1, 2 k. Але тод див. властивсть 7, п.1.1 ця конгруенця матиме мсце за модулем, який дорвню найменшому спльному кратному чисел m1, m2 тk тобто, зважаючи на те, що вони

попарно взамно прост, за модулем m1m2 mk fв 0 mod m1 m2 mk це означа, що в також розвязком конгруенц 1. Друге твердження виплива з таких мркувань припустимо, що х бi mod т будь-який розвязок конгруенц fx 0 mod т, тод завжди можна знайти дине число x1, яке розвязком системи лнйних конгруенцй х б1 mod т1, х б2 mod т2, 3 х бk mod тk. Це число x1 визначаться за модулем т m1m2 mk воно буде розвязком системи 2, а отже, конгруенц 1. Але, комбнуючи кожен розвязок одн конгруенц з системи 2 з кожним розвязком решти

конгруенцй, ми, очевидно, дстанемо S1S2Sk S лнйних систем конгруенцй типу 3 , через те що кожна така система ма диний розвязок, який розвязком як системи 2, так конгруенц 1, то цим доведено другу частину теореми. Висновок 1. Якщо хоч одна з конгруенцй системи 2 не ма розвязкв, то й дана конгруенця 2 також не матиме розвязкв. Висновок 2. Дослдження розвязування конгруенц fx 0 mod т, де т канончний розклад модуля т зводиться до дослдження розвязування конгруенцй fx 0 mod 1, 2, k.

З ц причини в теор конгруенцй звичайно приймають, що модуль конгруенц просте число або степнь простого числа. Це виплива з того, що числа попарно взамно прост. Отже, все зводиться до того, що доводиться окремо дослджувати розвязувати конгруенц виду fx 0 mod , 4 де p просте число, б цле додатне число. Зауважимо, що всякий розвязок конгруенц 4 буде розвязком конгруенц fx 0 mod p. 5 Очевидно, якщо конгруенця 5 не ма розвязкв, то й конгруенця 4 розвязкв не матиме.

Справд, з припущення виходить, що при жодному цлому х не ма мсця конгруенця fx 0 mod p, тобто fх не длиться на р, але тод fх поготв не длитиметься на pб, тобто fx 0 mod н при якому цлому х. ВИСНОВКИ 1. Розглянуто конгруенц, х означення та основн властивост. 2. Також розглянуто класи чисел за даним модулем та класи розв язкв конгруенц довльного степеня. 3. Було звернено увагу на системи конгруенцй 4. Доведено цлий ряд теорем необхдних при розв язуванн

конгруенцй з невдомою величиною. 5. Розв язано деклька прикладв 6. Псля доведення теорем, ршення прикладв та введення означень була отримана певна кльксть висновкв щодо тих чи нших операцй над конгруенцями. ЛТЕРАТУРА 1. Бородн О Теоря чисел. Радянська школа, К 1965. 244с. 2. Бухштаб А.А Теория чисел. Учпедгизд М 1960. 375с.

3. Окунев Л.Я Краткий курс теории чисел, Учебное пособие для пединститутов, М 1956 4. Сушкевич А.К Теоря чисел. Видавництво Харквського Державного Унверситета мен А.М.Горького, Х 1954. ДОДАТОК. СХЕМА ГОРНЕРА Pnx anxn an-1xn-1 a1x a0 Pn-1x Sn-1xx c R Sn-1x bn-1xn-1 bn-2xn-2 b1x b0 x c an bn-1 bn-1 an an-1 bn-2 cbn-1 bn-2 an-1 cbn-1 an-2 bn-3 cbn-2

bn-3 an-2 cbn-2 a0 R cb0 R a0 cb0 Таблиця СТРУКТУРНЕ ПРЕДСТАВЛЕННЯ СХЕМИ ГОРНЕРА anan-1an-2.a0cbn-1bn-2bn-3.R Шевчук М.Б. Кровоград, ДПУ КОНГРУЕНЦ ВИЩИХ СТЕПЕНВ a b mod m f х а0хп а1хп-1 аn-1x an f x 0mod m fx xp xqx rx f х х б1 f1 х mod р f х х б1 х - б2 х - бk fk x mod p