Вступ
Важливе місце в курсі теорії чисел посідають конгруенції та, зокрема, конгруенції вищих степенів. Але до того як вони почали розглядатися, математики різних країн, протягом століть розглядали невизначені рівняння 1-го степеня.
Невизначені рівняння 1-го степеня почали розглядатися ще індуськими математиками приблизно з V століття. Деякі такі рівняння з двома і трьома невідомими з'явилися в зв'язку з проблемами, що виникли в астрономії, наприклад, при розгляді питань, зв'язаних з визначенням періодичного повторення небесних явищ.
У другому виданні книги французького математика Баше де Мезір’яка “Problemis plaisans 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 < m.
Якщо двом цілим числам a і bвідповідає одна і та сама остача r від ділення їх на m, то вони називаються конгруентними за модулем m. Це позначається символом:
a≡b(mod m) (1)
і читається: а конгруентне з bза модулем m.
Деякі автори позначають це коротше:
a≡b(m). (1′)
Співвідношення (1) або (1′) між числами називаються порівнянням, або конгруенцією.
Приклади. 48 ≡ 84 (mod 18);
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(mod m), то 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(mod m), або b=а + тt, де t — деяке ціле число, тобто, інакше кажучи, b = а + тt є загальний вигляд цілих чисел, які належать до того самого класу, що й а.
2.
Конгруенції з невідомою величиною
Як видно з наведеного нижче малюнку, конгруенції в теорії чисел поділяються на конгруенції за простим та за складеним модулями.
Види конгруенцій Рисунок |
2.1. Класи розв'язків конгруенції довільного степеня
Припустимо, що т — натуральне число. Конгруенція виду
f (x) ≡ 0(modm), (1)
де f(х)= а0
хп
+ а1
хп-1
+ . . . + аn-1
x + an
, є многочлен степеня n з цілими коефіцієнтами і а0
≠ 0 (modm) називається алгебраїчною конгруенцією п-го степеня з одним невідомим x.
Цілі значення х, що задовольняють конгруенцію (1), називаються коренями або розв'язками цієї конгруенції.
Розв'язати конгруенцію — це означає знайти всі значення невідомих, які її задовольняють.
Дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий розв'язок однієї конгруенції є розв’язком іншої.
Теорема 1. Якщо x = x1
задовольняє конгруенцію (1), то всяке число, яке належить до того самого класу лишків за модулем т , що й число x1
,також задовольняє цю конгруенцію, тобто розв'язком буде весь клас чисел
х ≡ х1
(mod т).
Це твердження безпосередньо випливає з властивостей конгруенцій. Справді, нехай х2
— будь-яке число, яке належить до того самого класу лишків за модулем т, що й х1
; тоді х2
≡ x1
(modm). За умовою х1
є розв'язок конгруенції (1), тобто має місце тотожна конгруенція f(x1
) ≡ 0 (modт), але тоді матиме місце й конгруенція f(x1
) ≡ 0 (modт), тобто x2
також буде розв'язком конгруенції. Оскільки x2
— будь-яке число класу х ≡ х1
(modт), то весь цей клас задовольнятиме дану конгруенцію.
Розв'язки конгруенції (1), що належать до одного класу чисел за модулем т, приймають за один розв'язок даної конгруенції. При цьому конгруенція (1) має стільки розв'язків, скільки класів чисел її задовольняють.
Приклад. Конгруенція
8x5
— 12x3
— 13x2
— 15x + 6 ≡ 0 (mod5)
є еквівалентною конгруенції
Зх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 (mod5),
як ми вище бачили, має один розв'язок: x ≡ 1 (mod5). Але, якщо обидві частини цієї конгруенції помножити на 5, то дістанемо конгруенцію:
5x4
+ 5х3
+ 5х2
+ 5х + 5 ≡ 0 (mod5),
розв'язком якої буде вже будь-яке ціле число. Вона, по суті,перетворюється в конгруенцію 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-1
x + an
≡ 0 (mod p), n≥1, (1)
де a0
≠0 (modp) і р — просте число.
Теорема 1. Конгруенцію (1) завжди можна так перетворити що її старший коефіцієнт дорівнюватиме одиниці.
Справді, через те що р — просте і a0
не ділиться на р, то завжди існує єдине число α, що а0
α ≡ 1 (modp). Помноживши тепер конгруенцію (1) на α і замінивши а0
x одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, що дорівнює одиниці:
xn
+ b1
xn
-1
+ .. + bn
-1
x + bn
≡ 0 (modp); (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 (modp) при будь-якому цілому х, тому дістанемо тотожну конгруенцію:
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 (modp) та справедлива при будь-якому цілому 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 (mod5) і
f(x) ≡ Зх3
+ Зх ≡ 0 (mod 5),
або
f(x) ≡ х2
+ 1 ≡ 0 (mod 5).
Очевидні розв'язки останньої конгруенції x ≡ 2, 3 (mod 5) будуть також і розв'язками даної конгруенції:
f(x) ≡ 0 (mod 5).
Теорема 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 (modp) тобто α1
— корінь конгруенції (1); отже, маємо такий висновок.
Висновок. Конгруенція (1) має корінь х = α1
тоді і тільки тоді, коли ліва її частина f(x) ділиться на х — α1
за даним модулем р.
Зауважимо, що теорема 3 і висновок з неї справедливі і для складеного модуля т.
Теорема 4. Якщо α1
, α2
, . . , αk
(k ≤n) є різні розв'язки конгруенції (1), то має місце тотожна конгруенція:
f(х) ≡ (х – α1
) (х - α2
) . . . (х - αk
) fk
(x) (modp), (3)
де степінь f (х) дорівнює п — k і старші коефіцієнти у f(x) і fk
(x) однакові.
Справді, згідно, з теоремою 3 конгруенція (1) еквівалентна конгруенції
(x - α1
)f1
(x) ≡ 0 (modp). (21
)
Через те що α2
є розв'язок конгруенції (1), то, підставляючи його в еквівалентну конгруенцію (2'), дістанемо тотожну конгруенцію:
(α2
— α1
)f1
(α2
) ≡ 0 (mod р).
Але добуток двох чи кількох чисел ділиться на просте число р тоді і тільки тоді, коли на р ділиться принаймні один з співмножників. За умовою α1
і α2
різні, тобто
α1
≠α2
(modp),
отже, α2
— α1
не ділиться на р, а тому f1
(α2
) ділиться на р, тобто f1
(α2
) ≡ 0 (mod p); останнє означає, що α2
— розв'язок конгруенції f1
(x)≡0 (mod p). За теоремою 3 дістанемо:
f1
(х)≡ (x-α2
)f2
(x) (modp);
звідки
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
) (modp). (4)
Справді, тут k= п, отже, степінь многочлена fn
(x) дорівнюватиме п-n=0, тобто fn
(х) = а0
.
2.2.1.
Ma
к
c
им
a
льн
e
число розв'язків
Теорема 5. Конгруенція п-го степеня за простим модулем не може мати більш як п різних розв'язків.
Справді, нехай β – який-небудь інший розв'язок, відмінний від α1
, α2
, . . , αn
, тобто
β≠αi
(modp) (i = 1, 2, … , n);
покладаючи тепер в тотожній конгруенції (4) х=β, знайдемо, що
a0
(β – α1
)(β – α2
) … (β - αn
) ≡ 0 (mod p), (4′)
але різниці β — αi
за умовою не діляться на р, тобто взаємно прості з р, а в такому разі і їх добуток буде взаємно простим з р. Звідси випливає, що має місце конгруенція (4'), тобто f(β) ≡ 0 (modp), тому а0
має ділитись на р, що суперечить умові, бо в нас a0
≠ 0 (modp).
Слід зауважити, по-перше, що ця теорема не підтверджує, взагалі, наявності розв'язків конгруенції n-го степеня за простим модулем р і, по-друге, для складених модулів вона зовсім несправедлива; наприклад, конгруенція першого степеня 16 x ≡32 (mod 48), де (16, 48) = 16 і 32 ділиться на 16, має шістнадцять розв'язків.
Висновок. Конгруенція
f(х)= а0
хп
+ а1
хп-1
+ . . . + аn-1
x + an
≡ 0 (modp)
має більш як п- розв'язків тоді і тільки тоді, коли вона тотожна, тобто коли всі її коефіцієнти діляться на р.
Справді, якщо коефіцієнти даної конгруенції діляться на р, то вона задовольняється будь-яким значенням х, тобто вона, тотожна, і число її розв'язків (яке дорівнює р) буде більш як п (бо ми скрізь передбачаємо степінь конгруенції не більший за р — 1).
Якщо а0
не ділиться на р, то це конгруенція п-го степеня і за теоремою 5 вона має не більш як п розв'язків. Якщо ж а0
ділиться на р, але a1
не ділиться на р, то степінь цієї конгруенції дорівнюватиме n — 1 і вона за тією самою теоремою має не більше п — 1, а тому й не більш як п, розв'язків. Так можна продовжувати далі, і якщо тільки не всі коефіцієнти даної конгруенції діляться на р, то число її розв'язків, очевидно, не може перевищувати п.
2.3. Системи конгруенцій
Обмежимося системою конгруенцій:
a1
x ≡b1
(mod m1
); (a1
, m1
) = 1,
a2
x ≡b2
(mod m2
); (a2
, m2
) = 1,
………………………… (1)
ak
x ≡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-1
x + an
≡ 0 (modm1
m2
. . . mk
) (1) еквівалентна системі конгруенцій:
f(x) ≡ 0 (mod m1
),
f(x) ≡ 0 (mod m2
), (2)
………………..
f(x) ≡ 0 (modmk
).
При цьому, позначаючи через
S1
, S2
, . . . , Sk
числа розв'язків окремих конгруенцій (2) за відповідними модулями і через S — число розв'язків конгруенції (1), матимемо:
S= S1
S2
. . . Sk
.
Перша частина твердження безпосередньо випливає з властивостей 8 і 7, п.1.1. Справді, припустимо α — розв'язок конгруенції (1), тобто
f(α) ≡ 0 (modm1
m2
. . . mk
),
а звідси і поготів
f(α) ≡ 0 (mod ті
),
тобто α — розв'язок будь-якої конгруенції системи (2).
Навпаки, якщо β — розв'язок системи конгруенцій (2), то матимуть місце тотожні конгруенції:
f(β) ≡ 0 (mod ті
) (i = 1, 2, … , k).
Але тоді (див. властивість 7, п.1.1) ця конгруенція матиме місце і за модулем, який дорівнює найменшому спільному кратному чисел m1
, m2
, … , тk
,, тобто, зважаючи на те, що вони попарно взаємно прості, за модулем m1
m2
. . . mk
:
f(β) ≡ 0 (modm1
m2
. . . mk
);
це означає, що β є також розв'язком конгруенції (1).
Друге твердження випливає з таких міркувань: припустимо, що
х ≡ αi
(modті
)
є будь-який розв'язок конгруенції
f(x) ≡ 0 (mod ті
),
тоді завжди можна знайти єдине число x1
, яке є розв'язком системи лінійних конгруенцій:
х ≡ α1
(modт1
),
х ≡ α2
(modт2
),
……………… (3)
х ≡ αk
(modтk
).
Це число x1
визначається за модулем т = m1
m2
... mk
; воно буде розв'язком системи (2), а отже, і конгруенції (1). Але, комбінуючи кожен розв'язок однієї конгруенції з системи (2) з кожним розв'язком решти конгруенцій, ми, очевидно, дістанемо S1
∙S2
…Sk
= S лінійних систем конгруенцій типу (3) і, через те що кожна така система має єдиний розв'язок, який є розв'язком як системи (2), так і конгруенції (1), то цим і доведено другу частину теореми.
Висновок 1. Якщо хоч одна з конгруенцій системи (2) не має розв'язків, то й дана конгруенція (2) також не матиме розв'язків.
Висновок 2. Дослідження і розв'язування конгруенції
f(x) ≡ 0 (mod т),
де т = — канонічний розклад модуля т — зводиться до дослідження і розв'язування конгруенцій:
f(x) ≡ 0 (mod)(і = 1, 2, ..., k).[2]
Це випливає з того, що числа , , ..., попарно взаємно прості.
Отже, все зводиться до того, що доводиться окремо досліджувати і розв'язувати конгруенції виду
f(x) ≡ 0 (mod), (4)
де p — просте число, α — ціле додатне число. Зауважимо, що всякий розв'язок конгруенції (4) буде розв'язком конгруенції
f(x) ≡ 0 (modp). (5)
Очевидно, якщо конгруенція (5) не має розв'язків, то й конгруенція (4) розв'язків не матиме. Справді, з припущення виходить, що при жодному цілому х не має місця конгруенція
f(x) ≡ 0 (modp),
тобто f(х) не ділиться на р, але тоді f(х) і поготів не ділитиметься на pα
, тобто
f(x) ≠ 0 (mod)
ні при якому цілому х.
Висновки
Розглянуто конгруенції, їх означення та основні властивості.
Також розглянуто класи чисел за даним модулем та класи розв’язків конгруенції довільного степеня.
Було звернено увагу на системи конгруенцій
Доведено цілий ряд теорем необхідних при розв’язуванні конгруенцій з невідомою величиною.
Розв’язано декілька прикладів;
Після доведення теорем, рішення прикладів та введення означень була отримана певна кількість висновків щодо тих чи інших операцій над конгруенціями.
Список литературы
Бородін О.І., Теорія чисел. “Радянська школа”, К., 1965. – 244с.
Бухштаб А.А., Теория чисел. Учпедгизд., М., 1960. – 375с.
Окунев Л.Я., Краткий курс теории чисел, Учебное пособие для пединститутов, М., 1956
Сушкевич А.К., Теорія чисел. Видавництво Харківського Державного Університета Імені А.М.Горького, Х.,1954.
Приложение
СХЕМА ГОРНЕРА
Pn
(x) = an
xn
+ an-1
xn-1
+ … + a1
x + a0
;
Pn-1
(x) = Sn-1
(x)(x – c) + R ;
Sn-1
(x) = bn-1
xn-1
+ bn-2
xn-2
+ …+b1
x + 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
;
Таблиця
СТРУКТУРНЕ ПРЕДСТАВЛЕННЯ СХЕМИ ГОРНЕРА
| an
|
an-1
|
an-2
|
……. | a0
|
|
| c | bn-1
|
bn-2
|
bn-3
|
……. | R |
[1]
Рівняння
a
0
xn
+a
1
xn-
1
+…+an-
1
x
+an
=pt
(*)
з цілими коефіцієнтами і p
>1 еквівалентне конгруенції (1). Внаслідок такої залежності задачу на розв’язання рівняння (*) в цілих числах можна замінити задачею про розв’язання конгруенції (1), що і застосовується в теорії чисел.
[2]
З цієї причини в теорії конгруенцій звичайно приймають, що модуль конгруенції – просте число або степінь простого числа.