Разложение на множители диофантовых уравнений

Вторая глава: Диофантовы уравнения степени выше первой. Решение диофантовых уравнений методом разложения на множители

Диофантовы уравнения степени выше первой.

Решение диофантовых уравнений методом разложения на множители.

Задача 1. Решить в целых числах уравнение

Решение. Запишем уравнение в виде

Произведение двух целых чисел может равняться 1 только в том случае, когда оба они равны 1. Т. е. исходное уравнение равносильно совокупности

с решениями (0,0) и (2,2).

Задача 2. Решить в простых числах уравнение

Решение. Рассмотрим два случая в зависимости от четности переменной x.

a) Пусть x — нечетное число. Подстановка x = 2t + 1 приводит исходное уравне­ние к виду

Следовательно, y2 кратно 2. Так как y — простое число, то y = 2. Отсюда х= =3.

b) Пусть x — четное число. Так как x — простое число, то x = 2. Следовательно, т. е. уравнение неразрешимо в простых числах.

Следовательно, уравнение имеет в классе простых чисел единственное реше­ние (3;2).

Задача 3. Доказать, что уравнение

имеет бесконечно много решений в натуральных числах.

Решение. Нетрудно заметить, что (3,2) — одно из решений исходного уравне­ния. С другой стороны из тождества

(x2 + 2y2)2 — 2(2xy)2 = (x2 — 2y2)2

следует, что если (x, y) — решение данного уравнения, то пара (x2 + 2y2 , 2xy) также явля­ется его решением. Используя этот факт, рекуррентно определим бесконеч­ную последовательность (xn, yn) различных решений исходного уравнения:

(x1 , y1) = (3,2) и xn+1 = xn2 + 2yn2, yn+1 = 2xnyn, n ∈ N*.

Задача 4. Доказать, что уравнение

неразрешимо в целых положительных числах.

Решение. Нетрудно заметить, что исходное уравнение равносильно уравнению

Метод разложения на множители.

Содержание.

Введение 3

Основная часть

Глава 1 Общие сведения о решении уравнений в целых числах.

1.1 Диофантовы уравнения. 4

1.2 Историческая справка. 5

Глава 2. Способы решения уравнений в целых числах.

2.1 Способ перебора вариантов. 6

2.2 Алгоритм Евклида. 7

2.3 Цепные дроби. 10

2.4 Метод разложения на множители. 11

2.5 Решение уравнений в целых числах как квадратных относительно какой-либо переменной. 15

2.6 Метод остатков. 16

2.7 Метод бесконечного спуска. 17

Глава 2. Известные диофантовы уравнения.

3.1 Теорема Ферма. 19

3.2 Пифагоровы тройки. 21

3.3 Вокруг теоремы Пифагора. 22

3.4 Другие известные диофантовы уравнения. 23

Заключение. 25

Приложение. 26

Библиография. 28

Глава 1. Общие сведения о решении уравнений в целых числах.

Диофантовы уравнения.

Диофантовы уравнения – алгебраические уравнения с целыми коэффициентами или системы таких уравнений, у которых разыскиваются целые или рациональные решения.

Названы по имени древнегреческого учёного Диофанта (3 век до н. э.), в книге которого «Арифметика» впервые обстоятельно исследовались такие уравнения.

Задачи диофантовой «Арифметики» решаются с помощью уравнений, а проблемы решения уравнений относятся скорее к алгебре, чем к арифметике, но они имеют свои особенности:

1) они сводятся к уравнениям или системам уравнений с целочисленными коэффициентами. Как правило, эти системы неопределённые, т. е. число уравнений в них меньше числа неизвестных

2) решения требуется найти только целые, часто натуральные.

При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:

1. Способ перебора вариантов.

2. Алгоритм Евклида.

4. Метод разложения на множители.

5. Решение уравнений в целых числах как квадратных относительно какой-либо переменной.

6. Метод остатков.

7. Метод бесконечного спуска.

Глава 2. Способы решения уравнений в целых числах.

Способ перебора вариантов.

Задача 1.

Допустим, в аквариуме живут осьминоги и морские звёзды. У осьминогов по 8 ног, а у морских звёзд – по 5. Всего конечностей насчитывается 39. Сколько в аквариуме животных?

Решение.

Пусть х — количество морских звёзд, у – количество осьминогов. Тогда у всех осьминогов по 8у ног, а у всех звёзд 5х ног. Составим уравнение: 5х + 8у = 39.

Заметим, что количество животных не может выражаться нецелым или отрицательным числами. Следовательно, если х – целое неотрицательное число, то и у=(39 – 5х)/8 должно быть целым и неотрицательным, а, значит, нужно, чтобы выражение 39 – 5х без остатка делилось на 8. Простой перебор вариантов показывает, что это возможно только при х = 3, тогда у = 3.

Ответ:(3; 3)

Алгоритм Евклида.

Можно найти НОД натуральных чисел a и b, не раскладывая эти числа на простые множители, а применяя процесс деления с остатком. Для этого надо разделить большее из этих чисел на меньшее, потом меньшее из чисел на остаток при первом делении, затем остаток при первом делении на остаток при втором делении и вести этот процесс до тех пор, пока не произойдет деление без остатка. Последний отличный от нуля остаток и есть искомый НОД (a, b).

Чтобы доказать это утверждение, представим описанный процесс в виде следующей цепочки равенств: если a>b, то

Затем r1, . . . , rn — положительные остатки, убывающие с возрастанием номера. Из первого равенства следует, что общий делитель чисел a и b делит r1 и общий делитель b и r1 делит a, поэтому НОД (a,b) = НОД (b, r1) = НОД (r1, r2) = … = НОД (rn -1, rn)= = НОД (rn, 0) = rn.

Утверждение доказано. Приведённый способ нахождения НОД носит название метода последовательного деления с остатком или алгоритма Евклида, поскольку впервые он был изложен в его «Началах».

Обратимся к системе (1). Из первого равенства, выразив остаток r1 через a и b, получим r1 = a – bq0. Продолжая этот процесс, мы можем выразить все остатки через a и b, получим r1 = a – bq0. Подставляя его во второе равенство, найдём r2 = b(1 + q0q1) – aq1. Продолжая этот процесс дальше, мы сможем выразить все остатки через a и b, в том числе и последний: rn = Aa + Bb. В результате нами доказано предложение: если d – наибольший общий делитель натуральных чисел a и b, то найдутся такие целые числа A и B, что d = Aa + Bb. Заметим, что коэффициенты A и B имеют разные знаки; если НОД (a,b) = 1, то Aa + Bb = 1. Как найти числа A и B, видно из алгоритма Евклида.

Перейдем теперь к решению линейного уравнения с двумя неизвестными. Оно имеет вид:

Возможны два случая: либо число c делится на d = НОД(a,b), либо нет. В первом случае можно разделить обе части уравнения на d и свести задачу к решению в целых числах уравнения a1x = b1y = c1, коэффициенты которого a1 = a/d и b1 = b/d взаимно просты. Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число ax + by делиться на d и поэтому не может равняться числу c, которое на d не делится.

Итак, мы можем ограничиться случаем, когда в уравнении (2) коэффициенты a и b взаимно просты. На основании предыдущего предложения найдутся такие целые числа х0 и у0, что ax0 + by0 = 1, откуда пара (сх0, су0) удовлетворяет уравнению (2). Вместе с ней уравнению (2) удовлетворяет бесконечное множество пар (х, у) целых чисел, которые можно найти по формулам

х = сх0 + bt, y = cy0 – at. (3)

Здесь t – любое число. Нетрудно показать, что других целочисленных решений уравнение ах + by = c не имеет. Решение, записанное в виде (3), называется общим решением уравнения (2). Подставив вместо t конкретное целое число, получим его частное решение.

Задача 2.

Найдём, например, целочисленные решения уравнения 2x + 5y = 17. Решение.

Применив к числам 2 и 5 алгоритм Евклида, получим 2 * 3 – 5 = 1. Значит, пара сх0 = 3 * 17, су0 = — 1 * 17 удовлетворяет уравнению 2х + 5у = 17. Поэтому общее решение усходного уравнения таково:

x = 51 + 5t, у = — 17 – 2t, где t принимает любые целые значения. Очевидно, неотрицательные решения отвечают тем t, для которых выполняются неравенства

ì51 + 5t ³ 0

í

î — 17 — 2t ³ 0

Отсюда найдём – 51/5 £ t £ — 17/2. Этим неравенством удовлетворяют числа — 10, — 9. Соответствующие частные решения запишутся в виде пар: (1,3), (6, 1).

Сколько можно купить на 100 монет петухов, кур и цыплят, если всего надо купить 100 птиц, причём петух стоит 5 монет, курица – 4, а 4 цыплёнка – одну монету?

Пусть х – искомое число петухов, у – кур, а 4z – цыплят. Составим систему ìх + у + 4z = 100

î 5x + 4y + z = 100, которую надо решить в целых неотрицательных числах. Умножив первое уравнение системы на 4 , а второе – на (-1) и, сложив результаты, придём к уравнению -x + 15z = 300 с целочисленными решениями x = -300 + 15t, z = t. Подставляя эти значения в первое уравнение, получим y = 400 — 19t. Значит, целочисленные решения системы имеют вид x = -300 + 15t,

y = 400 — 19t, z = t. Из условия задачи вытекает, что

ì -300 + 15t ³ 0

í 400 – 19t ³ 0

î t ³ 0 , откуда 20 £ t £ 21 1/19, т. е. t = 21 или t = 20.

Ответ.

На 100 монет можно купить 20 кур и 80 цыплят, или 15 петухов, 1 курицу и 84 цыплёнка.

Задача 4.

Крестьянка несла на базар корзину яиц. Неосторожный всадник, обгоняя женщину, задел корзину, и все яйца разбились. Желая возместить ущерб, он спросил у крестьянки, сколько яиц было в корзине. Она ответила, что число яиц не знает, но когда она раскладывала их по 2, по 3, по 4, по 5 и по 6, то каждый раз одно яйцо оставалось лишним, а когда она разложила по 7, лишних яиц не осталось. Сколько яиц несла крестьянка на базар?

Решение.

Пусть х – число яиц. Так как х – 1 делится на 2, на 3, на 4, на 5, на 6, то оно делится на их НОК, равное 60. Значит, х имеет вид 60у + 1. Поэтому для ответа на вопрос задачи надо решить в натуральных числах уравнение 60у + 1 = 7z. С помощью алгоритма Евклида находим у0 = -2, z0 = — 17, откуда все целочисленные решения уравнения имеют вид у = -2 + 7t, z = -17 + 60t, где t – любое целое число. Наименьшее положительное решение получаем при t = 1. В этом случае у = 5, z = 43. Итак, крестьянка несла на базар 301 яйцо.

Ответ.

Крестьянка несла на базар 301 яйцо.

Цепные дроби.

Следующий метод связан с непрерывными или цепными дробями.

Обратимся вновь к алгоритму Евклида. Из первого равенства системы (1) вытекает, что дробь a/b можно записать в виде суммы целой части и правильной дроби: a/b = q0 + r1/b. Но r1/b = 1/b/r1, и на основании второго равенства той же системы имеем b/r1 = q1 + r2/r1. Значит, a/b=q0+1/(q1+r2/r1). Далее получим a/b=q0 + 1/(q1+1/(q2+r3/r2)). Продолжим этот процесс до тех пор. Пока не придём к знаменателю qn

В результате мы представим обыкновенную дробь a/b в следующем виде: a / b = q0 + 1 / (q1 + 1 / (…+ 1 / qn)). Эйлер назвал дроби такого вида непрерывными. Приблизительно в тоже время в Германии появился другой термин – цепная дробь. Так за этими дробями и сохранились оба названия. Ввиду громоздкости развёрнутой записи цепной дроби применяют компактную запись [q0; q1, q2, …,qn].

Задача 5.

Представить дробь 40/31 в виде цепной.

Решение.

40/31 = 1 + 9/31 = 1 + 1/3 /9 = 1 + 1/(3 + 4 / 9) = 1 + 1 / (3 + 1 / 9 / 4) = =1 + 1 / (3 + 1 / (2 +1 / 4)) = [1; 3, 2, 4]

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

Метод разложения на множители.

Задача 6.

Решите уравнение в целых числах: x² — y² = 91.

Решение.

Разложим левую часть данного уравнения на множители: (х–у)(х+у)= =91. Так как 91= 1 * 91 =91 * 1=(-1) * (-91) = (-91) * (-1) = 7 * 13 =

= 13 * 7 = (-7) * (-13) = (-13) * (-7), то решение данного уравнения сводится к решению восьми систем:

1)ìx – y = 1

í

îx + y = 91

2)ìx – y =- 1

í

îx + y =- 91

3)ìx – y = -91

í

îx + y = 1

4)ìx – y = -91

í

îx + y = -1

5)ìx – y = 7

í

îx + y = 13

6)ìx – y = -7

í

îx + y = -13

7)ìx – y = 13

í

îx + y = 7

8)ìx – y = -13

í

îx + y = -7

Ответ.

Задача 7.

Решите в целых числах х³ + 91 = у³.

Решение.

Перепишем данное уравнение в следующем виде у³ — х³ = 91, разложим левую часть на множители (у – х)(у² + ху + х²) = 91. Заметим, что у² + ху + х² = (у + х/2)² + ¾х² ³ 0 при уÎR.

Значит, решение данного уравнения сводится к решению следующих систем

1)ìу – х = 1

í

î у² + ху + х² = 91 решая данную систему, получаем (5; 6),(-6; -5);

2)ìу – х = 1

í

î у² + ху + х² = 1 система не имеет решения в целых числах;

3)ìу – х = 13

í

î у² + ху + х² = 7 решений в целых числах нет;

4)ìу – х = 7

í

î у² + ху + х² = 13 решая данную систему, получаем (-3; 4),(-4;3).

Ответ.

Задача 8.

Решите в целых числах ху=х+у

Решение.

Перепишем уравнение в следующем виде ху – х – у + 1 = 1. Левую часть данного уравнения разложим на множители, применяя способ группировки. х(у – 1) – (у – 1) = 1; (у – 1)(х – 1) = 1. Следовательно,

ìу – 1 = 1

í

îх – 1 = 1

ìу – 1 = -1

í

îх – 1 = -1

Ответ.

Задача 9.

Решите в натуральных числах 2х² + 5ху – 12у² = 28.

Решение.

Разложим левую часть данного уравнения на множители, для этого перепишем уравнение в следующем виде: 2х² — 3ху + 8ху – 12у² = 28.

Применяя способ группировки, получим (2х – 3у)(х + 4у) = 28. Так как х, у – натуральные числа, то (х + 4у)ÎN и х + 4у ³ 4, тогда возможны следующие случаи:

1)ì 2х – 3у = 1

í

îх + 4у = 28

2)ì 2х – 3у = 4

í

îх + 4у = 7

решений в натуральных числах нет;

3)ì 2х – 3у = 1

í

îх + 4у = 28

решений в натуральных числах нет.

Ответ.

Задача 10.

Решите в целых числах 2ху = х² + 2у.

Решение.

Перепишем уравнение в следующем виде х² — 2ху + 2у = 0. Данное уравнение также решается методом разложения на множители, однако, с помощью формулы разности квадратов или способа группировки мы не сможем разложить на множители левую часть этого уравнения, поэтому целесообразнее использовать метод выделения полного квадрата.

(х² — 2ху + у²) — у² + 2у – 1 + 1 = 0, (х – у)² — (у – 1)² =-1.

(х – у – у + 1)(х – у + у – 1) = -1, (х – 2у + 1)(х – 1) = -1.

Решение этого уравнения сводится к решению следующих систем:

ì х – 2у + 1= -1илиìх – 1= -1

í í

î х – 1= 1 î х – 2у + 1= 1

(2; 2) решений в нат. числах нет

Ответ.

Итак, из рассмотренных выше уравнений можно сделать вывод, что при решении уравнений методом разложения на множители применяются: формулы сокращённого умножения, способ группировки, метод выделения полного квадрата.

Теперь рассмотрим более сложные уравнения.

Задача 11.

Решите в натуральных числах х² — 4ху – 5у² = 1996.

Решение.

Перепишем уравнение в виде (х²-4ху+4у²)–9у²=1996, (х-4у)²–9у²=1996.

Разложим левую часть на множители (х – 5у)(х + у) = 1996.

1996=1 * 1996=2 * 998=4 * 499= -1 * (-1996)= -2 * (-998) = -4 * (-499).

Так как х Î N, yÎN, то (х + у) Î N, причём (х + у) > 1. Если (х + у)ÎN и (х + у)(х – 5у) = 1996, то (х – 5у) Î N. Тогда решение получившегося уравнения сводится к решению следующих систем

1)ìх — 5у = 1

í

îх + у = 1996

решений в натуральных числах нет

2)ìх — 5у = 499 или ìх — 5у = 4

í í

îх + у = 4îх + у = 499

системы решений в натуральных числах не имеют

3)ìх — 5у = 2 или ìх — 5у = 988

í í

îх + у =998 îх + у =2

(832; 166)решения в натуральных числах нет

Диофантовы уравнения

Что такое «решение задач подбором», и можно ли их решать иначе?

По отзывам сибмам, настоящим камнем преткновения в школьном курсе математики не только для учеников, но и для родителей становятся диофантовы уравнения. Что это такое и как их правильно решать? Разобраться нам помогли учитель математики образовательного центра «Горностай» Аэлита Бекешева и кандидат физико-математических наук Юрий Шанько.

Кто такой Диофант?

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

Первым, кто придумал, как можно записать уравнение, был замечательный ученый Диофант Александрийский. Александрия была большим культурным, торговым и научным центром древнего мира. Этот город существует и сейчас, он находится на Средиземноморском побережье Египта.

Жил Диофант, по-видимому, в III веке н.э. и был последним великим математиком античности. До нас дошли два его сочинения — «Арифметика» (из тринадцати книг сохранилось шесть) и «О многоугольных числах» (в отрывках). Творчество Диофанта оказало большое влияние на развитие алгебры, математического анализа и теории чисел.

А ведь вы знаете кое-что о диофантовых уравнениях…

Диофантовы уравнения знают все! Это задачки для учеников младших классов, которые решаются подбором.

” Например, «сколькими различными способами можно расплатиться за мороженое ценой 96 копеек, если у вас есть только копейки и пятикопеечные монеты?»

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

” Зачастую мамы (особенно те, кто окончил школу еще при развитом социализме) полагают, что основная цель таких задач – научить детей расплачиваться мелочью за мороженое. И вот, когда они искренне убеждены, что раскладывание мелочи кучками осталось далеко в прошлом, их любимый семиклассник (или восьмиклассник) подходит с неожиданным вопросом: «Мама, как это решать?», и предъявляет уравнение с двумя переменными. Раньше таких задачек в школьном курсе не было (все мы помним, что уравнений должно быть столько же, сколько и переменных), так что мама не-математик нередко впадает в ступор. А ведь это та же самая задача про мелочь и мороженое, только записанная в общем виде!

Кстати, а зачем к ней вдруг возвращаются в седьмом классе? Все просто: цель изучения диофантовых уравнения – дать основы теории целых чисел, которая дальше развивается как в математике, так и в информатике и программировании. Диофантовы уравнения часто встречаются среди задач части «С» единого госэкзамена. Трудность, прежде всего в том, что существует множество методов решения, из которых выпускник должен выбрать один верный. Тем не менее, линейные диофантовы уравнения ax + by = c могут быть решены относительно легко с помощью специальных алгоритмов.

Алгоритмы для решения диофантовых уравнений

— Изучение диофантовых уравнения начинается в углубленном курсе алгебры с 7 класса. В учебнике Ю.Н. Макарычева, Н.Г. Миндюка приводятся некоторые задачи и уравнения, которые решают с использованием алгоритма Евклида и метода перебора по остаткам, — рассказывает Аэлита Бекешева. — Позже, в 8 – 9 классе, когда уже рассматриваем уравнения в целых числах более высоких порядков, показываем ученикам метод разложения на множители, и дальнейший анализ решения этого уравнения, оценочный метод. Знакомим с методом выделения полного квадрата. При изучении свойств простых чисел знакомим с малой теоремой Ферма, одной из основополагающих теорем в теории решений уравнений в целых числах. На более высоком уровне это знакомство продолжается в 10 – 11 классах. В это же время мы подводим ребят к изучению и применению теории «сравнений по модулю», отрабатываем алгоритмы, с которыми знакомились в 7 – 9 классах. Очень хорошо это материал прописан в учебнике А.Г. Мордковича «Алгебра и начала анализа, 10 класс» и Г.В. Дорофеева «Математика» за 10 класс.

Алгоритм Евклида

Сам метод Евклида относится к другой математической задаче – нахождению наибольшего общего делителя: вместо исходной пары чисел записывают новую пару – меньшее число и разность между меньшим и большим числом исходной пары. Это действие продолжают до тех пор, пока числа в паре не уравняются – это и будет наибольший общий делитель . Разновидность алгоритма используется и при решении диофантовых уравнений — сейчас мы вместе с Юрием Шанько покажем на примере, как решать задачи «про монетки».

— Рассматриваем линейное диофантово уравнение ax + by = c, где a, b, c, x и y — целые числа. Как видите, одно уравнение содержит две переменных. Но, как вы помните, нам нужны только целые корни, что упрощает дело — пары чисел, при которых уравнение верно, можно найти.

Впрочем, диофантовы уравнения не всегда имеют решения. Пример: 4x + 14y = 5. Решений нет, т.к. в левой части уравнения при любых целых x и y будет получаться четное число, а 5 — число нечетное. Этот пример можно обобщить. Если в уравнении ax + by = c коэффициенты a и b делятся на какое-то целое d, а число c на это d не делится, то уравнение не имеет решений. С другой стороны, если все коэффициенты (a, b и c) делятся на d, то на это d можно поделить все уравнение.

Например, в уравнении 4x + 14y = 8 все коэффициенты делятся на 2. Делим уравнение на это число и получаем: 2𝑥 + 7𝑦 = 4. Этот прием (деления уравнения на какое-то число) позволяет иногда упростить вычисления.

Зайдем теперь с другой стороны. Предположим, что один из коэффициентов в левой части уравнения (a или b) равен 1. Тогда наше уравнение уже фактически решено. Действительно, пусть, например, a = 1, тогда мы можем в качестве y взять любое целое число, при этом x = c − by. Если научиться сводить исходное уравнение к уравнению, в котором один из коэффициентов равен 1, то мы научимся решать любое линейное диофантово уравнение!

Я покажу это на примере уравнения 2x + 7y = 4.

Его можно переписать в следующем виде: 2(x + 3y) + y = 4.

Введем новую неизвестную z = x + 3y, тогда уравнение запишется так: 2z + y = 4.

Мы получили уравнение с коэффициентом один! Тогда z — любое число, y = 4 − 2z.

Осталось найти x: x = z − 3y = z − 3(4 − 2z) = 7z − 12.

” В этом примере важно понять, как мы перешли от уравнения с коэффициентами 2 и 7 к уравнению с коэффициентами 2 и 1. В данном случае (и всегда!) новый коэффициент (в данном случае — единица) это остаток от деления исходных коэффициентов друг на друга (7 на 2).

В этом примере нам повезло, мы сразу после первой замены получили уравнение с коэффициентом 1. Такое бывает не всегда, но и мы можем повторять предыдущий трюк, вводя новые неизвестные и выписывая новые уравнения. Рано или поздно после таких замен получится уравнение с коэффициентом 1.

Давайте попрообуем решить более сложное уравнение, предлагает Аэлита Бекешева.

Рассмотрим уравнение 13x — 36y = 2.

Шаг №1

36/13=2 (10 в остатке). Таким образом, исходное уравнение можно переписать следующим образом: 13x-13 * 2y-10y=2. Преобразуем его: 13(x-2y)-10y=2. Введем новую переменную z=x-2y. Теперь мы получили уравнение: 13z-10y=2.

Шаг №2

13/10=1 (3 в остатке). Исходное уравнение 13z-10y=2 можно переписать следующим образом: 10z-10y+3z=2. Преобразуем его: 10(z-y)+3z=2. Введем новую переменную m=z-y. Теперь мы получили уравнение: 10m+3z=2.

Шаг №3

10/3=3 (1 в остатке). Исходное уравнение 10m+3z=2 можно переписать следующим образом: 3 * 3m+3z+1m=2. Преобразуем его: 3(3m+z)+1m=2. Введем новую переменную n=3m+z. Теперь мы получили уравнение: 3n+1m=2.

Ура! Мы получили уравнение с коэффициентом единица!

m=2-3n, причем n может быть любым числом. Однако нам нужно найти x и y. Проведем замену переменных в обратном порядке. Помните, мы должны выразить x и y через n, которое может быть любым числом.

y=z-m; z=n-3m, m=2-3n ⇒ z=n-3 * (2-3n), y=n-3*(2-3n)-(2-3n)=13n-8; y=13n-8

x=2y+z ⇒ x=2(13n-8)+(n-3*(2-3n))=36n-22; x=36n-22

Пусть n=5. Тогда y=57, x=158. 13_*(158)-36 _* (57)=2

Да, разобраться не очень просто, зато теперь вы всегда сможете решить в общем виде задачи, которые решаются подбором!

Решаем задачи на подбор чисел

Примеры задач для учеников младших классов, которые решаются подбором: посоревнуйтесь с ребенком, кто решит их быстрее: вы, используя алгорит Евклида, или школьник — подбором?

Задача про лапы

Условия

В клетке сидят куры и кролики. Всего у них 20 лап. Сколько там может быть кур, а сколько — кроликов?

Решение

Пусть у нас будет x кур и y кроликов. Составим уравнение: 2х+4y=20. Сократим обе части уравнения на два: x+2y=10. Следовательно, x=10-2y, где x и y — это целые положительные числа.

Ответ

Число кроликов и куриц: (1; 8), (2; 6), (3; 4), (4; 2), (5; 0)

Согласитесь, получилось быстрее, чем перебирать «пусть в клетке сидит один кролик. »

Задача про монетки

Условия

У одной продавщицы были только пяти- и двухрублевые монетки. Сколькими способами она может набрать 57 рублей сдачи?

Решение

Пусть у нас будет x двухрублевых и y пятирублевых монеток. Составим уравнение: 2х+5y=57. Преобразуем уравнение: 2(x+2y)+y=57. Пусть z=x+2y. Тогда 2z+y=57. Следовательно, y=57-2z, x=z-2y=z-2(57-2z) ⇒ x=5z-114. Обратите внимание, переменная z не может быть меньше 23 (иначе x, число двухрублевых монеток, будет отрицательным) и больше 28 (иначе y, число пятирублевых монеток, будет отрицательным). Все значения от 23 до 28 нам подходят.