Знайти всі цілі x та y. такі, що ax + by = c (де a. b. c - цілі числа).
Рівняння в цілих числах називають діофантових по імені давньогрецького математика Діофанта, який жив, імовірно, в III столітті н.е. Лінійні діофантови рівняння містять невідомі величини тільки в першого ступеня.
Нагадуємо, що вирішити рівняння - означає знайти всі його рішення і довести, що інших немає. Зокрема, якщо рівняння має нескінченно багато рішень, потрібно описати все безліч рішень деякої загальною формулою, а не обмежитися одним або декількома прикладами. З іншого боку, якщо рівняння має порожня множина рішень, то обґрунтувати цей факт - теж означає вирішити рівняння.
Спочатку знайдемо безліч рішень рівняння 2x + 5y = 1.
2 × 3 - 5 × 1 = 1, тому можемо вважати, що x0 = 3, y0 = -1.
Оскільки ми вирішуємо рівняння 2x + 5y = 17, а не 2x + 5y = 1, то значення x0 і y0 потрібно збільшити в 17 разів.
В цьому випадку 2 × (17x0) + 5 × (17y0) = 17.
Але завдання полягає в тому, щоб знайти всі пари цілих чисел, що задовольняють рівності (2).
Якщо збільшити 17x0 на 5t, а 17y0 зменшити на 2t (де t - деяке ціле число), то пара чисел x = 17x0 + 5t і y = 17y0 - 2t буде задовольняти умові (2), оскільки доданок 2x збільшиться на 10t, а доданок 5y зменшиться на 10t.
x = 51 + 5t, y = -17 - 2t.
Деякі лінійні діофантови рівняння мають порожня множина рішень, наприклад, 6x + 21y = 2. При цьому ліва частина рівності кратна 3, а права частина рівності не кратна 3.
Натуральне число називають простим. якщо воно ділиться тільки на себе і на 1. Натуральне число, що не є простим, називають складовим.
Число 1 не є ні простим, ні складеним.
Зручний спосіб виписати всі прості числа, що не перевищують заданого натурального числа, придумав давньогрецький математик Ератосфен (276 рік до н. Е. - 194 рік до н. Е.). Ідея полягає в тому, щоб виписати підряд всі цілі числа від 2 до деякого числа n, а потім викреслити спочатку все числа, кратні 2, потім все числа, кратні 3, і так далі, викреслюючи все числа, кратні простому числу p. Можна зупинити дії тоді, коли величина p 2 перевершить n.