решение диофантовых уравнений
Автор Антон Плахотин-Лопухин задал вопрос в разделе Образование
Диофантово уравнение и получил лучший ответ
Ответ от JoKa Fern Lowd[гуру]
Есть общий алгоритм решения таких уравнений, исходя из которого можно получить и общее решение.
Если с не делится нацело на НОД (a,b) -- решений нет.
Если делится делим всё уравнение на НОД (a,b), получаем уравнение такого же вида, но с взаимно простыми a и b.
Выразив y из уравнения ax+by=c, получим y=(c-ax)/b. Если мы найдём хотя бы одно решение этого уравнения x0, такое что (c-ax0)/b будет целым, то для x=x0+kb, значение (c-ax)/b также будет целым. Поэтому зная частное решение x0, можно найти общее решение x=x0+kb, y=(c-ax0-akb)/b=(c-ax0)/b-ka=y0-ka, где y0=(c-ax0)/b -- значение y для частного решения.
Общий метод поиска частного решения таков:
Используем алгоритм Евклида для нахождения НОД (a,b)=1, причём на каждом шаге записываем получившееся число, как линейную комбинацию a и b. В результате, найдём линейную комбинацию a и b, дающую 1, умножением этой комбинации на c получаем искомое частное решение.
Пример:
5x+8y=4
Ищем НОД (5,8) 5=a, 8=b.
8-5=3=b-a
5-3=2=a-(b-a)=2a-b
3-2=1=(b-a)-(2a-b)=2b-3a
Таким образом, 2b-3a=1, значит -12a+8b=4, поэтому в качестве частного решения можно взять x0=-12, y0=8.
Полученное частное решение можно поменять выбрав в качестве частного любое другое решение уравнения, полученное по формулам x=x0+kb, y=y0-ka. Как правило, на этом этапе выбирается такое частное решение, чтобы числа x0 и y0 были поменьше по абсолютной величине.
В приведенном выше примере:
x=-12+8k, y=8-5k если выбрать k=2, то x=4, y=-2.
Если теперь выбрать частное решение x0=4, y0=-2 в качестве основного, то общее решение будет иметь вид x=4+8k, y=-2-5k.
Может я че-то не понимаю?
Это уравнение приводится к виду y=kx+t, где
k=-a/b
t=c/b
если рассмотреть график этой функции, то это есть прямая, а.. .
k - это есть тангенс угла наклона относительно положительного направления оси х против часовой стрелки,
t - это есть смещение прямой по оси у
Соответственно, областью значенй данного уравнения, является вся числовая ось.
То есть подходят ВСЕ числа в качестве решения
По-видимому, дано, что a,b,c - целые числа. Будем, кроме того, считать a и b взаимно простыми.
Теорема: Если пара целых чисел (х0, у0) есть какое-нибудь решение уравнения, то
пары (x0+b*n, y0-a*n), где n - любое целое, есть общее решение.
Док-во. 1) Подстановка пары указанного вида в уравнение сразу показывает, что
при всяком целом n эта пара есть также решение.
2) Пусть (x0,y0) и (x1,y1) - два решения, тогда, очевидно, a(x1-x0)+b(y1-y0)=0.
Обозначим целые числа x1-x0=m, y-y0=k. Тогда a*m+b*k=0, k= - a/b*m. Так как a,b взаимно простые, то дробь a/b несократима. Значит, m делится нацело на b, или m=b*n, где n - целое число.
Отсюда, x1=x0+b*n, y1=y0-a*n.