Загрузить PDF
Загрузить PDF
Чтобы решить линейное диофантово уравнение, нужно найти значения переменных «x» и «y», которые являются целыми числами. Целочисленное решение сложнее обычного и требует определенного набора действий. Сначала необходимо вычислить наибольший общий делитель (НОД) коэффициентов, а затем найти решение. Если вы нашли одно целочисленное решение линейного уравнения, можно применить простой шаблон, чтобы найти бесконечное множество других решений.
Шаги
-
Запишите уравнение в стандартной форме. Линейное уравнение — это уравнение, в котором показатели степени переменных не превышают 1. Чтобы решить такое линейное уравнение, сначала запишите его в стандартной форме. Стандартная форма линейного уравнения выглядит так: , где и — целые числа.
- Если уравнение дано в другой форме, приведите его к стандартной форме с помощью основных алгебраических действий. Например, дано уравнение . Приведите подобные члены и запишите уравнение так: .
-
Упростите уравнение (если можно). Когда вы запишете уравнение в стандартной форме, посмотрите на коэффициенты и . Если у этих коэффициентов есть НОД, разделите на него все три коэффициента. Решение такого упрощенного уравнения также будет решением исходного уравнения.
- Например, если все три коэффициента четные, разделите их как минимум на 2. Например:
- (все члены делятся на 2)
- (теперь все члены делятся на 3)
- (это уравнение больше нельзя упростить)
- Например, если все три коэффициента четные, разделите их как минимум на 2. Например:
-
Проверьте, можно ли решить уравнение. В некоторых случаях можно сразу заявить, что уравнение не имеет решений. Если коэффициент «С» не делится на НОД коэффициентов «А» и «В», у уравнения нет решений.
- Например, если оба коэффициента
и
четные, то и коэффициент
должен быть четным. Но если
нечетный, то решения нет.
- У уравнения нет целочисленных решений.
- У уравнения нет целочисленных решений, так как левая часть уравнения делится на 5, а правая — нет.
Реклама - Например, если оба коэффициента
и
четные, то и коэффициент
должен быть четным. Но если
нечетный, то решения нет.
-
Уясните алгоритм Евклида. Это ряд повторных делений, в котором предыдущий остаток используется как следующий делитель. Последний делитель, который делит числа нацело, является наибольшим общим делителем (НОД) двух чисел. [1] X Источник информации
- Например, найдем НОД чисел 272 и 36 с помощью алгоритма Евклида:
- — разделите большее число (272) на меньшее (36) и обратите внимание на остаток (20);
- — разделите предыдущий делитель (36) на предыдущий остаток (20). Обратите внимание на новый остаток (16);
- — разделите предыдущий делитель (20) на предыдущий остаток (16). Обратите внимание на новый остаток (4);
- — разделите предыдущий делитель (16) на предыдущий остаток (4). Так как остаток равен 0, можно сказать, что 4 является НОДом исходных двух чисел 272 и 36.
- Например, найдем НОД чисел 272 и 36 с помощью алгоритма Евклида:
-
Примените алгоритм Евклида к коэффициентам «A» и «B». Когда вы запишете линейное уравнение в стандартной форме, определите коэффициенты «A» и «B», а затем примените к ним алгоритм Евклида, чтобы найти НОД. Например, дано линейное уравнение . [2] X Источник информации
- Вот алгоритм Евклида для коэффициентов А=87 и В=64:
- Вот алгоритм Евклида для коэффициентов А=87 и В=64:
-
Найдите наибольший общий делитель (НОД). Поскольку последним делителем было число 1, НОД 87 и 64 равен 1. Таким образом, 87 и 64 являются простыми числами по отношению друг к другу. [3] X Источник информации
-
Проанализируйте полученный результат. Когда вы найдете НОД коэффициентов и , сравните его с коэффициентом исходного уравнения. Если делится на НОД и , уравнение имеет целочисленное решение; в противном случае у уравнения нет решений. [4] X Источник информации
- Например, уравнение можно решить, потому что 3 делится на 1 (НОД=1).
- Например, предположим, что НОД=5. 3 не делится на 5 нацело, поэтому такое уравнение не имеет целочисленных решений.
- Как показано ниже, если уравнение имеет одно целочисленное решение, оно также имеет бесконечное множество других целочисленных решений.
Реклама
-
Пронумеруйте шаги вычисления НОД. Чтобы найти решение линейного уравнения, нужно использовать алгоритм Евклида в качестве основы процесса подстановки и упрощения. [5] X Источник информации
- Начните с нумерации шагов вычисления НОД. Процесс вычисления выглядит так:
- Начните с нумерации шагов вычисления НОД. Процесс вычисления выглядит так:
-
Обратите внимание на последний шаг, где есть остаток. Перепишите уравнение этого шага так, чтобы изолировать остаток. [6] X Источник информации
- В нашем примере последний шаг с остатком — это шаг 6. Остаток равен 1. Перепишите уравнение шага 6 следующим образом:
- В нашем примере последний шаг с остатком — это шаг 6. Остаток равен 1. Перепишите уравнение шага 6 следующим образом:
-
Изолируйте остаток предыдущего шага. Этот процесс представляет собой пошаговое «перемещение вверх». Каждый раз вы будете изолировать остаток в уравнении предыдущего шага. [7] X Источник информации
- Изолируйте остаток уравнения шага 5:
- или
- Изолируйте остаток уравнения шага 5:
-
Сделайте замену и упростите. Обратите внимание, что уравнение шага 6 содержит число 2, а в уравнении шага 5 число 2 изолировано. Поэтому вместо «2» в уравнении шага 6 подставьте выражение шага 5: [8] X Источник информации
- (уравнение шага 6)
- (вместо 2 подставили выражение)
- (раскрыли скобки)
- (упростили)
-
Повторите процесс подстановки и упрощения. Повторите описанный процесс, перемещаясь по алгоритму Евклида в обратном порядке. Каждый раз вы будете переписывать уравнение предыдущего шага и подставлять его в последнее полученное уравнение. [9] X Источник информации
- Последним рассмотренным шагом был шаг 5. Поэтому перейдите к шагу 4 и изолируйте остаток в уравнении этого шага:
- Подставьте это выражение вместо «3» в последнее уравнение:
- Последним рассмотренным шагом был шаг 5. Поэтому перейдите к шагу 4 и изолируйте остаток в уравнении этого шага:
-
Продолжите процесс подстановки и упрощения. Этот процесс будет повторяться до тех пор, пока вы не достигнете первоначального шага алгоритма Евклида. Цель процесса — записать уравнение с коэффициентами 87 и 64 исходного уравнения, которое нужно решить. В нашем примере: [10] X Источник информации
-
(подставили выражение из шага 3)
-
(подставили выражение из шага 2)
-
(подставили выражение из шага 1)
-
Перепишите полученное уравнение в соответствии с исходными коэффициентами. Когда вы вернетесь к первому шагу алгоритма Евклида, вы увидите, что полученное уравнение содержит два коэффициента исходного уравнения. Перепишите уравнение так, чтобы порядок его членов соответствовал коэффициентам исходного уравнения. [11] X Источник информации
- В нашем примере исходное уравнение
. Поэтому перепишите полученное уравнение так, чтобы коэффициенты привести в соответствие. Обратите особое внимание на коэффициент «64». В исходном уравнении этот коэффициент отрицательный, а в алгоритме Евклида — положительный. Поэтому множитель 34 нужно сделать отрицательным. Окончательное уравнение запишется так:
- В нашем примере исходное уравнение
. Поэтому перепишите полученное уравнение так, чтобы коэффициенты привести в соответствие. Обратите особое внимание на коэффициент «64». В исходном уравнении этот коэффициент отрицательный, а в алгоритме Евклида — положительный. Поэтому множитель 34 нужно сделать отрицательным. Окончательное уравнение запишется так:
-
Примените соответствующий множитель, чтобы найти решение. Обратите внимание, что в нашем примере НОД=1, поэтому окончательное уравнение равно 1. Но исходное уравнение (87x-64y) равно 3. Поэтому все члены окончательного уравнения нужно умножить на 3, чтобы получить решение: [12] X Источник информации
-
Запишите целочисленное решение уравнения. Числа, которые умножаются на коэффициенты исходного уравнения, являются решениями этого уравнения.
- В нашем примере запишите решение в виде пары координат: .
Реклама
-
Уясните, что существует бесконечное множество решений. Если линейное уравнение имеет одно целочисленное решение, то оно должно иметь бесконечно множество целочисленных решений. Вот краткое доказательство (в алгебраической форме): [13] X Источник информации
- (если прибавить «B» к «x» и вычесть «A» из «y», значение исходного уравнения не изменится)
-
Запишите исходные значения «x» и «y». Шаблон для вычисления последующих (бесконечных) решений начинается с единственного решения, которое вы уже нашли. [14] X Источник информации
- В нашем примере решение представляет собой пару координат .
-
Прибавьте коэффициент «B» к значению «x». Сделайте это, чтобы найти новое значение «x». [15] X Источник информации
- В нашем примере x=-75, а В=-64:
- Таким образом, новое значение «х»: x=-139.
- В нашем примере x=-75, а В=-64:
-
Вычтите коэффициент «A» из значения «y». Чтобы значение исходного уравнения не изменилось, при прибавлении одного числа к «x» нужно вычесть другое число из «y».
- В нашем примере y=-102, а А=87:
- Таким образом, новое значение «у»: у=-189.
- Новая пара координат запишется так: .
- В нашем примере y=-102, а А=87:
-
Проверьте решение. Чтобы убедиться, что новая пара координат является решением исходного уравнения, подставьте значения в уравнение. [16] X Источник информации
- Поскольку равенство соблюдено, решение верное.
-
Запишите выражения для нахождения множества решений. Значения «x» будут равны исходному решению плюс любое кратное коэффициента «В». Это можно записать в виде следующего выражения: [17] X Источник информации
- x(k)=x+k(B), где «x(k)» — множество значений «х», а «x» — исходное (первое) значение «x», которое вы нашли.
- В нашем примере:
- y(k)=y-k(A), где «у(k)» — множество значений «у», а «у» — исходное (первое) значение «у», которое вы нашли.
- В нашем примере:
Реклама - x(k)=x+k(B), где «x(k)» — множество значений «х», а «x» — исходное (первое) значение «x», которое вы нашли.
Источники
- ↑ http://mathworld.wolfram.com/EuclideanAlgorithm.html
- ↑ http://mathworld.wolfram.com/EuclideanAlgorithm.html
- ↑ http://mathworld.wolfram.com/EuclideanAlgorithm.html
- ↑ http://mathworld.wolfram.com/EuclideanAlgorithm.html
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
- ↑ https://brilliant.org/wiki/linear-diophantine-equations-one-equation/
- ↑ https://brilliant.org/wiki/linear-diophantine-equations-one-equation/
- ↑ https://brilliant.org/wiki/linear-diophantine-equations-one-equation/
- ↑ https://brilliant.org/wiki/linear-diophantine-equations-one-equation/
- ↑ https://brilliant.org/wiki/linear-diophantine-equations-one-equation/
Об этой статье
Эту страницу просматривали 91 479 раз.
Реклама
