Лінійні конгруенції та китайська теорема про лишки

Лінійна конгруенція дуже схожа на просте лінійне рівняння, відоме зі школи. А саме вона має вигляд $$ax=b(mod \ m).$$ Ця конгруенція рівносильна діофантовому рівнянню $ax=b+my$, або $$ax-my=b.$$

розв'язок. Якщо $b$ не ділиться на $d = НСД(a, m)$, то розв'язку немає. Інакше, рівння можна поділити на $d$ $$a_1x=b_1(mod \ m_1).$$ При цьому $ НСД(a_1, m_1)=1.$ В цьому випадку для $a_1$ існує обернений $c$ такий, що $a_1c=1(mod \ m_1)$, тоді рівняння має наступний розв'язок $x = b_1c(mod \ m_1)$. Нехай $x_0 = b_1c$, тоді $x = x_0+ k m_1$, $k \in \mathbb Z$. оскільки початкове рівняння було за модулем $m$, то розв'язки в $\mathbb Z_m$ будуть наступними: $$x= x_0+km_1,\ 0 \leq k < d.$$

Китайська теорема про лишки