10. Конгруенції 1-го степеня з одним невідомим у кільці цілих чисел.

Конгруенцією з одним невідомим за модулем m називається конгруенція виду

f(x)=a_nxⁿ+a_n-1x^n-1+…+a₁x+ a₀≡0(mod m)

числа a_i є Z, i=0…n.

Якщо a_n не ділиться націло на m , то степінь n називається степенем конгруенції. Якщо a_n ділиться націло на m то конгруенція має степінь < n.

Розв’язком конгруенції з одним невідомим називається ціле число α при підстановці якого у дану конгруенцію одержимо вірну числову конгруенцію f(α)≡0(mod m)

Зрозуміло, що разом з α дану конгруенцію задовольняє будь-яке число β=α+mt, що належить тому ж класу лишків, що і α, тобто розв’язком даної конгруенції є цілий клас лишків . Знайти розв’язки даної конгруенції можна наприклад перебрати повну систему лишків по модулю n. Враховуючи, що в ній міститься m представників кожного класу, дана конгруенція матиме не більше ніж m розв’язків.

Дві конгруенції називаються рівносильними, якщо вони мають по модулю m одну й ту ж саму множину розв’язків. До операцій, які дозволяють перейти від даної конгруенції до рівносильної їй відносять: додавання до обох частин конгруенції многочлена з цілими коефіцієнтами, кратними модулю; множення (ділення) обох частин конгруенції на число взаємно просте з модулем; множення (ділення) обох частин конгруенції і модуля на натуральне число.

Означ. Лінійною конгруенцією з одним невідомим називають конгруенцію виду ax≡b(mod m), (1) a,b єZ

Дослідження лінійної конгруенції.

1. Якщо (a,m)=1, то конгруенція має єдиний розв’язок, який можна знайти за формулою x≡ba^φ(m)-1(mod m) (2)

Помножимо конгруенцію (1) на a^φ(m)-1

Це можна зробити, бо (a^φ(m)-1, m)=1

a a^φ(m)-1x≡b a^φ(m)-1 (mod m),

a a^φ(m)x≡b a^φ(m)-1 (mod m). Оскільки (a,m)=1, то за теоремою Ейлера будемо мати: , тому в останній конгруенції будемо мати:x≡ba^φ(m)-1(mod m). Покажемо, що конгруенції (1) та (2) рівносильні. Нехай β-розв’язок конгруенції (2), тобто β≡bа^φ(m)(mod m). Помножимо обидві частини останньої конгруенції на а одержимо: аβ≡bа^φ(m)(mod m), за теоремою Ейлера маємо

аβ≡b( mod m), отже β – розв’язок конгруенції (1). Нехай α – розв’язок конгруенції (1), тобто aα≡b(mod m) помноживши обидві частини на a^φ(m)-1

одержимо α≡bа^φ(m)-1(mod m) тобто α-є розв’язком конгруенції (2), а раз так то (1) і (2) рівносильні.

2. Нехай (a, m)=d≠1 i b не ділиться націло на d, то конгруенція розв’язку не має. Справді, перепишемо (1) у вигляді ax=b+mt, тоді оскільки ax÷d і b÷d, то mt÷d що є протиріччям.

3. Нехай (a, m)=d і b ÷ d, тоді конгруенція (1) має d розв’язків.

x≡x₀(mod m)x≡x₀+d₁(mod m), d₁=m/d

x≡x₀+2m/d(mod m )

…………………….. (3)

x≡x₀ +((d-1)m)/d(mod m)

де х₀ – розв’язок конгруенції

(4)

Покажемо, що конгруенції (1) і (4) рівносильні. Нехай α – один з розв’язків конгруенції (1) тобто aα≡b(mod m). Поділимо обидві частини конгруенції і модуль на число d отримаємо , отже α – розв’язок (4).

Нехай тепер α – розв’язок конгруенції (4), тобто , помножимо обидві частини конгруенції та модуль на α :тобто α – розв’язок (1) і рівності (1) (4) рівносильні.

Розглянемо конгруенцію (4) оскільки у ній (,)=1, то (4) має один розв’язок, наприклад x₀+(m/d)t

Розглянемо числа x₀; x₀+; x₀+; … x0+, (5) де х₀ – найменший невід’ємний лишок по модулю . Очевидно, що числа (5) є розв’язками конгруенції (4), а раз так, то і рівносильної їй конгруенції (1). Покажемо, що числа (5) належать різним класам лишків по модулю m, припустимо що це не так і

x₀+≡ x₀+ (mod m), k,tє[0,d-1]

(k-t)≡ 0 (mod m). Покажемо, щоєZ . Оскільки k,t≤d-1, то |k-t|≤d-1, (k-t)÷d ↔ k-t=0, k=t, отже вказані числа належать одному класу лишків по модулю m.