§8. Ознаки подільності.

В шкільному курсі математики знайомляться з ознаками подільності на числа Ознака подільності на число: число ділиться натоді і тільки тоді, коли різниця між сумою цифр, які стоять на парних місцях, і сумою цифр, які стоять на непарних місцях, ділиться на.

Аналогічно формулюється ознака подільності на

/отже, на і, так як/. Дане число потрібно записати в системі числення з основою, тобто розбити цифри даного числа на групи по три цифри справа наліво. Ряд ознак подільності можна отримати, якщо скористатися тією властивістю, що число, яке ділиться на взаємно прості числа, ділиться на добуток отанніх.

Приклад. Знайти значення цифр та, які задовільняють умову.

Так як , тоА так якто

Отже,

Відповідь:

Завдання. Знайти значення цифр та, які задовільняють вказані умови.

§9. Теореми Ейлера і Ферма.

Теорема Ейлера. При натуральному взаємно простому з цілим числоммає місце порівняння.

Теорема Ферма. Якщо ціле число не ділиться на просте число, то.

Приклад. Знайти натуральні значення , які не перевищуютьі задовільняють порівнянню.

Так як , то

Так як то

Відповідь.

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

§ 10. Конгруенції першого степеня з однією невідомою.

Конгруенція виду , де, має єдиний розв’язок

Часто при розв’язанні такої конгруенції використовують апарат ланцюгових дробів. Нехай та. Тоді.

Конгруенція не має розв’язків якщоі.

Якщо і, то конгруенція маєрозв’язків, де- розв’язок допоміжної конгруенції

.

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

Так як , то конгруенція має один розв’язок. Розкладемов ланцюговий дріб;. Потім знаходимо, що. Отже,.

Відповідь: .

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

§ 11. Невизначені рівняння першого степеня.

Невизначене рівняння приіне має розв’язків. Якщо жі, то розв’язки рівняння задаються формуламиде- розв’язок конгруентностіі- ціле число.

Приклад. Розв’язати невизначене рівняння

Так як і, то рівняння має нескінченну множину розв’язків. Розв’язуючи допоміжну конгруентність,абознаходимо, щоТоді

Відповідь.

Завдання. Розв’язати невизначені рівняння.

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

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

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

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

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

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

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

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

Відповідь. .

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