Системы линейных сравнений

Теорема 2.48 (Китайская теорема об остатках) Пусть имеется система линейных сравнений,

'х = с_х (mod т_г)

х = c₂(mod m₂)

• (2.182)
• (2.183)
• (2.184)

= c_k (mod m_k)

где m_v m₂..., m_k - попарно взаимно простые.

Пусть M_s = т_г ...m_s^₁m_s+1 ...m_k и M определяется из сравнений

ММ' = l(modm_s)

Тогда исходная система эквивалентна сравнению

х = x₀(mod т^.-.т^ где

х₀ = М₁М₁'с₁ + М₂М₂'с₂ + ...+ M^M_kc_k(mod т_г...т_к) (2.185)

Доказательство. Пусть

M_s - m₁m₂...m_s_₁m_s+1.. ,m_k, M_SM_S' = l(modm_s)

и

x₀ = + M₂M₂'c₂ + ...+ M_kM_k'c_k(mod т_г...т_к).

В соответствии с китайской теоремой об остатках запишем алгоритм решения системы сравнений первой степени.

Алгоритм решения системы сравнений первой степени 'х = c₁(mod х = c₂(mod m₂)

= c_k(mod m_k)

• 1. УбеДИТЬСЯ В ТОМ, ЧТО ДЛЯ Любых І, j = 1, П, i^j ВЫПОЛНеНО (ТПі, TTlj) = 1.
• 2. Найти М = т.^2 ...т_п.

м --

• 3. Определить все М[ = —, і = 1, п.
• 4. Найти все Уі, і = 1,п, решив сравнение = l(modmi).
• 5. Найти решение х₀ = ?”₌₁ у^.
• 6. Записать решение сравнения х= x₀(modM).

Например, решим систему линейных сравнений ' х = 2 (mod т_г)

х = 3 (mod m₂)

fc)

Решение.

• 1. m₁ = 3, m₂ = 5, m₃ = 7. (3, 5) = 1, (3, 7) = 1, (5, 7) = 1. Мы убедились, что m₁, m₂, m₃ - взаимно простая система.
• 2. M = т!т₂т₃ = 3-5-7 = 105.

М 105 105 105

• 3. М_І= — ,М_І= — = 35;М₂ =--= 21;М₃ =— =15.
• 1 ^{mt 1} 3 ² 5 ⁶ 7
• 4. М₁у₁ = (mod mJ; 35y_t = l(mod 3).

Применяем метод подбора.

m=3, следовательно, полная система вычетов 1, 2.

Проверяем:

• 35-1 = }(mod 3)
• 35 - 1 = 34 не кратно 3, следовательно, 1 - не является решением.

Далее, проверяем двойку:

• 35-2 = 1 (mod 3)
• 70 - 1 = 69 : 3, следовательно, 2 - решение.

Таким образом,

Уі = 2(mod 3).

Далее,

М₂у₂ = Urnodm₂) 21у₂ = l(mod 5) Полная система вычетов: 1, 2, 3,4.

Проверяем:

у₂ = 1:21-1 = l(mod 5)

21 - 1 = 20 : 5, следовательно, у₂ = 1 - решение.

у₂ = (mod 5)

Далее,

М₃у₃ = 1 (modm₃) 15-1 = 1 (mod 7) 15-1 = 14:7, следовательно, у₃ = 1 решение этого сравнения Уз = (mod 7)

Находим решение:

п

х° = ? —

і-1

*0 = ^іУі^сі + М₂у₂с₂ + м₃у₃с₃.

х₀ = 35-2-2+ 21-1-3+ 15-1-1.

х₀ = 218.

Таким образом, получено решение системы: х = 218(mod 105);

Но 218 > 105, воспользуемся свойством сравнений

х = 218 - 105-2(mod 105)

х = S(mod 105)

Проверка:

• 7)8 = 2(mod 3), 8 - 2 = 6 • 3 - верно;
• 2) 8 = 3(mod 5), 8 - 3= 5 • 5 - верно;
• 3) 8= l(mod 7), 8 - 1 = 7 • 7 - верно.

Ответ: х = 8(mod 105) - решение заданной системы линейных сравнений.