Лабораторна робота №4
Тема: Діофантові рівняння. Застосування конгруенції, їх властивостей та теорем Ейлера і Ферма.
Ціль: навчитись розвязувати Діофантові рівняння першого степеня, визначати остачу від ділення, розвязувати лінійні конгруенції та використовувати їх в прикладних задач цілочисельного розвязку.
Теоретичні відомості
Рівняння виду 
, де 
- многочлен декількох змінних з цілими коефіцієнтами для яких потрібно знайти цілі розв’язки, називають діофантовими рівняннями. Названі вони ім’ям грецького математика Діофанта, який жив у ІІІ столітті н.е. Його книга «Арифметика» містила 189 задач з цілими числами, для кожної з яких наводилося один або декілька розв’язків.
Розв’язати діофантове рівняння означає:
a) з’ясувати, чи має рівняння хоча б один ненульовий розв’язок в цілих числах;
b) якщо рівняння має розв’язок в цілих числах, то з’ясувати скінченна чи нескінченна множина його розв’язків;
c) знайти всі цілі розв’язки рівняння.
Лінійні діофантові рівняння виду 
навчились розв’язувати ще до Діофанта. Стародавні греки знали, що якщо це рівняння має один цілий розв’язок 
, то його буде задовольняти нескінченна множина пар 
виду 
, де 
- будь яке ціле число.
Математики Стародавньої Греції та Стародавньої Індії знали методи розв’язання деяких рівнянь другого степеня виду 
. Зокрема їм були відомі всі піфагорові трійки натуральних чисел 
, що задовольняють рівняння 
. Всі трійки взаємно простих піфагорових чисел стародавні математики знаходили за формулами 
, 
- натуральні числа причому 
.
Особливе місце серед діофантових рівнянь займає рівняння 
, де 
- натуральне число. Французький математик П’єр Ферма довів, що при 
рівняння не має розв’язків в натуральних числах .
Діофантові рівняння першого степеня
Рівняння виду де 
- числа, а 
- змінні, називають діофантовим рівнянням першого степеня з двома змінними. Для розв’язання рівняння застосовують наступні теореми.
Теорема1. Якщо 
- взаємно прості числа, то для будь якого цілого 
, рівняння має хоча б один розв’язок в цілих числах.
Теорема2. Якщо мають спільний натуральний дільник 
, а ціле число не ділиться на 
, то рівняння не має розв’язків в цілих числах.
Теорема3. Якщо взаємно прості числа, то рівняння має нескінченну кількість розв’язків 
, які знаходять за формулами, де - будь який цілий розв’язок даного рівняння, 
.
Частинний розв’язок можна знайти підбором, для малих , а у випадку коли числа великі, то користуємось наступною теоремою.
Теорема4. НСД(
) 
може бути записаний у вигляді 
, де цілі числа.
знаходимо за алгоритмом Евкліда.
Означення 1. Цілі числа 
і 
називають конгруентними за модулем 
, де — ціле число, якщо їхня річниця 
ділиться на . Позначення:
Якщо і не конгруентні за модулем , то пишуть
Означення 2. Цілі числа і називають конгруентними ва модулем , де 
, якщо еони при діленні на дають однакові остачі.
Означення 3. Цілі числа і називають конгруентними за модулем , де , якщо існує таке ціле число 
, що 
.
Означення 1, 2, 3 рівносильні.
