Система сравнений первой степени

Мы рассмотрим лишь простейшую систему сравнений

x º b₁(mod m₁),

x º b₂(mod m₂),

…………… (1)

x º b_k(mod m_k)

с одним неизвестным, но с разными и притом попарно простыми модулями.

Решить систему (1), т. е. найти все значения x, ей удовлетворяющие, можно, применяя следующую теорему:

Теорема 1: Пусть числа M_s и , определены из условий

и пусть

М_s.

Тогда совокупность значений x, удовлетворяющих системе (1), определяется сравнением

x º x₀(mod m_lm₂...m_k). (2)

Доказательство: Ввиду делимости на m_s всех M_j, отличных от M_s, при любом s = 1, 2, ..., k имеем

,

и, следовательно, система (1) равносильна системе

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

(т. е. системам (1) и (3) удовлетворяют одни и те же значения x). Системе же (3), ввиду (глава 3, п. 3, Свойство 3 и Свойство 4), удовлетворяют те и только те значения x, которые удовлетворяют сравнению (2).

Теорема 2: Если b₁, b₂, …, b_k независимо друг от друга пробегают полные системы вычетов по модулям m₁, m₂, ..., m_k, то х₀ пробегает полную систему вычетов по модулю m₁m₂...m_k.

Доказательство: x₀ пробегает m₁m₂...m_k значений, ввиду (глава 3, п. 3, Свойство 4), несравнимых по модулю m₁m₂...m_k.

Пример: Решим систему

x º b₁(mod 4), x º b₂(mod 5), x º b₃(mod 7).

Здесь 4?5?7 = 35?4 = 28?5 = 20?7, причем

35?3 º 1(mod 4), 28?2 º 1(mod 5), 20?6 º 1(mod 7).

Поэтому

x₀ = 35?3b₁ + 28?2b₂ + 20?6b₃ = 105b₁ + 56b₂ + 120b₃

и, следовательно, совокупность значений x, удовлетворяющих системе, может быть представлена в виде

х = 105b₁ + 56b₂ + 120b₃(mod 140).

Так, например, совокупность значений x, удовлетворяющих системе

x º 1(mod 4), x º 3(mod 5), x º 2(mod 7),

будет

x º 105?1 + 56?3 + 120?2 º 93(mod 140),

а совокупность значений х, удовлетворяющих системе

x º 3(mod 4), x º 2(mod 5), x º 6(mod 7),

будет

x º 105?3 + 56?2 + 120?6 º 27(140). 4