Дальнейшие свойства сравнений

Свойство 1: Обе части сравнения и модуль можно умножить на одно и то же целое.

Доказательство: Из a º b(mod m) следует

a = b + mt, ak = bk + mkt

и, следовательно, ak º bk(mod mk).

Свойство 2: Обе части сравнения и модуль можно разделить на любой их общий делитель.

Доказательство: Пусть

a º b(mod m), a = a₁d, b = b₁d, m = m₁d.

Имеем

a = b + mt, a_ld = b₁d + m₁dt, a₁ = b_l + m_lt

и, следовательно, a₁ º b₁(mod m₁).

Свойство 3: Если сравнение а º b имеет место по нескольким модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

Доказательство: Из a º b(mod m₁), a º b(mod m₂), ... , a º b(mod m_k) следует, что разность а - b делится на все модули m₁, m₂, ..., m_k. Поэтому (Глава 1, п. 5, Теорема 9) она должна делиться и на наименьшее общее кратное m этих модулей, т. е. a º b(mod m).

Свойство 4: Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.

Доказательство: Из a º b(mod m) следует, что разность а - b должна делиться на m; поэтому (Глава 1, п. 1, Теорема 1) она должна делиться и на любой делитель d числа m, т. е. A º b(mod d).

Свойство 5: Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.

Доказательство: Из a º b(mod m) следует a = b + mt; если a и т кратны d, то (Глава 1, п. 1, Теорема 2) и b должно быть кратным d, что и утверждалось.

Свойство 6: Если a º b(mod m), то (а, m) = (b, m).

Доказательство: Ввиду (Глава 1, п. 2, Теорема 2) это равенство непосредственно следует из a = b + mt. 4