Как решить линейное диофантово уравнение

Загрузить PDF

Загрузить PDF

В этой статье:

Как записать уравнение

Как записать алгоритм Евклида

Как найти решение с помощью алгоритма Евклида

Как найти бесконечное множество других решений

Показать еще 1...

Показать меньше...

Дополнительные статьи

Источники

Чтобы решить линейное диофантово уравнение, нужно найти значения переменных «x» и «y», которые являются целыми числами. Целочисленное решение сложнее обычного и требует определенного набора действий. Сначала необходимо вычислить наибольший общий делитель (НОД) коэффициентов, а затем найти решение. Если вы нашли одно целочисленное решение линейного уравнения, можно применить простой шаблон, чтобы найти бесконечное множество других решений.

Шаги

Часть 1

Часть 1 из 4:

Как записать уравнение

Загрузить PDF

1. 
   1
   Запишите уравнение в стандартной форме. Линейное уравнение — это уравнение, в котором показатели степени переменных не превышают 1. Чтобы решить такое линейное уравнение, сначала запишите его в стандартной форме. Стандартная форма линейного уравнения выглядит так: $Ax+By=C$, где $A,B$ и $C$ — целые числа.

   • Если уравнение дано в другой форме, приведите его к стандартной форме с помощью основных алгебраических действий. Например, дано уравнение $23x+4y-7x=-3y+15$. Приведите подобные члены и запишите уравнение так: $16x+7y=15$.
2. 
   2
   Упростите уравнение (если можно). Когда вы запишете уравнение в стандартной форме, посмотрите на коэффициенты $A,B$ и $C$. Если у этих коэффициентов есть НОД, разделите на него все три коэффициента. Решение такого упрощенного уравнения также будет решением исходного уравнения.

   • Например, если все три коэффициента четные, разделите их как минимум на 2. Например:
     • $42x+36y=48$ (все члены делятся на 2)
     • $21x+18y=24$ (теперь все члены делятся на 3)
     • $7x+6y=8$ (это уравнение больше нельзя упростить)
3. 
   3
   Проверьте, можно ли решить уравнение. В некоторых случаях можно сразу заявить, что уравнение не имеет решений. Если коэффициент «С» не делится на НОД коэффициентов «А» и «В», у уравнения нет решений.

   • Например, если оба коэффициента $A$ и $B$ четные, то и коэффициент $C$ должен быть четным. Но если $C$ нечетный, то решения нет.
     • У уравнения $2x+4y=21$ нет целочисленных решений.
     • У уравнения $5x+10y=17$ нет целочисленных решений, так как левая часть уравнения делится на 5, а правая — нет.
   Реклама

Часть 2

Часть 2 из 4:

Как записать алгоритм Евклида

Загрузить PDF

1. 
   1
   Уясните алгоритм Евклида. Это ряд повторных делений, в котором предыдущий остаток используется как следующий делитель. Последний делитель, который делит числа нацело, является наибольшим общим делителем (НОД) двух чисел.

   • Например, найдем НОД чисел 272 и 36 с помощью алгоритма Евклида:
     • $272=7*36+20$ — разделите большее число (272) на меньшее (36) и обратите внимание на остаток (20);
     • $36=1*20+16$ — разделите предыдущий делитель (36) на предыдущий остаток (20). Обратите внимание на новый остаток (16);
     • $20=1*16+4$ — разделите предыдущий делитель (20) на предыдущий остаток (16). Обратите внимание на новый остаток (4);
     • $16=4*4+0$ — разделите предыдущий делитель (16) на предыдущий остаток (4). Так как остаток равен 0, можно сказать, что 4 является НОДом исходных двух чисел 272 и 36.
2. 
   2
   Примените алгоритм Евклида к коэффициентам «A» и «B». Когда вы запишете линейное уравнение в стандартной форме, определите коэффициенты «A» и «B», а затем примените к ним алгоритм Евклида, чтобы найти НОД. Например, дано линейное уравнение $87x-64y=3$.

   • Вот алгоритм Евклида для коэффициентов А=87 и В=64:
     • $87=1*64+23$
     • $64=2*23+18$
     • $23=1*18+5$
     • $18=3*5+3$
     • $5=1*3+2$
     • $3=1*2+1$
     • $2=2*1+0$
3. 
   3
   Найдите наибольший общий делитель (НОД). Поскольку последним делителем было число 1, НОД 87 и 64 равен 1. Таким образом, 87 и 64 являются простыми числами по отношению друг к другу.
4. 
   4
   Проанализируйте полученный результат. Когда вы найдете НОД коэффициентов $A$ и $B$, сравните его с коэффициентом $C$ исходного уравнения. Если $C$ делится на НОД $A$ и $B$, уравнение имеет целочисленное решение; в противном случае у уравнения нет решений.

   • Например, уравнение $87x-64y=3$ можно решить, потому что 3 делится на 1 (НОД=1).
   • Например, предположим, что НОД=5. 3 не делится на 5 нацело, поэтому такое уравнение не имеет целочисленных решений.
   • Как показано ниже, если уравнение имеет одно целочисленное решение, оно также имеет бесконечное множество других целочисленных решений.
   Реклама

Часть 3

Часть 3 из 4:

Как найти решение с помощью алгоритма Евклида

Загрузить PDF

1. 
   1
   Пронумеруйте шаги вычисления НОД. Чтобы найти решение линейного уравнения, нужно использовать алгоритм Евклида в качестве основы процесса подстановки и упрощения.

   • Начните с нумерации шагов вычисления НОД. Процесс вычисления выглядит так:
     • ${\text{Шаг 1}}:87=(1*64)+23$
     • ${\text{Шаг 2}}:64=(2*23)+18$
     • ${\text{Шаг 3}}:23=(1*18)+5$
     • ${\text{Шаг 4}}:18=(3*5)+3$
     • ${\text{Шаг 5}}:5=(1*3)+2$
     • ${\text{Шаг 6}}:3=(1*2)+1$
     • ${\text{Шаг 7}}:2=(2*1)+0$
2. 
   2
   Обратите внимание на последний шаг, где есть остаток. Перепишите уравнение этого шага так, чтобы изолировать остаток.

   • В нашем примере последний шаг с остатком — это шаг 6. Остаток равен 1. Перепишите уравнение шага 6 следующим образом:
     • $1=3-(1*2)$
3. 
   3
   Изолируйте остаток предыдущего шага. Этот процесс представляет собой пошаговое «перемещение вверх». Каждый раз вы будете изолировать остаток в уравнении предыдущего шага.

   • Изолируйте остаток уравнения шага 5:
     • $2=5-(1*3)$ или $2=5-3$
4. 
   4
   Сделайте замену и упростите. Обратите внимание, что уравнение шага 6 содержит число 2, а в уравнении шага 5 число 2 изолировано. Поэтому вместо «2» в уравнении шага 6 подставьте выражение шага 5:

   • $1=3-2$ (уравнение шага 6)
   • $1=3-(5-3)$ (вместо 2 подставили выражение)
   • $1=3-5+3$ (раскрыли скобки)
   • $1=2(3)-5$ (упростили)
5. 
   5
   Повторите процесс подстановки и упрощения. Повторите описанный процесс, перемещаясь по алгоритму Евклида в обратном порядке. Каждый раз вы будете переписывать уравнение предыдущего шага и подставлять его в последнее полученное уравнение.

   • Последним рассмотренным шагом был шаг 5. Поэтому перейдите к шагу 4 и изолируйте остаток в уравнении этого шага:
     • $3=18-(3*5)$
   • Подставьте это выражение вместо «3» в последнее уравнение:
     • $1=2(18-3*5)-5$
     • $1=2(18)-6(5)-5$
     • $1=2(18)-7(5)$
6. 
   6
   Продолжите процесс подстановки и упрощения. Этот процесс будет повторяться до тех пор, пока вы не достигнете первоначального шага алгоритма Евклида. Цель процесса — записать уравнение с коэффициентами 87 и 64 исходного уравнения, которое нужно решить. В нашем примере:

   • $1=2(18)-7(5)$
   • $1=2(18)-7(23-18)$ (подставили выражение из шага 3)
     • $1=2(18)-7(23)+7(18)$
     • $1=9(18)-7(23)$
   • $1=9(64-2*23)-7(23)$ (подставили выражение из шага 2)
     • $1=9(64)-18(23)-7(23)$
     • $1=9(64)-25(23)$
   • $1=9(64)-25(87-64)$ (подставили выражение из шага 1)
     • $1=9(64)-25(87)+25(64)$
     • $1=34(64)-25(87)$
7. 
   7
   Перепишите полученное уравнение в соответствии с исходными коэффициентами. Когда вы вернетесь к первому шагу алгоритма Евклида, вы увидите, что полученное уравнение содержит два коэффициента исходного уравнения. Перепишите уравнение так, чтобы порядок его членов соответствовал коэффициентам исходного уравнения.

   • В нашем примере исходное уравнение $87x-64y=3$. Поэтому перепишите полученное уравнение так, чтобы коэффициенты привести в соответствие. Обратите особое внимание на коэффициент «64». В исходном уравнении этот коэффициент отрицательный, а в алгоритме Евклида — положительный. Поэтому множитель 34 нужно сделать отрицательным. Окончательное уравнение запишется так:
     • $87(-25)-64(-34)=1$
8. 
   8
   Примените соответствующий множитель, чтобы найти решение. Обратите внимание, что в нашем примере НОД=1, поэтому окончательное уравнение равно 1. Но исходное уравнение (87x-64y) равно 3. Поэтому все члены окончательного уравнения нужно умножить на 3, чтобы получить решение:

   • $87(-25*3)-64(-34*3)=1*3$
   • $87(-75)-64(-102)=3$
9. 
   9
   Запишите целочисленное решение уравнения. Числа, которые умножаются на коэффициенты исходного уравнения, являются решениями этого уравнения.

   • В нашем примере запишите решение в виде пары координат: $(x,y)=(-75,-102)$.
   Реклама

Часть 4

Часть 4 из 4:

Как найти бесконечное множество других решений

Загрузить PDF

1. 
   1
   Уясните, что существует бесконечное множество решений. Если линейное уравнение имеет одно целочисленное решение, то оно должно иметь бесконечно множество целочисленных решений. Вот краткое доказательство (в алгебраической форме):

   • $Ax+By=C$
   • $A(x+B)+B(y-A)=C$ (если прибавить «B» к «x» и вычесть «A» из «y», значение исходного уравнения не изменится)
2. 
   2
   Запишите исходные значения «x» и «y». Шаблон для вычисления последующих (бесконечных) решений начинается с единственного решения, которое вы уже нашли.

   • В нашем примере решение представляет собой пару координат $(x,y)=(-75,-102)$.
3. 
   3
   Прибавьте коэффициент «B» к значению «x». Сделайте это, чтобы найти новое значение «x».

   • В нашем примере x=-75, а В=-64:
     • $x=-75+(-64)=-139$
   • Таким образом, новое значение «х»: x=-139.
4. 
   4
   Вычтите коэффициент «A» из значения «y». Чтобы значение исходного уравнения не изменилось, при прибавлении одного числа к «x» нужно вычесть другое число из «y».

   • В нашем примере y=-102, а А=87:
     • $y=-102-87=-189$
   • Таким образом, новое значение «у»: у=-189.
   • Новая пара координат запишется так: $(x,y)=(-139,-189)$.
5. 
   5
   Проверьте решение. Чтобы убедиться, что новая пара координат является решением исходного уравнения, подставьте значения в уравнение.

   • $87x-64y=3$
   • $87(-139)-64(-189)=3$
   • $3=3$
   • Поскольку равенство соблюдено, решение верное.
6. 
   6
   Запишите выражения для нахождения множества решений. Значения «x» будут равны исходному решению плюс любое кратное коэффициента «В». Это можно записать в виде следующего выражения:

   • x(k)=x+k(B), где «x(k)» — множество значений «х», а «x» — исходное (первое) значение «x», которое вы нашли.
     • В нашем примере:
     • $x(k)=-75-64k$
   • y(k)=y-k(A), где «у(k)» — множество значений «у», а «у» — исходное (первое) значение «у», которое вы нашли.
     • В нашем примере:
     • $y(k)=-102-87k$
   Реклама