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

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);

це означає, що β є також розв'язком конгруенції (1).

Друге твердження випливає з таких міркувань: припустимо, що

х ≡ α_i (mod т_і)

є будь-який розв'язок конгруенції

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

тоді завжди можна знайти єдине число x₁, яке є розв'язком системи лінійних конгруенцій:

х ≡ α₁ (mod т₁),

х ≡ α₂ (mod т₂),

……………… (3)

х ≡ α_k (mod т_k).

Це число x₁ визначається за модулем т = m₁m₂ ... m_k; воно буде розв'язком системи (2), а отже, і конгруенції (1). Але, комбінуючи кожен розв'язок однієї конгруенції з системи (2) з кожним розв'язком решти конгруенцій, ми, очевидно, дістанемо S₁∙S₂…S_k = 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.

Приложение

СХЕМА ГОРНЕРА

P_n(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀ ;

P_n-1(x) = S_n-1(x)(x – c) + R ;

S_n-1(x) = b_n-1x^n-1 + b_n-2x^n-2 + …+b₁x + b₀ ;

(x – c);

a_n = b_n-1 ; b_n-1 = a_n ;

a_n-1 = b_n-2 – cb_n-1 ; b_n-2 = a_n-1 + cb_n-1 ;

a_n-2 = b_n-3 – cb_n-2 ; b_n-3 = a_n-2 + cb_n-2 ;

…………………  …………………

a₀ = R – cb₀ ; R = a₀ + cb₀ ;

Таблиця

СТРУКТУРНЕ ПРЕДСТАВЛЕННЯ СХЕМИ ГОРНЕРА

	an	an-1	an-2	…….	a0
c	bn-1	bn-2	bn-3	…….	R

[1] Рівняння

a₀xⁿ+a₁x^n-1+…+a_n-1x+a_n=pt (*)

з цілими коефіцієнтами і p>1 еквівалентне конгруенції (1). Внаслідок такої залежності задачу на розв’язання рівняння (*) в цілих числах можна замінити задачею про розв’язання конгруенції (1), що і застосовується в теорії чисел.

[2] З цієї причини в теорії конгруенцій звичайно приймають, що модуль конгруенції – просте число або степінь простого числа.