6027-1 (675530), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

f (α) ≡ 0 (mod m).

Помножаючи обидві частини цієї конгруенції на k, дістанемо:

k∙f (α) ≡ 0 (mod m). (2)

Отже, ми бачимо, що α є розв'язком конгруенції

k∙f (x) ≡ 0 (mod m). (3)

Навпаки, якщо α — розв'язок конгруенції (3), тобто k∙f (α) ≡ 0 (mod m), тоді обидві частини конгруенції (2) можна скоротити на k, не змінюючи модуля, бо (k, m) = 1, (див. властивість 4, п.1.1), отже,

f (α) ≡ 0 (mod m),

тобто α є розв'язком конгруенції (1), що і доводить наше твердження.

Зауважимо, що при розв'язуванні конгруенцій з невідомою величиною можна, не змінюючи модуля, скорочувати обидві частини конгруенції тільки на такий їх спільний дільник, який є взаємно простий з модулем (див. властивість 4, п.1.1).

2.2. Конгруенції n-го степеня за простим модулем.

У попередньому параграфі ми бачили, що дослідження й розв'язання конгруенції п-го степеня (п≥1) зводиться кінець кінцем до дослідження і розв'язання відповідних конгруенцій за простими модулями. Тому зараз доведемо деякі загальні теореми, що стосуються конгруенцій n-го степеня за простим модулем р.

Припустимо, що задано конгруенцію¹:

f (х)= а₀х^п + а₁х^п-1 + . . . + а_n-1x + a_n ≡ 0 (mod p), n≥1, (1)

де a₀≠0 (mod p) і р — просте число.

Теорема 1. Конгруенцію (1) завжди можна так перетворити що її старший коефіцієнт дорівнюватиме одиниці.

Справді, через те що р — просте і a₀ не ділиться на р, то завжди існує єдине число α, що а₀α ≡ 1 (mod p). Помноживши тепер конгруенцію (1) на α і замінивши а₀x одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, що дорівнює одиниці:

xⁿ + b₁x^n-1+ .. + b_n-1x + b_n ≡ 0 (mod p); (1')

тут b_i ≡ a_iα (mod p).

Теорема 2. Якщо степінь конгруенції (1) не менший від модуля конгруенції, то вона еквівалентна деякій конгруенції степеня, не вище за р—1 (за тим самим модулем).

Справді, поділимо f(х) на х^р-х; і частку від ділення позначимо через q(x), а остачу через r(х). Тоді на підставі алгоритму ділення з остачею дістанемо:

f(x) = (x^p—x)q(x) + r(x),

де частка q(х) і остача r(х) будуть многочленами з цілими коефіцієнтами, причому степінь r(х) буде не вище р—1. За теоремою Ферма x^p—-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) ділиться на x^p—-x , тобто r(х) ≡ 0 (mod р) – тотожна конгруенція за модулем p, тобто остача при діленні конгруентна з нулем і дана конгруенція еквівалентна конгруенції 0 ≡ 0 (mod p) та справедлива при будь-якому цілому x. Далі, нехай остача від ділення f(х) на x^p—-x є многочлен нульового степеня, що дорівнює b_p-1. Якщо b_p-1 не ділиться на p, то дана конгруенція не має розв’язків, бо вона зводиться до невірної конгруенції :

b_p-1 ≡ 0 (mod p).

Приклад. Якій конгруенції нижче від 5-го степеня еквівалентна конгруенція:

f(х) = х¹⁷ + 2x¹¹ + Зx⁸ — 4x⁷ + 2x — 3 ≡ 0 (mod 5).

Поділивши f (х) на х⁵ — х і замінивши всі коефіцієнти остачі найменшими невід'ємними лишками за модулем 5, дістанемо, що дана конгруенція еквівалентна конгруенції

r(х) = Зx⁴ + Зx³ + Зx + 2 ≡ 0 (mod 5).

Зауваження. Можна вказане ділення на х^p — х фактично і не виконувати, а просто замінити хⁿ на х^r, де r > 0 є остача від ділення п на р — 1. Справді, за теоремою Ферма х^р ≡ х (mod р), звідси x^p+1 ≡ x², x^p+2 ≡ x³, ... і взагалі:

Через те що в нашому прикладі x¹⁷ можна замінити через х, а 2x¹¹ через 2x³, Зx⁸ через Зx⁴,—4x⁷ замінити через —4x³ ≡ x³ , тому відразу дістанемо:

f(x) ≡ Зx⁴ + Зx³ + Зx + 2 ≡ 0 (mod 5).

У свою чергу, останню конгруенцію можна спростити так: х ≠ 0 (mod 5), тому x^5-1 ≡ 1 (mod 5) і

f(x) ≡ Зх³ + Зх ≡ 0 (mod 5),

або

f(x) ≡ х² + 1 ≡ 0 (mod 5).

Очевидні розв'язки останньої конгруенції x ≡ 2, 3 (mod 5) будуть також і розв'язками даної конгруенції:

f(x) ≡ 0 (mod 5).

Теорема 3. Якщо α₁—який-небудь розв'язок конгруенції (1), то має місце тотожна конгруенція:

f (х) ≡ (х — α₁) f₁ (х) (mod р), (2)

де f₁(х) — многочлен степеня, на одиницю нижчий від степеня многочлена f(x). Старший коефіцієнт многочлена f₁(x) збігається з старшим коефіцієнтом даного многочлена fix).

Справді, поділимо f(x) на х — α₁ і частку позначимо через f₁(х), а остачу через r. За теоремою Безу r = f(α₁), але

f(α₁) ≡ 0 (mod p)

за умовою, тоді конгруенцію

f(x) = (x – α₁) f₁(x) + f(α₁) ≡ 0 (mod р)

можна переписати так:

f(x) ≡ (x-α₁)f₁(x) (mod p).

При цьому кажуть, що f(х) ділиться на х — α₁ за модулем р. Очевидно, що й навпаки: з конгруенції (2) випливає, що f(α₁) ≡ 0 (mod p) тобто α₁ — корінь конгруенції (1); отже, маємо такий висновок.

Висновок. Конгруенція (1) має корінь х = α₁ тоді і тільки тоді, коли ліва її частина f(x) ділиться на х — α₁ за даним модулем р.

Зауважимо, що теорема 3 і висновок з неї справедливі і для складеного модуля т.

Теорема 4. Якщо α₁, α₂, . . , α_k (k ≤ n) є різні розв'язки конгруенції (1), то має місце тотожна конгруенція:

f (х) ≡ (х – α₁) (х - α₂) . . . (х - α_k) f_k (x) (mod p), (3)

де степінь f (х) дорівнює п — k і старші коефіцієнти у f(x) і f_k(x) однакові.

Справді, згідно, з теоремою 3 конгруенція (1) еквівалентна конгруенції

(x - α₁)f₁(x) ≡ 0 (mod p). (2¹)

Через те що α₂ є розв'язок конгруенції (1), то, підставляючи його в еквівалентну конгруенцію (2'), дістанемо тотожну конгруенцію:

(α₂ — α₁)f₁(α₂) ≡ 0 (mod р).

Але добуток двох чи кількох чисел ділиться на просте число р тоді і тільки тоді, коли на р ділиться принаймні один з співмножників. За умовою α₁ і α₂ різні, тобто

α₁≠α₂ (mod p),

отже, α₂ — α₁ не ділиться на р, а тому f₁(α₂) ділиться на р, тобто f₁(α₂) ≡ 0 (mod p); останнє означає, що α₂ — розв'язок конгруенції f₁(x)≡0 (mod p). За теоремою 3 дістанемо:

f₁(х)≡ (x-α₂)f ₂(x) (mod p);

звідки

f(x)≡(x-α₁)(x-α₂)f₂(x) (mod p).

Аналогічно міркуючи, кінець кінцем прийдемо до тотожної конгруенції (3). З самого процесу одержання многочленів f₁(x), f₂(x),… f_k (x) видно, що старші коефіцієнти цих многочленів однакові і дорівнюють старшому коефіцієнтові a₀ многочлена f(x).

В и с н о в о к. Якщо конгруенція (1) п-го степеня за простим модулем р (п можна вважати не більшим за р — 1) має п різних розв'язків α₁, α₂, . . , α_n, то має місце тотожна конгруенція:

f(x) ≡ а₀ (х — α₁) (х — α₂) ... (х — α_n) (mod p). (4)

Справді, тут k = п, отже, степінь многочлена f_n(x) дорівнюватиме п-n=0, тобто f_n (х) = а₀.

2.2.1.Maкcимaльнe число розв'язків

Теорема 5. Конгруенція п-го степеня за простим модулем не може мати більш як п різних розв'язків.

Справді, нехай β – який-небудь інший розв'язок, відмінний від α₁, α₂, . . , α_n, тобто

β≠α_i (mod p) (i = 1, 2, … , n);

покладаючи тепер в тотожній конгруенції (4) х=β, знайдемо, що

a₀(β – α₁)(β – α₂) … (β - α_n) ≡ 0 (mod p), (4′)

але різниці β — α_i за умовою не діляться на р, тобто взаємно прості з р, а в такому разі і їх добуток буде взаємно простим з р. Звідси випливає, що має місце конгруенція (4'), тобто f(β) ≡ 0 (mod p), тому а₀ має ділитись на р, що суперечить умові, бо в нас a₀ ≠ 0 (mod p).

Слід зауважити, по-перше, що ця теорема не підтверджує, взагалі, наявності розв'язків конгруенції n-го степеня за простим модулем р і, по-друге, для складених модулів вона зовсім несправедлива; наприклад, конгруенція першого степеня 16 x ≡32 (mod 48), де (16, 48) = 16 і 32 ділиться на 16, має шістнадцять розв'язків.

Висновок. Конгруенція

f (х)= а₀х^п + а₁х^п-1 + . . . + а_n-1x + a_n ≡ 0 (mod p)

має більш як п- розв'язків тоді і тільки тоді, коли вона тотожна, тобто коли всі її коефіцієнти діляться на р.

Справді, якщо коефіцієнти даної конгруенції діляться на р, то вона задовольняється будь-яким значенням х, тобто вона, тотожна, і число її розв'язків (яке дорівнює р) буде більш як п (бо ми скрізь передбачаємо степінь конгруенції не більший за р — 1).

Якщо а₀ не ділиться на р, то це конгруенція п-го степеня і за теоремою 5 вона має не більш як п розв'язків. Якщо ж а₀ ділиться на р, але a₁ не ділиться на р, то степінь цієї конгруенції дорівнюватиме n — 1 і вона за тією самою теоремою має не більше п — 1, а тому й не більш як п, розв'язків. Так можна продовжувати далі, і якщо тільки не всі коефіцієнти даної конгруенції діляться на р, то число її розв'язків, очевидно, не може перевищувати п.

2.3. Системи конгруенцій

О бмежимося системою конгруенцій:

a₁x ≡b₁ (mod m₁); (a₁, m₁) = 1,

a₂x ≡b₂ (mod m₂); (a₂, m₂) = 1,

………………………… (1)

a_kx ≡b_k (mod m_k); (a_k, m_k) = 1,

з одним невідомим, але різними модулями.

Розв'язати яку-небудь систему конгруенцій з одним невідомим— це означає знайти такі цілі значення невідомого х, які задовольняли б усі конгруенції даної системи. Якщо х ≡ α за деяким модулем є розв'язком системи (1), то весь цей клас чисел прийматимемо за один розв'язок. Якщо дана система має хоч би один розв'язок, то вона називається сумісною.

Насамперед, зауважимо, що розв'язуючи окремо кожну з конгруенцій (1), врешті матимемо систему, еквівалентну даній:

x ≡ c₁ (mod m₁),

x ≡ c₂ (mod m₂),

……………. (2)

x ≡ c_k (mod m_k).

Отже, досить уміти розв'язувати систему конгруенцій (2).

Неважко показати, що коли система (2) сумісна, то вона має єдиний розв'язок за модулем М, що дорівнює найменшому спільному кратному чисел m₁, m₂,… ,m_k.

2.4. Зведення конгруенцій за складеним модулем до системи конгруенцій за простими модулями

Теорема 1. Якщо m₁, m₂, … , т_k — попарно взаємно прості числа, то конгруенція

f (х)= а₀х^п + а₁х^п-1 + . . . + а_n-1x + a_n ≡ 0 (mod m₁ m₂ . . . m_k) (1) еквівалентна системі конгруенцій:

f(x) ≡ 0 (mod m₁),

f(x) ≡ 0 (mod m₂), (2)

………………..

f(x) ≡ 0 (mod m_k).

При цьому, позначаючи через

S₁, S₂ , . . . , S_k

числа розв'язків окремих конгруенцій (2) за відповідними модулями і через S — число розв'язків конгруенції (1), матимемо:

S = S₁S₂ . . . S_k .

Перша частина твердження безпосередньо випливає з властивостей 8 і 7, п.1.1. Справді, припустимо α — розв'язок конгруенції (1), тобто

f(α) ≡ 0 (mod m₁ m₂ . . . m_k),

а звідси і поготів

f(α) ≡ 0 (mod т_і),

тобто α — розв'язок будь-якої конгруенції системи (2).

Навпаки, якщо β — розв'язок системи конгруенцій (2), то матимуть місце тотожні конгруенції:

f(β) ≡ 0 (mod т_і) (i = 1, 2, … , k).

Але тоді (див. властивість 7, п.1.1) ця конгруенція матиме місце і за модулем, який дорівнює найменшому спільному кратному чисел m₁, m₂, … , т_k,, тобто, зважаючи на те, що вони попарно взаємно прості, за модулем m₁m₂ . . . m_k :

f(β) ≡ 0 (mod m₁ m₂ . . . m_k);

Характеристики

Список файлов реферата