Сравнения высших степеней - (реферат)
p>Зауваження. Можна вказане ділення на х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 (mod 5), тому x5-1 ? 1 (mod 5) і 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) (mod p).
При цьому кажуть, що 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)f 2(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-го степеня за простим модулем р і, по-друге, для складених модулів вона зовсім несправедлива; наприклад, конгруенція першого степеня 16x ? 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) еквівалентна системі конгруенцій: f(x) ? 0 (mod m1),
f(x) ? 0 (mod m2), (2) ………………...
f(x) ? 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 ті)
є будь-який розв'язок конгруенції
f(x) ? 0 (mod ті),
тоді завжди можна знайти єдине число x1, яке є розв'язком системи лінійних конгруенцій: х ? б1 (mod т1),
х ? б2 (mod т2),
……………… (3)
х ? бk (mod тk).
Це число x1 визначається за модулем т = m1m2 .... 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 (mod p). (5) Очевидно, якщо конгруенція (5) не має розв'язків, то й конгруенція (4) розв'язків не матиме. Справді, з припущення виходить, що при жодному ціломух не має місця конгруенція f(x) ? 0 (mod p),
тобто f(х) не ділиться на р, але тоді f(х) і поготів не ділитиметься на pб, тобто f(x) ? 0 (mod )
ні при якому цілому х.
ВИСНОВКИ
Розглянуто конгруенції, їх означення та основні властивості. Також розглянуто класи чисел за даним модулем та класи розв’язків конгруенції довільного степеня. Було звернено увагу на системи конгруенцій
Доведено цілий ряд теорем необхідних при розв’язуванні конгруенцій з невідомою величиною. Розв’язано декілька прикладів;
Після доведення теорем, рішення прикладів та введення означень була отримана певна кількість висновків щодо тих чи інших операцій над конгруенціями.
ЛІТЕРАТУРА
Бородін О. І. , Теорія чисел. “Радянська школа”, К. , 1965. – 244с. Бухштаб А. А. , Теория чисел. Учпедгизд. , М. , 1960. – 375с.
Окунев Л. Я. , Краткий курс теории чисел, Учебное пособие для пединститутов, М. , 1956
Сушкевич А. К. , Теорія чисел. Видавництво Харківського Державного Університета Імені А. М. Горького, Х. ,1954.
ДОДАТОК. СХЕМА ГОРНЕРА
Pn(x) = anxn + an-1xn-1 + … + a1x + a0 ;
Pn-1(x) = Sn-1(x)(x – c) + R ;
Sn-1(x) = 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 ;
Таблиця
СТРУКТУРНЕ ПРЕДСТАВЛЕННЯ СХЕМИ ГОРНЕРА
an
an-1
an-2
…….
a0
c
bn-1
bn-2
bn-3
…….
R
Шевчук М. Б. (Кіровоград, ДПУ)
КОНГРУЕНЦІЇ ВИЩИХ СТЕПЕНІВ
a ? b (mod m)
f (х)= а0хп + а1хп-1 + ... . +
+ аn-1x + an
f (x) ? 0(mod m)
f(x) = (xp—x)q(x) + r(x)
f (х) ? (х — б1) f1 (х) (mod р)
f (х) ? (х – б1) (х - б2) ґ ... . ґ
ґ (х - бk) fk (x) (mod p)
