§5. Теорія порівнянь

Пункт 16. Визначення і найпростіші властивості.

Визначення. Нехай а, b Î Z , m Î N. Число а порівняльне з b за модулем m, якщо а і b при діленні на m мають однакові залишки: a º b(mod m) .

Очевидно, що бінарне відношення порівняння º _m є відношенням еквівалентності на множині цілих чисел, або це відношення є конгруенцією кільця Z, фактор-кільце за якою Z/ º _m називається кільцем лишків і позначається Z_m.

Зрозуміло, що число a порівняльне з b за модулем m тоді і тільки тоді, коли a-b ділиться на m без остачі. Очевидно, що це буває тоді і тільки тоді, коли знайдеться таке ціле число t, що a=b+mt. Порівняльність a і b за модулем m означає, що a і b є тим самим елементом у кільці Z_m.

Процес збирання цілих чисел у класи порівняльних між собою за модулем m (класи еквівалентності º _m ) ілюструє рисунок:

На ньому зображений процес намотування ланцюжка цілих чисел на кільце з m діленнями, при цьому на одне ділення автоматично попадають порівняльні між собою числа. До речі, ця картинка непогано пояснює і термін "кільце".

Перелічимо, далі, властивості порівнянь, схожі на властивості відношення рівності.

Властивість 1. Порівняння за однаковим модулем можна почленно додавати.

Доказ. Нехай a₁º b₁(mod m), a₂º b₂(mod m). Це означає, що a₁ =b₁ +mt₁, a₂ =b₂ +mt₂. Після додавання останніх двох рівностей, одержимо a₁ +a₂ =b₁ +b₂ +m(t₁ +t₂ ), що означає a₁+a₂º b₁ +b₂ (mod m).

Властивість 2. Доданок, що стоїть в якій-небудь частині порівняння, можна переносити в іншу частину, змінивши його знак на зворотний.

Доказ. .

Властивість 3. До будь-якої частини порівняння можна додати будь-яке число, кратне модулю.

Доказ. .

Властивість 4. Порівняння за однаковим модулем можна почленно перемножувати і, відповідно,

Властивість 5. Обидві частини порівняння можна піднести до однакового степеня.

Доказ. .

Наслідком перелічених властивостей, є

Властивість 6. Якщо a₀ º b₀ (mod m), a₁ º b₁ (mod m),..., a_n º b_n (mod m), x º y(mod m), то a₀xⁿ+a₁ x^n-1 +...+a_n º b₀ yⁿ +b₁ y^n-1 +...+b_n (mod m)

Властивість 7. Обидві частини порівняння можна поділити на їхній спільний дільник, взаємно простий з модулем.

Доказ. Нехай a º b(mod m) , a=a₁ d , b=b₁ d . Тоді (a₁ -b₁ ) × d ділиться на m. Оскільки d і m взаємно прості, то на m ділиться число (a₁ -b₁ ), що означає a₁ º b₁ (mod m).

Властивість 8. Обидві частини порівняння і його модуль можна помножити на те саме ціле число або розділити на їхній спільний дільник.

Доказ.

a º b(mod m) Û a=b+mt Û ak=bk+mkt Û ak º bk(mod mk).

Властивість 9. Якщо порівняння a º b існує за кількома різними модулями, то воно існує й за модулем, що дорівнює найменшому спільному кратному цих модулів.

Доказ. Якщо a º b(mod m₁ ) і a º b(mod m₂ ), то a-b ділиться на m₁ і на m₂, отже a-b ділиться на найменше спільне кратне m₁ і m₂.

Властивість 10. Якщо порівняння існує за модулем m, то воно існує і за модулем d, що дорівнює будь-якому дільнику числа m.

Доказ очевидний (випливає з транзитивності відношення подільності: якщо a º b(mod m), то a-b ділиться на m, отже a-b ділиться на d, де d|m).

Властивість 11. Якщо одна частина порівняння і модуль діляться на деяке число, то й інша частина порівняння мусить ділитися на те ж число.

Доказ.

a º b(mod m) Û a=b+mt

Приклад. Довести, що для будь-якого натурального n число 37ⁿ⁺²+16ⁿ⁺¹+23ⁿ ділиться на 7.

Рішення. Очевидно, що 37 º 2(mod 7), 16 º 2(mod 7), 23 º 2(mod 7)

Піднесемо перше порівняння до степеня n+2, друге – до степеня n+1, третє – до степеня n і додамо:

тобто 37ⁿ⁺²+16ⁿ⁺¹+23ⁿ ділиться на 7.