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

Теорема 2.3.8. Для заданного множества попарно взаимно простых многочленов т₁ (х), m₂(х),..., т_k (х) и множества многочленов с₁ (х), с₂ (х),..., с_k (х), таких, что deg c_i(x) < deg m_i(x ), система сравнена и

с₁ (х) = с (х) (mod m_i(x) i = 1,..., k, имеет не более одного решения с (х}, удовлетворяющего условию

_k

dtg c(x<∑deg m_i (x.).

ⁱ⁼¹

Доказательство.. Предположим, что имеются два решения, а именно

c(x) = Q_i(x) m_i(x) +c_i(x)

и

c*(x) = Q_i^*(x) m_i(x) +c_i(x),

так что разность с(х) — с*(х) кратна многочлену т_{ (х) для каждого i. Тогда многочлен с(х) — с*(х) кратен и многочлену ∏^k_i=1 m_i(x), причем

deg [с(х) – с* (х)]<deg [ ∏ ^k m_i(x) ],

i=1

Следовательно, с(х) — с*(х) = О, и доказательство закончено.

Так же как и в кольце целых чисел, в кольце многочленов над произвольным полем выполняется равенство

НОД [r (х), s(х)] = а (х) r(х) + b(х) s (х)

для некоторых а(х) и b(х). Для заданного множества попарно взаимно простых т_{ (х) положим М (х) = П^k_i=1 m_i (х) и М_i(х)=М(х)/т₁(х) и допустим, что N_i (х) и п_i (х) удовлетворяют ра­венствам N_i(х) М_i (х)+ п_i(х) т_i(х) = I; согласно следствию 2.3.7, такие многочлены N_{(х) и п_г (х) всегда существуют

Теорема 2.3..9. Пусть М(х) = ∏^k_i=1 m_i(x)- произведение попарно взаимно простых многочленов, и пусть М_i (х) = М (х)/т_i (х)

и N_i(х) удовлетворяют равенствам N_i(х) М_i (х)+ п_i(х) т_i(х) = I. Тогда единственным решением системы сравнений,

с_i(х) = с (х) (mod mi(x)), i = 1,..., k, является

_k

с(х)=∑_i=1 с_i(х} N_i (х) М_i (х) (mod М (х)).

Доказательство. Так как мы уже знаем, что рассматриваемая система сравнений имеет не более одного решения, то нам надо только доказать, что выписанное выше с(х) действительно является решением. Но

с (х) = с_г (х) N _i (х) М_i (х) (mod m_i(x) ),
ибо т_i (х) делит М_r (х), если r ≠ i. Наконец, так как

N_i(х) М_i (х)+ п_i(х) т_i(х) = I,

то N_i(х) М_i(х) = 1 (mod m_i(x) ) и с(х) = с_i (х) (mod m_i(x) ), что и завершает доказательство.