Порівняння, система відрахувань, рішення лінійних систем по модулю

[Ред] Порівняння по модулю

Будемо розглядати цілі числа в зв'язку із залишками від ділення їх на дане ціле число m. яке назвемо модулем. Кожному цілому числу відповідає певний залишок від ділення його на m. Якщо двом цілим a і b відповідає один і той же залишок r. то вони називаються порівнянними за модулем m.

Порівнянність для a і b записується так:

Порівнянність чисел a і b по модулю m рівносильна:

• а. Можливості уявити a в формі, де t - ціле.
• б. Подільності на m.
  • Дійсно, з слід, звідки, і, де.
    
  • Назад, з, представляючи b в формі, виводимо, де, значить.

[Ред] Арифметика порівнянь

[Ред] Властивості порівнянь

• 1. Два числа, які можна порівняти з третім порівнянні між собою.
  • Легко виводиться з пункту "а".

• 2. Порівняння можна почленно складати.
  • Представляємо порівняння, як в пункті "а" і складаємо.

• 3. Порівняння можна почленно перемножувати.
  • Представляємо порівняння, як в пункті "а", перемножуємо, отримаємо, де N-ціле.

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

• 5. Обидві частини порівняння можна помножити на одне і теж число.
  • Дійсно, з, слід, і, отже,.

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

• 7. Якщо порівняння має місце за кількома модулями, то воно має місце і по модулю рівному НОК цих модулів.
  • Справді, з випливає, що різниця ділиться на всі модулі. Тому вона повинна ділитися і на їх НОК.

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

• 9. Якщо одна частина порівняння і модуль діляться на деяке число, то і інша сторона порівняння повинна ділитися на це число.
  • Випливає з пункту "а".

• 10. Якщо, то.
  • Випливає з пункту "а" по властивості Нода.

[Ред] Повна і наведена система відрахувань

Числа равноостаточние (порівнянні по модулю m) утворюють клас чисел за модулем m. З такого визначення випливає, що всім числам класу відповідає один залишок r. і ми отримаємо всі числа класу, якщо в формі змусимо t пробігати всі цілі числа. Таким чином для кожного значення залишку є свій клас чисел.

Будь-яке число класу називається вирахуванням за модулем m. Відрахування одержуваний при, рівний самому залишку r. називається найменшим невід'ємним вирахуванням.

Будь-які m чисел, попарно незрівнянні за модулем m. утворюють повну систему відрахувань по цьому модулю.

Згідно 10 властивості порівнянь, числа одного класу по модулю m мають однаковий НСД. Особливо важливі класи, що містять числа, взаємно прості з модулем. Взявши відрахування від кожного такого класу, отримаємо наведену систему відрахувань по модулю m.

[Ред] Рішення лінійних систем по модулю

Нехай. Порівняння неможливо, якщо b не ділиться на d. При b, кратному d. порівняння має d рішень.
Пошук рішень:
,
Складемо нове порівняння, позначимо його. Нехай його рішенням буде, тоді інші рішення знайдуться за такою формулою: (слід розуміти, що відрахування по модулю, тому в цій формулі можна змінити знак, для зручності), всього рішень буде d. Якщо знаходження не є очевидним, то слід скористатися теорією ланцюгових дробів. і тоді, де - чисельник придатної дробу.

[Ред] Приклади розв'язання

Приклад 1.

знайдемо НСД
Перейдемо до нового порівнянні
легко знаходиться
Тоді відповіддю буде

Приклад 2.

Знайдемо НСД, 75 кратно 3, значить маємо 3 рішення
Перейдемо до нового порівнянні
Скористаємося ланцюговими дробами, в нашому випадку, отже
Тоді відповіддю буде.