Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

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 (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),

Рекомендуем скачать другие рефераты по теме: шпаргалки по гражданскому, організація реферат.





Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата