Лема 1 (Китайська теорема про лишки). Нехай дана найпростіша система порівнянь першого степеня:

                                           (*)

де m₁,m₂,...,m_k попарно взаємно прості. Нехай, m₁ m₂ ...m_k =M_s m_s; M_s M_s^Ñ º 1(mod m_s) (Очевидно, що таке число M_s^Ñ  завжди можна підібрати хоча б за допомогою алгоритму Евкліда, оскільки (m_s, M_s )=1); x₀ =M₁ M₁^Ñ b₁+M₂ M₂^Ñ b₂ +...+M_k M_k^Ñ b_k. Тоді система (*) рівносильна одному порівнянню

x º x₀ (mod m₁ m₂ ...m_k ),

а саме набір розв’язків (*) збігається з набором розв’язків порівняння xº x₀(mod m₁m₂ ...m_k).

Доказ. Маємо: m_s ділить M_j, при s¹j. Отже, x₀ º M_s M_s^Ñ b_s (mod m_s), звідки x₀º b_s(mod m_s). Це означає, що система (*) рівносильна системі

яка, у свою чергу, рівносильна одному порівнянню xº x₀ (mod m₁ m₂ ...m_k ).

Приклад. Знайти число, що при діленні на 4 дає в залишку 1, при діленні на 5 дає в залишку 3, а при діленні на 7 дає в залишку 2.

Складемо систему:

,

яку розв’язуємо за допомогою леми 1.

b₁ =1; b₂ =3; b₃ =2; m₁ m₂ m₃ , тобто M₁ =35, M₂ =28, M₃ =20.

35 × 3 º 1(mod 4)

28 × 2 º 1(mod 5)

20 × 6 º 1(mod 7)

тобто M₁^Ñ =3, M₂^Ñ =2, M₃^Ñ =6. Значить x₀ =35 × 3 × 1+28 × 2 × 3+20 × 6 × 2=513. Після цього, за лемою 1:

x º 513(mod 140) º 93(mod 140),

а саме найменше додатне число дорівнює 93.

У наступній лемі, для стислості формулювання, збережені позначення леми 1.

Лема 2. Якщо b₁ ,b₂ ,...,b_k набувають значення з повних систем лишків за модулями m₁,m₂,...,m_k відповідно, то x₀ набуває значення з повної системи лишків за модулями m₁ m₂ ...m_k .

Доказ. Дійсно, x₀ =A₁ b₁ +A₂ b₂ +...+A_k b_k набуває m₁ m₂ ...m_k різних значень. Покажемо, що усі вони попарно непорівняльні за модулями m₁ m₂ ...m_k .

Нехай виявилося, що

A₁ b₁ +A₂ b₂ +...+A_k b_k º A₁ b'₁ +A₂ b'₂ +...+A_k b'_k (mod m₁ m₂ ...m_k ).

Тоді

A₁ b₁ +A₂ b₂ +...+A_k b_k º A₁ b'₁ +A₂ b'₂ +...+A_k b'_k (mod m_s )

для кожного s, звідки

M_s M_s^Ñ b_s º M_s M_s^Ñ b'_s

Згадаємо тепер, що M_s M_s^Ñ º 1(mod m_s), значить M_s M_s^Ñ º 1+m_s× t, звідки (M_s M_s^Ñ ,m_s)=1. Розділивши тепер обидві частини порівняння

M_s M_s^Ñ b_s º M_s M_s^Ñ b'_s

на число M_s M_s^Ñ , взаємно просте з модулем, одержимо, що b_s º b'_s (mod m_s), тобто b_s=b'_s для кожного s.

Отже, x₀ набуває m₁ m₂ ...m_k різних значень, попарно непорівняльних за модулями m₁ m₂ ...m_k , а саме значення з повної системи лишків.