Системи конгруенцій першого степеня

Для сумісності системи конгруенцій

-------------------

необхідно, щоб кожна конгруенція мала розв’язок.

Розв’язуючи першу конгруенцію знаходять, що або - ціле число. Знайдене значення підставляють в другу конгруенцію: Якщо то і або Отримане значення , яке задовільняє перші дві конгруенції, підставляють в третю конгруенцію і так далі. Якщо система сумісна, то розв’язками будуть класи чисел по модулю , де .

Приклад. Розв’язати систему конгруенцій.

Конгруенція має розв’язок . Якщо то або , звідки .

Підставляючи значення в третю конгруенцію, отримаємо: . Підстановка інших значень в третю конгруенцію не дає нічого нового. Якщо то приходимо до конгруенції , яка не має розв’язків.

Відповідь. .

Завдання. Розв’язати конгруенції першого степеня.