double arrow

Линейные диофантовы уравнения с двумя неизвестными

Найти все целые x и y, такие, что ax + by = c (где a, b, c – целые числа).

Уравнения в целых числах называют диофантовыми по имени древнегреческого математика Диофанта, жившего, предположительно, в III веке н.э. Линейные диофантовы уравнения содержат неизвестные величины только в первой степени.

Напоминаем, что решить уравнение – значит найти все его решения и доказать, что других нет. В частности, если уравнение имеет бесконечно много решений, нужно описать всё множество решений некоторой общей формулой, а не ограничиться одним или несколькими примерами. С другой стороны, если уравнение имеет пустое множество решений, то обосновать этот факт – тоже означает решить уравнение.

Пример

2x + 5y = 17 (2)

Сначала найдём множество решений уравнения 2x + 5y = 1.

2 × 3 – 5 × 1 = 1, поэтому можем считать, что x0 = 3, y0 = –1.

Поскольку мы решаем уравнение 2x + 5y = 17, а не 2x + 5y = 1, то значения x0 и y0 нужно увеличить в 17 раз.

Получим: 17x0 = 51, 17y0 = –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.

Примечание

Некоторые линейные диофантовы уравнения имеют пустое множество решений, например, 6 x + 21 y = 2. При этом левая часть равенства кратна 3, а правая часть равенства не кратна 3.

Простые числа

Определение.

Натуральное число называют простым, если оно делится только на себя и на 1. Натуральное число, не являющееся простым, называют составным.

Примечание.

Число 1 не является ни простым, ни составным.

Решето Эратосфена

Удобный способ выписать все простые числа, не превосходящие заданного натурального числа, придумал древнегреческий математик Эратосфен (276 год до н. э. — 194 год до н. э.). Идея состоит в том, чтобы выписать подряд все целые числа от 2 до некоторого числа n, а затем вычеркнуть сначала все числа, кратные 2, затем все числа, кратные 3, и так далее, вычёркивая все числа, кратные простому числу p. Можно остановить действия тогда, когда величина p2 превзойдёт n.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: