Китайская теорема об остатках

Китайская теорема об остатках Найти решение системы сравнений
x=2(mod 5),
x=15(mod 17),
x=5(mod 12).

Решение.

Числа 5, 17 и 12 являются взаимно простые, согласно теореме решение существует.

Запишем систему в виде

x=a_i(mod m_i), i=1,...,n.

Вычислим величины

M₀=m₁m₂m₃=1020,

M_i=M₀/m_i, i=1,...,n,

M₁=204, M₂=60, M₃=85.

Решим вспомогательные сравнения

M_iy_i=a_i(mod m_i), i=1,...,3.

Рассмотрим первое сравнение:

204y₁=2(mod 5)=200y₁+4y₁=2(mod 5)=0+4y₁=2(mod 5).
Здесь мы учли, что 200y₁(mod 5)=0, т.к. 200 делится на 5.

Перебирая y₁=1,2,3,4,5 в сравнении 4y₁=2(mod 5), находим y₁=3.
Действительно, 4·3-2=12-2=10 делится на 5.

Аналогично находим решения

60y₂=15(mod 17), y₂=13,

85y₃=5(mod 12), y₃=5.

Получаем решение

x=M₁y₁+M₂y₂+M₃y₃ (mod M₀)=1817(mod 1020)=797(mod 1020)

File translated from T_EX by T_TH, version 3.64.
On 22 Nov 2009, 11:57.