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

Соавтор(ы): Grace Imson, MA

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

Часть 1

Часть 1 из 4:

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

Загрузить PDF

1
Запишите уравнение в стандартной форме. Линейное уравнение — это уравнение, в котором показатели степени переменных не превышают 1. Чтобы решить такое линейное уравнение, сначала запишите его в стандартной форме. Стандартная форма линейного уравнения выглядит так: $Ax+By=C$ , где $A,B$ и $C$ — целые числа.
- Если уравнение дано в другой форме, приведите его к стандартной форме с помощью основных алгебраических действий. Например, дано уравнение $23x+4y-7x=-3y+15$ . Приведите подобные члены и запишите уравнение так: $16x+7y=15$ .
2
Упростите уравнение (если можно). Когда вы запишете уравнение в стандартной форме, посмотрите на коэффициенты $A,B$ и $C$ . Если у этих коэффициентов есть НОД, разделите на него все три коэффициента. Решение такого упрощенного уравнения также будет решением исходного уравнения.
- Например, если все три коэффициента четные, разделите их как минимум на 2. Например:
  - $42x+36y=48$ (все члены делятся на 2)
  - $21x+18y=24$ (теперь все члены делятся на 3)
  - $7x+6y=8$ (это уравнение больше нельзя упростить)
3
Проверьте, можно ли решить уравнение. В некоторых случаях можно сразу заявить, что уравнение не имеет решений. Если коэффициент «С» не делится на НОД коэффициентов «А» и «В», у уравнения нет решений.
- Например, если оба коэффициента $A$ и $B$ четные, то и коэффициент $C$ должен быть четным. Но если $C$ нечетный, то решения нет.
  - У уравнения $2x+4y=21$ нет целочисленных решений.
  - У уравнения $5x+10y=17$ нет целочисленных решений, так как левая часть уравнения делится на 5, а правая — нет.
Реклама

Часть 2

Часть 2 из 4:

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

Загрузить PDF

1
Уясните алгоритм Евклида. Это ряд повторных делений, в котором предыдущий остаток используется как следующий делитель. Последний делитель, который делит числа нацело, является наибольшим общим делителем (НОД) двух чисел. ^{[1]
X
Источник информации}
- Например, найдем НОД чисел 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
Примените алгоритм Евклида к коэффициентам «A» и «B». Когда вы запишете линейное уравнение в стандартной форме, определите коэффициенты «A» и «B», а затем примените к ним алгоритм Евклида, чтобы найти НОД. Например, дано линейное уравнение $87x-64y=3$ . ^{[2]
X
Источник информации}
- Вот алгоритм Евклида для коэффициентов А=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$
Поскольку последним делителем было число 1, НОД 87 и 64 равен 1. Таким образом, 87 и 64 являются простыми числами по отношению друг к другу. ^{[3]
X
Источник информации}
4
Проанализируйте полученный результат. Когда вы найдете НОД коэффициентов $A$ и $B$ , сравните его с коэффициентом $C$ исходного уравнения. Если $C$ делится на НОД $A$ и $B$ , уравнение имеет целочисленное решение; в противном случае у уравнения нет решений. ^{[4]
X
Источник информации}
- Например, уравнение $87x-64y=3$ можно решить, потому что 3 делится на 1 (НОД=1).
- Например, предположим, что НОД=5. 3 не делится на 5 нацело, поэтому такое уравнение не имеет целочисленных решений.
- Как показано ниже, если уравнение имеет одно целочисленное решение, оно также имеет бесконечное множество других целочисленных решений.
Реклама

Часть 3

Часть 3 из 4:

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

Загрузить PDF

1
Пронумеруйте шаги вычисления НОД. Чтобы найти решение линейного уравнения, нужно использовать алгоритм Евклида в качестве основы процесса подстановки и упрощения. ^{[5]
X
Источник информации}
- Начните с нумерации шагов вычисления НОД. Процесс вычисления выглядит так:
  - ${\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
Обратите внимание на последний шаг, где есть остаток. Перепишите уравнение этого шага так, чтобы изолировать остаток. ^{[6]
X
Источник информации}
- В нашем примере последний шаг с остатком — это шаг 6. Остаток равен 1. Перепишите уравнение шага 6 следующим образом:
  - $1=3-(1*2)$
3
Изолируйте остаток предыдущего шага. Этот процесс представляет собой пошаговое «перемещение вверх». Каждый раз вы будете изолировать остаток в уравнении предыдущего шага. ^{[7]
X
Источник информации}
- Изолируйте остаток уравнения шага 5:
  - $2=5-(1*3)$ или $2=5-3$
4
Сделайте замену и упростите. Обратите внимание, что уравнение шага 6 содержит число 2, а в уравнении шага 5 число 2 изолировано. Поэтому вместо «2» в уравнении шага 6 подставьте выражение шага 5: ^{[8]
X
Источник информации}
- $1=3-2$ (уравнение шага 6)
- $1=3-(5-3)$ (вместо 2 подставили выражение)
- $1=3-5+3$ (раскрыли скобки)
- $1=2(3)-5$ (упростили)
5
Повторите процесс подстановки и упрощения. Повторите описанный процесс, перемещаясь по алгоритму Евклида в обратном порядке. Каждый раз вы будете переписывать уравнение предыдущего шага и подставлять его в последнее полученное уравнение. ^{[9]
X
Источник информации}
- Последним рассмотренным шагом был шаг 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
Продолжите процесс подстановки и упрощения. Этот процесс будет повторяться до тех пор, пока вы не достигнете первоначального шага алгоритма Евклида. Цель процесса — записать уравнение с коэффициентами 87 и 64 исходного уравнения, которое нужно решить. В нашем примере: ^{[10]
X
Источник информации}
- $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
Перепишите полученное уравнение в соответствии с исходными коэффициентами. Когда вы вернетесь к первому шагу алгоритма Евклида, вы увидите, что полученное уравнение содержит два коэффициента исходного уравнения. Перепишите уравнение так, чтобы порядок его членов соответствовал коэффициентам исходного уравнения. ^{[11]
X
Источник информации}
- В нашем примере исходное уравнение $87x-64y=3$ . Поэтому перепишите полученное уравнение так, чтобы коэффициенты привести в соответствие. Обратите особое внимание на коэффициент «64». В исходном уравнении этот коэффициент отрицательный, а в алгоритме Евклида — положительный. Поэтому множитель 34 нужно сделать отрицательным. Окончательное уравнение запишется так:
  - $87(-25)-64(-34)=1$
8
Примените соответствующий множитель, чтобы найти решение. Обратите внимание, что в нашем примере НОД=1, поэтому окончательное уравнение равно 1. Но исходное уравнение (87x-64y) равно 3. Поэтому все члены окончательного уравнения нужно умножить на 3, чтобы получить решение: ^{[12]
X
Источник информации}
- $87(-25*3)-64(-34*3)=1*3$
- $87(-75)-64(-102)=3$
9
Запишите целочисленное решение уравнения. Числа, которые умножаются на коэффициенты исходного уравнения, являются решениями этого уравнения.
- В нашем примере запишите решение в виде пары координат: $(x,y)=(-75,-102)$ .
Реклама

Часть 4

Часть 4 из 4:

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

Загрузить PDF

1
Уясните, что существует бесконечное множество решений. Если линейное уравнение имеет одно целочисленное решение, то оно должно иметь бесконечно множество целочисленных решений. Вот краткое доказательство (в алгебраической форме): ^{[13]
X
Источник информации}
- $Ax+By=C$
- $A(x+B)+B(y-A)=C$ (если прибавить «B» к «x» и вычесть «A» из «y», значение исходного уравнения не изменится)
2
Запишите исходные значения «x» и «y». Шаблон для вычисления последующих (бесконечных) решений начинается с единственного решения, которое вы уже нашли. ^{[14]
X
Источник информации}
- В нашем примере решение представляет собой пару координат $(x,y)=(-75,-102)$ .
3
Прибавьте коэффициент «B» к значению «x». Сделайте это, чтобы найти новое значение «x». ^{[15]
X
Источник информации}
- В нашем примере x=-75, а В=-64:
  - $x=-75+(-64)=-139$
- Таким образом, новое значение «х»: x=-139.
4
Вычтите коэффициент «A» из значения «y». Чтобы значение исходного уравнения не изменилось, при прибавлении одного числа к «x» нужно вычесть другое число из «y».
- В нашем примере y=-102, а А=87:
  - $y=-102-87=-189$
- Таким образом, новое значение «у»: у=-189.
- Новая пара координат запишется так: $(x,y)=(-139,-189)$ .
5
Проверьте решение. Чтобы убедиться, что новая пара координат является решением исходного уравнения, подставьте значения в уравнение. ^{[16]
X
Источник информации}
- $87x-64y=3$
- $87(-139)-64(-189)=3$
- $3=3$
- Поскольку равенство соблюдено, решение верное.
6
Запишите выражения для нахождения множества решений. Значения «x» будут равны исходному решению плюс любое кратное коэффициента «В». Это можно записать в виде следующего выражения: ^{[17]
X
Источник информации}
- x(k)=x+k(B), где «x(k)» — множество значений «х», а «x» — исходное (первое) значение «x», которое вы нашли.
  - В нашем примере:
  - $x(k)=-75-64k$
- y(k)=y-k(A), где «у(k)» — множество значений «у», а «у» — исходное (первое) значение «у», которое вы нашли.
  - В нашем примере:
  - $y(k)=-102-87k$
Реклама