Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего

профессионального образования

«Тобольская государственная социально-педагогическая академия

им. Д.И. Менделеева»

Кафедра математики, ТиМОМ

Некоторые диофантовы уравнения

Курсовая работа

студента III курса ФМФ

Матаева Евгения Викторовича

Научный руководитель:

к.ф.-м.н.Валицкас А.И.

Оценка: ____________

Тобольск – 2011

Введение……………………………………………………………………........ 2

§ 1. Линейные диофантовы уравнения………………………………….. 3

§ 2. Диофантово уравнение x 2 – y 2 = a ………………………………….....9

§ 3. Диофантово уравнение x 2 + y 2 = a …………………………………... 12

§ 4. Уравнение х 2 + х + 1 = 3у 2 …………………………………………….. 16

§ 5. Пифагоровы тройки………………………………………………….. 19

§ 6. Великая теорема Ферма………………………………………………23

Заключение……………………………………………………………….….....29

Список литературы........... ………………………………………………..30

ВВЕДЕНИЕ

Диофантово уравнение – это уравнение вида P (x 1 , … , x n ) = 0 , где левая часть представляет собой многочлен от переменных x 1 , … , x n с целыми коэффициентами. Любой упорядоченный набор (u 1 ; … ; u n ) целых чисел со свойством P (u 1 , … , u n ) = 0 называется (частным) решением диофантова уравнения P (x 1 , … , x n ) = 0 . Решить диофантово уравнение – значит найти все его решения, т.е. общее решение этого уравнения.

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

Для этого, необходимо ответить на следующие вопросы:

а. Всегда ли диофантово уравнение имеет решение, найти условия существования решения.

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

Примеры: 1. Диофантово уравнение 5 x – 1 = 0 не имеет решений.

2. Диофантово уравнение 5 x – 10 = 0 имеет решение x = 2 , которое является единственным.

3. Уравнение ln x – 8 x 2 = 0 не является диофантовым.

4. Часто уравнения вида P (x 1 , … , x n ) = Q (x 1 , … , x n ) , где P (x 1 , … , x n ) , Q (x 1 , … , x n ) – многочлены с целыми коэффициентами, также называют диофантовыми. Их можно записать в виде P (x 1 , … , x n ) – Q (x 1 , … , x n ) = 0 , который является стандартным для диофантовых уравнений.

5. x 2 – y 2 = a – диофантово уравнение второй степени с двумя неизвестными x и y при любом целом a. Оно имеет решения при a = 1 , но не имеет решений при a = 2 .

§ 1. Линейные диофантовы уравнения

Пусть a 1 , … , a n , с Z . Уравнение вида a 1 x 1 + … + a n x n = c называется линейным диофантовым уравнением с коэффициентами a 1 , … , a n , правой частью c и неизвестными x 1 , … , x n . Если правая часть с линейного диофантова уравнения нулевая, то такое диофантово уравнение называется однородным.

Наша ближайшая цель – научиться находить частные и общие решения линейных диофантовых уравнений с двумя неизвестными. Очевидно, что любое однородное диофантово уравнение a 1 x 1 + … + a n x n = 0 всегда имеет частное решение (0; … ; 0).

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

Теорема (о существовании решения линейного диофантова уравнения). Линейное диофантово уравнение a 1 x 1 + … + a n x n = c , не все коэффициенты которого равны нулю, имеет решение тогда и только тогда, когда НОД(a 1 , … , a n ) | c.

Доказательство. Необходимость условия очевидна: НОД(a 1 , … , a n ) | a i (1 i n ) , так что НОД(a 1 , … , a n ) | (a 1 x 1 + … + a n x n ) , а значит, делит и

c = a 1 x 1 + … + a n x n .

Пусть D = НОД(a 1 , … , a n ) , с = Dt и a 1 u 1 + … + a n u n = D – линейное разложение наибольшего общего делителя чисел a 1 , … , a n . Умножая обе части на t , получим a 1 (u 1 t ) + … + a n (u n t ) = Dt = c , т.е. целочисленная

n -ка (x 1 t ; … ; x n t) является решением исходного уравнения с n неизвестными.

Теорема доказана.

Эта теорема даёт конструктивный алгоритм для нахождения частных решений линейных диофантовых уравнений.

Примеры: 1. Линейное диофантово уравнение 12x+21y = 5 не имеет решений, поскольку НОД(12, 21) = 3 не делит 5 .

2. Найти частное решение диофантова уравнения 12x+21y = 6 .

Очевидно, что теперь НОД(12, 21) = 3 | 6 , так что решение существует. Запишем линейное разложение НОД(12, 21) = 3 = 122 + 21(–1) . Поэтому пара (2; –1) – частное решение уравнения 12x+21y = 3 , а пара (4; –2) – частное решение исходного уравнения 12x+21y = 6 .

3. Найти частное решение линейного уравнения 12x + 21y – 2z = 5 .

Так как (12, 21, –2) = ((12, 21), –2) = (3, –2) = 1 | 5 , то решение существует. Следуя доказательству теоремы, вначале найдём решение уравнения (12,21)х–2у=5 , а затем, подставив линейное разложение наибольшего общего делителя из предыдущей задачи, получим решение исходного уравнения.

Для решения уравнения 3х – 2у = 5 запишем линейное разложение НОД(3, –2) = 1 = 31 – 21 очевидно. Поэтому пара чисел (1; 1) является решением уравнения 3 x – 2 y = 1 , а пара (5; 5) – частным решением диофантова уравнения 3х – 2у = 5 .

Итак, (12, 21)5 – 25 = 5 . Подставляя сюда найденное ранее линейное разложение (12, 21) = 3 = 122 + 21(–1) , получим (122+21(–1))5 – 25 = 5 , или 1210 + 21(–5) – 25 = 5 , т.е. тройка целых чисел (10; –5; 5) является частным решением исходного диофантова уравнения 12x + 21y – 2z = 5 .

Теорема (о структуре общего решения линейного диофантова уравнения). Для линейного диофантова уравнения a 1 x 1 + … + a n x n = c справедливы следующие утверждения:

(1) если = (u 1 ; … ; u n ), = (v 1 ; … ; v n ) – его частные решения, то разность (u 1 – v 1 ; … ; u n – v n ) – частное решение соответствующего однородного уравнения a 1 x 1 + … + a n x n = 0 ,

(2) множество частных решений линейного диофантова однородного уравнения a 1 x 1 + … + a n x n = 0 замкнуто относительно сложения, вычитания и умножения на целые числа,

(3) если M – общее решение данного линейного диофантова уравнения, а L – общее решение соответствующего ему однородного диофантова уравнения, то для любого частного решения = (u 1 ; … ; u n ) исходного уравнения верно равенство M = + L .

Доказательство. Вычитая равенство a 1 v 1 + … + a n v n = c из равенства a 1 u 1 + … + a n u n = c , получим a 1 (u 1 – v 1 ) + … + a n (u n – v n ) = 0 , т. е. набор

(u 1 – v 1 ; … ; u n – v n ) – частное решение линейного однородного диофантова уравнения a 1 x 1 + … + a n x n = 0 . Таким образом, доказано, что

= (u 1 ; … ; u n ), = (v 1 ; … ; v n ) M L .

Это доказывает утверждение (1).

Аналогично доказывается утверждение (2):

, L z Z L z L .

Для доказательства (3) вначале заметим, что M + L . Это следует из предыдущего: M+L .

Обратно, если = (l 1 ; … ; l n ) L и = (u 1 ; … ; u n ) M , то M :

a 1 (u 1 + l 1 )+ …+a n (u n + l n ) = (a 1 u 1 + … + a n u n )+(a 1 l 1 + … + a n l n ) = c + 0 = c .

Таким образом, + L M , и в итоге M = + L .

Теорема доказана.

Доказанная теорема имеет наглядный геометрический смысл. Если рассмотреть линейное уравнение a 1 x 1 + … + a n x n = c , где х i R , то как известно из геометрии, оно определяет в пространстве R n гиперплоскость, полученную из плоскости L c однородным уравнением a 1 x 1 + … +a n x n =0 , проходящей через начало координат, сдвигом на некоторый вектор R n . Поверхность вида + L называют также линейным многообразием с направляющим пространством L и вектором сдвига . Таким образом, доказано, что общее решение М диофантова уравнения a 1 x 1 + … + a n x n = c состоит из всех точек некоторого линейного многообразия, имеющих целые координаты. При этом координаты вектора сдвига тоже целые, а множество L решений однородного диофантова уравнения a 1 x 1 + … + a n x n = 0 состоит из всех точек направляющего пространства с целыми координатами. По этой причине часто говорят, что множество решений произвольного диофантова уравнения образует линейное многообразие с вектором сдвига и направляющим пространством L .

Пример: для диофантова уравнения х – у = 1 общее решение M имеет вид (1+у; у), где у Z , его частное решение = (1; 0) , а общее решение L однородного уравнения х – у = 0 запишется в виде (у; у) , где у Z . Таким образом, можно нарисовать следующую картинку, на которой решения исходного диофантова уравнения и соответствующего однородного диофантова уравнения изображены жирными точками в линейном многообразии М и пространстве L соответственно.

2. Найти общее решение диофантова уравнения 12x + 21y – 2z = 5 .

Частное решение (10; –5; 5) этого уравнения было найдено ранее, найдём общее решение однородного уравнения 12x + 21y – 2z = 0 , эквивалентного диофантову уравнению 12 x + 21 y = 2 z .

Для разрешимости этого уравнения необходимо и достаточно выполнение условия НОД(12, 21) = 3 | 2z, т.е. 3 | z или z = 3t для некоторого целого t . Сокращая обе части на 3 , получим 4x + 7y = 2t . Частное решение (2; –1) диофантова уравнения 4x + 7y = 1 найдено в предыдущем примере. Поэтому (4t ; –2t) – частное решение уравнения 4x + 7y = 2t при любом

t Z . Общее решение соответствующего однородного уравнения

(7 u ; –4 u ) уже найдено. Таким образом, общее решение уравнения 4x + 7y = 2t имеет вид: (4t + 7 u ; –2t – 4 u ) , а общее решение однородного уравнения 12x + 21y – 2z = 0 запишется так:

(4t + 7 u ; –2t – 4 u ; 3t) .

Нетрудно убедиться, что этот результат соответствует сформулированной выше без доказательства теореме о решениях однородного диофантова уравнения а 1 х 1 + … + а n х n = 0 : если Р = , то Р и

(u ; t ) P – общее решение рассматриваемого однородного уравнения.

Итак, общее решение диофантова уравнения 12x + 21y – 2z = 5 выглядит так: (10 + 4t + 7 u ; –5 – 2t – 4 u ; 5 + 3t) .

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

12x + 21y – 2z = 5 12x + (102 + 1)y – 2z = 5

12x + y – 2(z – 10y) = 5

Таким образом, общее решение рассматриваемого уравнения можно записать и так: (x; 5 – 12x + 2u ; 50 – 120x + 21u) , где x, u – произвольные целые параметры.

§ 2. Диофантово уравнение x 2 – y 2 = a

Примеры: 1. При a = 0 получаем бесконечное число решений: x = y или x = – y для любого y Z .

2. При a = 1 имеем x 2 – y 2 = 1 (x + y )(x – y ) = 1 . Таким образом, число 1 разложено в произведение двух целых множителей x + y и x – y (важно, что x , y – целые!). Поскольку у числа 1 всего два разложения в произведение целых множителей 1 = 11 и 1 = (–1)(–1) , то получаем две возможности: .

3. Для a = 2 имеем x 2 – y 2 = 2 (x + y )(x – y ) = 2. Действуя аналогично предыдущему, рассматриваем разложения

2=12=21=(–1)(–2)=(–2)(–1), составляем системы: , которые, в отличие от предыдущего примера, не имеют решений. Так что нет решений и у рассматриваемого диофантова уравнения x 2 – y 2 = 2.

4. Предыдущие рассмотрения наводят на некоторые выводы. Решения уравнения x 2 – y 2 = a находятся по разложению a = km в произведение целых чисел из системы . Эта система имеет целые решения тогда и только тогда, когда k + m и k – m чётны, т.е. когда числа k и m одной чётности (одновременно чётны или нечётны). Таким образом, диофантово уравнение x 2 – y 2 = a имеет решение тогда и только тогда, когда a допускает разложение в произведение двух целых множителей одной чётности. Остаётся только найти все такие a .

Теорема (об уравнении x 2 – y 2 = a ). (1) Уравнение x 2 – y 2 = 0 имеет бесконечное множество решений .

(2) Любое решение уравнения получается имеет вид , где a = km – разложение числа a в произведение двух целых множителей одной чётности.

(3) Уравнение x 2 – y 2 = a имеет решение тогда и только тогда, когда a 2 (mod 4).

Доказательство. (1) уже доказано.

(2) уже доказано.

(3) () Пусть вначале диофантово уравнение x 2 – y 2 = a имеет решение. Докажем, что a 2 (mod 4) . Если a = km – разложение в произведение целых чисел одной чётности, то при чётных k и m имеем k = 2 l , m = 2 n и a = km = 4 ln 0 (mod 4) . В случае же нечётных k , m их произведение a также нечётно, разность a – 2 нечётна и не делится на 4 , т.е. снова

a 2 (mod 4).

() Если теперь a 2 (mod 4) , то можно построить решение уравнения x 2 – y 2 = a . Действительно, если a нечётно, то a = 1 a – разложение в произведение целых нечётных чисел, так что – решение диофантова уравнения. Если же a чётно, то ввиду a 2 (mod 4) получаем, что 4 | a , a = 4 b = 2(2 b ) – разложение в произведение целых чётных чисел, так что – решение диофантова уравнения.

Теорема доказана.

Примеры: 1. Диофантово уравнение x 2 – y 2 = 2012 не имеет решений, т.к. 2010 = 4502 + 2 2 (mod 4).

2. Диофантово уравнение x 2 – y 2 = 2011 имеет решения, т.к.

2011 3 (mod 4). Имеем очевидные разложения

2011 = 12011 = 20111 = (–1)(–2011) = (–2011)(–1),

по каждому из которых находим решения (комбинации знаков любые). Других решений нет, т.к. число 2011 простое (?!).

§ 3. Диофантово уравнение x 2 + y 2 = a

Примеры: 1. 0 = 0 2 + 0 2 , 1 = 0 2 + 1 2 , k 2 = 0 2 + k 2 . Таким образом, очевидно, любой квадрат тривиальным образом представим в виде суммы двух квадратов.

2. 2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 8 = 2 2 + 2 2 , 10 = 1 2 + 3 2 , 13 = 2 2 + 3 2 , 17 = 1 2 + 4 2 , 18 = 3 2 + 3 2 , 20 = 2 2 + 4 2 , …

3. Решений нет для a = 3, 6 = 23, 7, 11, 12 = 2 2 3, 14 = 27, 15 = 35, 19, 21 = 37, 22 = 211, 23, 24 = 32 3 , …

Анализ приведённых результатов способен навести на мысль, что отсутствие решений каким-то образом связано с простыми числами вида

4 n +3 , присутствующими в разложении на множители чисел, не представимых в виде сумм двух квадратов.

Теорема (о представлении натуральных чисел суммами двух квадратов). Натуральное число a представимо в виде суммы двух квадратов тогда и только тогда, когда в его каноническом разложении простые числа вида 4 n + 3 имеют чётные показатели степеней.

Доказательство. Вначале докажем, что если натуральное число a представимо в виде суммы двух квадратов, то в его каноническом разложении все простые числа вида 4 n + 3 должны иметь чётные показатели степеней. Предположим, вопреки доказываемому, что a = р 2 k +1 b = x 2 + y 2 , где

р – простое число вида 4 n +3 и b p . Представим числа х и у в виде

х = Dz , y = Dt , где D = НОД(x , y ) = р s w , p w ; z , t , s N 0 . Тогда получаем равенство р 2 k +1 b = D 2 (z 2 + t 2 ) = р 2 s w 2 (z 2 + t 2 ) , т.е. р 2( k – s )+1 b = w 2 (z 2 + t 2 ) . В левой части равенства присутствует p (нечётная степень не равна нулю), значит, на простое число p делится один из множителей в правой части. Поскольку p w , то р | (z 2 + t 2 ) , где числа z , t взаимно просты. Это противоречит следующей лемме (?!).

Лемма (о делимости суммы двух квадратов на простое число вида

4 n + 3 ). Если простое число р = 4 n +3 делит сумму квадратов двух натуральных чисел, то оно делит каждое из этих чисел.

Доказательство. От противного. Пусть x 2 + y 2 0(mod p ) , но x 0(mod p ) или y 0 (mod p ) . Поскольку x и y симметричны, их можно менять местами, так что можно предполагать, что x p .

Лемма (об обратимости по модулю p ). Для любого целого числа x , не делящегося на простое число p , существует обратный элемент по модулю p – такое целое число 1 u < p , что xu 1 (mod p ).

Доказательство. Число x взаимно простое с p , поэтому можно записать линейное разложение НОД(x , p ) = 1 = xu + pv (u , v Z ) . Ясно, что xu 1(modp ) , т.е. u – обратный элемент к x по модулю p . Если u не удовлетворяет ограничению 1 u < p , то поделив u с остатком на p , получим остаток r u (mod p ) , для которого xr xu 1 (mod p ) и 0 r < p .

Лемма об обратимости по модулю p доказана.

Умножая сравнение x 2 + y 2 0 (mod p ) на квадрат u 2 обратного элемента к x по модулю p , получим 0 = 0u 2 x 2 u 2 + y 2 u 2 = (xu) 2 + (yu) 2 1 + t 2 (mod p).

Таким образом, для t = yu выполнено сравнение t 2 –1 (mod p ) , которое и приведём к противоречию. Ясно, что t p : иначе t 0 (mod p ) и 0 t 2 –1 (mod p ) , что невозможно. По теореме Ферма имеем t p –1 1 (mod p ), что вместе с t 2 –1 (mod p ) и p = 4 n + 3 приводит к противоречию:

1 t p–1 = t 4n+3–1 = t 2(2n+1) = (t 2 ) 2n+1 (–1) 2n+1 = –1 (mod p).

Полученное противоречие показывает, что допущение о x 0 (mod p ) было не верным.

Лемма о делимости суммы двух квадратов на простое число 4 n +3 доказана.

Таким образом, доказано, что число, в каноническое разложение которого входит простое число p = 4 n + 3 в нечётной степени, не представимо в виде суммы двух квадратов.

Докажем теперь, что любое число, в каноническом разложении которого простые числа p = 4 n + 3 участвуют только в чётных степенях, представимо в виде суммы двух квадратов.

Идея доказательства основана на следующем тождестве:

(а 2 + b 2 )(c 2 + d 2 ) = (ac – bd) 2 + (ad + bc) 2 ,

которое можно получить из известного свойства модуля комплексных чисел – модуль произведения равен произведению модулей. Действительно,

| z || t | = | zt | | a + bi || c + di | = |(a + bi )(c + di )|

|a + bi| 2 |c + di| 2 = |(ac – bd) + (ad + bc)i| 2

(а 2 + b 2 )(c 2 + d 2 ) = (ac – bd) 2 + (ad + bc) 2 .

Из этого тождества следует, что если два числа u, v представимы в виде суммы двух квадратов: u = x 2 + y 2 , v = z 2 + t 2 , то и их произведение uv представимо в виде суммы двух квадратов: uv = (xz – yt ) 2 + (xt + yz ) 2 .

Любое натуральное число a > 1 можно записать в виде a = р 1 … р k m 2 , где р i – попарно различные простые числа, m N . Для этого достаточно найти каноническое разложение , записать каждую степень вида r в виде квадрата (r ) 2 при чётном = 2, или в виде r = r (r ) 2 при нечётном = 2 + 1 , а затем сгруппировать отдельно квадраты и оставшиеся одиночные простые числа. Например,

29250 = 23 2 5 3 13 = 2513(35) 2 , m = 15.

Число m 2 обладает тривиальным представлением в виде суммы двух квадратов: m 2 = 0 2 + m 2 . Если доказать представимость в виде суммы двух квадратов всех простых чисел р i (1 i k ) , то используя тождество, будет получено и представление числа a. По условию, среди чисел р 1 , … , р k могут встретиться только 2 = 1 2 + 1 2 и простые числа вида 4 n + 1 . Таким образом, осталось получить представление в виде суммы двух квадратов простого числа р = 4т + 1 . Это утверждение выделим в отдельную теорему (см. ниже)

Например, для a = 29250 = 2513(15) 2 последовательно получаем:

2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 13 = 2 2 + 3 2 ,

25 = (11 – 12) 2 + (12 + 11) 2 = 1 2 + 3 2 ,

2513 = (12 – 33) 2 + (13 + 32) 2 = 7 2 + 9 2 ,

29250 = 2513(15) 2 = (715) 2 + (915) 2 = 105 2 + 135 2 .

Теорема доказана.

§ 4. Уравнение х+ х + 1 = 3у

Займемся теперь уравнением х+x+1=Зу. Оно уже имеет свою историю. В 1950 г. Р. Облат высказал предположение, что, кроме решения

x =у=1 . оно не имеет иных решений в натуральных числах х, у , где х есть нечетное число. В том же году Т. Нагель указал решение x = 313, у =181. Метод, аналогичный изложенному выше для уравнения х+х-2у=0 , позволит нам определить все решения уравнения x +х+1=3у (1)

в натуральных числах x , у. Предположим, что (х, у) есть решение уравнения (1) в натуральных числах, причем х > 1 . Можно легко убедиться, что уравнение(18) не имеет решений в натуральных числах x , у , где х = 2, 3. 4, 5, 6, 7, 8, 9; поэтому должно быть х10.

Покажем, что 12у<7 x +3, 7у>4 x + 2. 4у> 2 x +1 . (2)

Если бы было 12y > 7x+3 , мы имели бы 144у > 49 x +42 x +9 . а так как, в виду (18), 144у= 48 x + 48 x + 48 , то было бы х < 6 x +3 9, откуда

Муниципальное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа №1

г. Павлово.

Научно-исследовательская работа

Методы решения диофантовых уравнений.

Отделение: физико-математическое

Секция: математика

Выполнил:

ученик 8 А класса Трухин Николай (14 лет)

Научный руководитель:

учитель математики

Лефанова Н. А.

г. Павлово

2013 г.

Оглавление

I Введение…………………………………………………………………………3

II Обзор литературы……………………………………………………………....5

III Основная часть…………………………………………………………………6

IV Заключение…………………………………………………………………...15

V Список литературы……………………………………………………………16

VI Приложение…………………………………………………………………..17

Введение.

В 2011-2012 году я выполнял исследовательскую работу на тему: «Решение уравнений в Древней Греции и Индии». При работе над ней я познакомился с трудами Диофанта Александрийского и Мухаммеда аль - Хорезми. В своей прошлой работе я рассмотрел некоторые способы решения уравнений первой степени с двумя неизвестными, познакомился с некоторыми старинными задачами, приводящими к решению уравнений первой степени с двумя неизвестными.

Мухаммед Бен Мусса аль – Хорезми, - или Магомед сын Моисея Хорезмского, состоящий членом «дома мудрости» в Иране, около 820 года нашего летоисчисления написал книгу, где учил решать простые и сложные вопросы арифметики, которые необходимы людям при дележе наследства, составлении завещаний, разделе имущества и судебных делах, в торговле, всевозможных сделках. С именем аль – Хорезми связаны понятия «алгебра», «арабские цифры», «алгоритм». Он отделил алгебру от геометрии, внёс большой вклад в математику исламского средневековья. Мухаммед аль – Хорезми был известен и уважаем, как при жизни, так и после смерти.

Но мне захотелось больше узнать о Диофанте. И тема моего исследования в этом году: «Методы решения диофантовых уравнений»

Диофант Александрийский - один из самых своеобразных древнегреческих математиков, труды которого имели большое значение для алгебры и теории чисел. Из работ Диофанта самой важной является «Арифметика», из 13 книг которой, только 6 сохранились до наших дней. В сохранившихся книгах содержится 189 задач с решениями. В первой книги изложены задачи, приводящиеся к определенным уравнениям первой и второй степени. Остальные пять книг содержат в основном неопределенные уравнения (неопределенными называются уравнения, содержащие более чем одно неизвестное). В этих книгах ещё нет систематической теории неопределённых уравнений, методы решения меняются от случая к случаю. Диофант довольствуется одним решением, целым или дробным, лишь бы оно было положительным. Тем не менее, методы решения неопределённых уравнений, составляют основной вклад Диофанта в математику. В символике Диофанта был один только знак для неизвестного. Решая неопределённые уравнения, он применял в качестве нескольких неизвестных произвольные числа, вместо которых можно было взять и любые другие, что и сохраняло характер общности его решений.

Цель моей работы:

1.Продолжить знакомство с диофантовыми уравнениями.

2.Исследовать методы перебора и рассеивания (измельчения) при решении диофантовых уравнений.

3.Исследовать возможность применения диофантовых уравнений для решения некоторых практических задач.

II . Обзор литературы.

При написании работы мной использовалась следующая литература:

Мной использована информация о Диофанте и аль – Хорезми.

Книга посвящена методам Диофанта при решении неопределённых уравнений. В ней рассказывается о жизни и самого Диофанта. Эта информация использована мной в работе.

В книги рассказывается об истории алгебры с древних времён. Я использовал информацию о теории уравнений, начиная с древности.

В этой книге собрано около 200 статей, посвященных основным понятиям математики и её приложения. Мной были использованы материалы статей «Алгебра», «Уравнения», «Диофантовы уравнения»

Из книги взяты тексты задач для практического использования.

По теме мной использовался сайт:

http :// ru . wikipedia . org (информация об аль – Хорезми и Диофанте. О методах решения диофантовых уравнений).

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

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

(1)

Рассмотрим задачу.

Задача 1. В клетке находится x фазанов и у кроликов. Сколько в клетке фазанов и кроликов, если общее количество ног равно 62.

Общее число ног можно записать с помощью уравнения 2х+4у=62 (2)

Это равенство, которое я составил по условию задачи, называют уравнением с двумя переменными. Данное уравнение называют линейным уравнением. Линейные уравнения играют важную роль при решении различных задач. Напомню основные положения, связанные с этим понятием.

Линейным уравнением с двумя переменными называется уравнение вида ax +by =c , где x и у – переменные, а, b и с – некоторые числа.

Однозначно определить из уравнения (2) значения x и y нельзя. Даже если ограничиться только натуральными значениями переменных, здесь могут быть такие случаи: 1 и 15, 3 и 14, 5 и 13 и т. д.

Пара чисел (a , b ) называется решением уравнения с двумя переменными, если при замене x на а и y на b получаем истинное равенство.

Каждому уравнению с двумя переменными соответствует множество его решений, т. е. множество, состоящее из всех пар чисел (a , b ), при подстановке которых в уравнение получается истинное равенство. При этом, конечно, если заранее указаны множества Х и Y , которые могут принимать неизвестные x и у, то надо брать лишь такие пары (a , b ), для которых а принадлежит Х и b принадлежит Y .

Пару чисел (a , b ) можно изобразить на плоскости точкой М, имеющей координаты а и b , М= М (a , b ). Рассматривая изображения всех точек множества решений уравнения с двумя неизвестными, получим некоторое подмножество плоскости. Его называют графиком уравнения.

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

Два уравнения с двумя переменными, имеющие одни и те же решения называются равносильными.

Например, равносильны уравнения х+2у=5 и 3х+6у=15 – любая пара чисел, удовлетворяющая одному из этих уравнений, удовлетворяет и второму.

Уравнения с двумя переменными обладают такими же свойствами, как и уравнения с одной переменной:

1) если в уравнении перенести слагаемое из одной части в другую, изменив его знак, то получится уравнение, равносильное данному;

2) если обе части уравнения умножить или разделить на одно и то же отличное от нуля число, то получится уравнение, равносильное данному.

Существует несколько способов решения диофантовых уравнений:

Метод перебора вариантов

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

С использованием цепной дроби

Метод рассеивания (измельчения)

При помощи программирования на языке программирования Паскаль

В своей работе я исследовал методы – перебор вариантов и рассеивание (измельчения)

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

Задача 2 . Андрей работает летом в кафе. За каждый час ему платят 10 р. И высчитывают 2 р. за каждую разбитую тарелку. На прошедшей неделе он заработал 180 р. Определите, сколько часов он работал и сколько разбил тарелок, если известно, что он работает не более 3 ч в день.

Решение.

Пусть x часов он всего работал в неделю, тогда 10х р. ему заплатили, но он разбил у тарелок, и с него вычли 2у р. Имеем уравнение 10х – 2у =180 , причем x меньше или равен 21. Получим: 5х-у=90, 5х=90+у, х=18+у:5.

Так как x целое число, то у должно нацело делится на 5, чтобы в правой части получилось целое число. Возможны четыре случая

у=0, х=18, т. е. решением является пара – (18, 0);

у=5, х=19, (19, 5);

у=10, х=20, (20, 10);

у=15, х=21, (21, 15).

Эту задачу я решил, используя способ перебора вариантов. Ответ содержит четыре возможных варианта. Я попробовал решить этим способом ещё несколько задач.

Задача 3. Из двухрублевых и пятирублевых монет составлена сумма в 23 рубля. Сколько среди этих монет двухрублевых?

Решение.

Пусть x – количество двухрублевых монет, у – количество пятирублевых монет. Составим и решим уравнение: 2х+5у=23; 2х=23–5у; x = (23 – 5у):2; x =(22+1 – 5у):2, почленно поделим 22 на 2 и (1 – 5у) на 2, получим: x = 11 + (1 – 5у):2.

Так как x и y натуральные числа по условию задачи, то левая часть уравнения есть натуральное число, значит, и правая часть должна быть натуральным числом. К тому же, чтобы получить в правой части число натуральное, нужно чтобы выражение (1 – 5у) нацело делилось на 2. Осуществим перебор вариантов.

y =1, х=9, то есть двухрублевых монет может быть 9;

у=2, при этом выражение (1 – 5у) не делится нацело на 2;

у=3, х=4, то есть двухрублевых монет может быть 4;

при у больше или равном 4 значение x не является числом натуральным.

Таким образом, ответ в задаче следующий: среди монет 9 или 4 двухрублевых.

Задача 4. Шехерезада рассказывает свои сказки великому правителю. Всего она должна рассказать 1001 сказку. Сколько ночей потребуется Шехерезаде, чтобы рассказать все свои сказки, если x ночей она будет рассказывать по 3 сказки, а остальные сказки по 5 за у ночей

Решение.

Сказочнице потребуется x + у ночей, где x и у – натуральные корни уравнения 3х+5у=1001

x = (1001 – 5у):3; так как x – натуральное число, то и в правой части равенства также должно быть натуральное число, а значит выражение (1001 – 5у) должно нацело делиться на 3.

Осуществим перебор вариантов.

у=1, 1001 – 5у=1001-5= 996, 996 делится на 3, следовательно, х=332; решение (332;1);

у=2, 1001– 10=991, 991 не делится на 3;

у=3, 1001 – 15 = 986; 986 не делится на3;

у =4, 1001 – 20 = 981, 981 делится на 3, следовательно, x = 327, решение (327;4) и т. д.

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

Уравнение ax + by = c (1) в приведённых задачах я решал способом перебора вариантов. Я уяснил для себя, что способ перебора вариантов не всегда эффективен для решения данной задач, так как для нахождения всех решений уравнения требуются значительные временные затраты. И, на мой взгляд, в настоящее время он неактуален.

Поэтому я решил задачу про Шехерезаду, используя метод рассеивания (измельчения).

Метод рассеивания – это общий метод для решения в целых числах неопределённых уравнений первой степени с целыми коэффициентами.

Итак, решим задачу про Шехерезаду методом рассеивания:

Обратимся к уравнению 3х + 5у = 1001.

Перепишем его иначе: 3х= 1001- 5у; 3х= 1001 - 2у - 3у;

x = – y +
и обозначим x l = у + x

В результате уравнение примет вид 3х 1 = 1001 – 2у или

у = –x l
.

Если вновь произвести замену у 1 = у + х 1 , то придем к уравнению

x 1 + 2у 1 = 1001. Заметим, что коэффициенты при неизвестных уменьшились - измельчились.

Здесь коэффициент при x 1 , равен 1, а поэтому при любом целом у 1 = t число х 1 тоже целое. Остается выразить исходные переменные через t :

х 1 = 1001 – 2 t , следовательно, у = – 1001 + 3 t , а x = 2002 – 5 t . Итак, получаем бесконечную последовательность (2002 – 5 t , – 1001 + 3 t ) целочисленных решений. Внешний вид формул для нахождения значений переменных отличается от решений, полученных ранее, но с учетом условия задачи, корни получаются те же самые. Так, пара (332;1) получается при t =334.

На мой взгляд, этот метод не только более удобный (у него есть алгоритм действий), но и интересный. Известно, что этот метод в первые применил в начале VI в. индийский математик Ариабхатта.

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

Оно представлено ниже:

«Найти два целых числа, зная, что разность произведений первого на 19 и второго на 8 равно 13. »

В задаче требуется найти все целые решения уравнений.

Решение:

(1) 19x – 8y = 13

Выражаю y – неизвестное с наименьшим по абсолютной величине коэффициентом через x , получаю:

(2) y = (19x – 13)/8

Нужно теперь узнать, при каких целых значениях x соответствующие значения y являются тоже целыми числами. Перепишу уравнение (2) следующим образом:

(3) y = 2x + (3x – 13)/8

Из (3) следует, что y при целом x принимает целое значение только в том случае, если выражение (3x -13)/8 является целым числом, скажем y 1 . Полагая

(4) (3x - 13)/8 = y 1 ,

вопрос сводится к решению в целых числах уравнения (4) с двумя неизвестными x и y 1 ; его можно записать так:

(5) 3x – 8y 1 = 13.

Это уравнение имеет по сравнению с первоначальным (1) преимущество, что 3 – наименьшее из абсолютных величин коэффициентов при неизвестных – меньше, чем в (1), т.е. 8. Это было достигнуто благодаря тому, что коэффициент при x (19) был заменен остатком от деления на 8.

Продолжая тем же способом, мы получим из (5):

(6) x = (8y 1 +13)/3 = 2y 1 + (2y 1 + 13)/3.

Итак, неизвестное x при целом y 1 только тогда принимает целые значения, когда (2y 1 + 13)/3 есть целое число, скажем y 2 :

(7) (2y 1 + 1)/3 = y 2 ,

или

(8) 3y 2 – 2 y 1 = 13.

(9) y 1 = (3y 2 - 13)/2 = y 2 + (y 2 - 13)/2

Полагая

(10) (y 2 - 13)/2 = y 3 ,

получаю

(11) y 2 – 2 y 3 = 13.

Это самое простое из всех рассмотренных неопределенных уравнений, так как один из коэффициентов равен 1.

Из (11) получаю:

(12) y 2 = 2y 3 + 13.

Отсюда видно, что y 2 принимают целые значения при любых целых значениях y 3 . Из равенств (6), (9), (12), (3) путем последовательных подстановок можно найти следующие выражения для неизвестных x и y уравнения (1):

x = 2y 1 + y 2 = 2(y 2 + y 3 ) + y 2 = 3y 2 + 2y 3 = 3(2y 2 + 13) + 2y 3 = 8y 3 + 39;

у = 2x + y 1 = 2(8y 3 + 39) + y 2 + y 3 = 19y 3 +91.

Таким образом, формулы

x = 8y 3 + 39,

y = 19y 3 + 91.

При y 3 = 0, + 1,+ 2, + 3, … дают все целые решения уравнения (1).

В следующей таблице приведены примеры таких решений.

Таблица 1.

y3

x

y

Решим эту задачу рационально. В решении используется определённый алгоритм.

Задача 5.

Найти два числа, если разность произведений первого на 19 и второго на 8 равна 13.

Решение. Требуется решить уравнение 19х - 8у = 13

Перепишем его иначе: 8y =19x –13; 8y =16x +3x –13; у = 2х +

и обозначим y 1 = у - 2х.

В результате уравнение примет вид 8у 1 = Зx - 13 или x = 2y 1
.

Если вновь произвести замену х 1 = x - 2у 1 , то придем к уравнению

3x l - 2у 1 = 13.

Коэффициенты при неизвестных уменьшились - измельчились. Дальнейшее измельчение: y 1 = x l +
, то получим у 2 =у 1 –х 1 .

В результате последнее уравнение преобразуется к виду х 1 - 2у 2: = 13. Здесь коэффициент при х 1 , равен 1, а поэтому при любом целом у 2 = t число х 1 тоже целое.

Остается выразить исходные переменные через t :

вначале выразим х 1 =2t +13, y 1 = 3t +13; а затем x = 8 t +39, y = 19 t + 91.

Итак, получаем бесконечную последовательность (39 + 8 t , 91 + 19 t ) целочисленных решений . Уравнение ax + by = c (1) в приведённых задачах я решал способом рассеивания (измельчения).

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

Изучая диофантовы уравнения для их решения, я использовал методы перебора вариантов и рассеивания (измельчения). Этими методами я решал, как современные, так и древние задачи. В содержании моей работы были включены задачи, которые сводятся к решению уравнений первой степени с двумя переменными ах+b у=с (1)

В ходе своей работы я сделал выводы:

Метод перебора требует значительные временные затраты, а значит он не очень удобен и рационален.

Более рациональным, на мой взгляд, является метод рассеивания. Когда я решал старинную индийскую задачу этим методом, я понял, что существует определённый алгоритм решения. Мне было достаточно полученных в школе знаний. Я убедился, что методы решения дофантовых уравнений с развитием математики постоянно совершенствуются.

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

V . Список литературы

Г. И. Глейзер «История математики в школе» М.: изд. «Просвещение» 1964г. 376с.

И. Г. Башмакова «Диофант и диофантовы уравнения» М.: изд. «Наука» 1972г. 68с.

В. А. Никифоровский «В мире уравнений» М.: изд. «Наука» 1987г. 176с.

А. П. Савин «Энциклопедический словарь юного математика» М.: изд. «Педагогика» 1985г.

Г. М. Возняк, В. Ф. Гусев «Прикладные задачи на экстремумы» М.: изд. «Просвещение» 1985г. 144с.

http :// ru . wikipedia . org

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

На фермерском хозяйстве нужно провести водопровод длиной 167м. Имеются трубы длиной 5м и 7м. Сколько нужно использовать тех и других труб, чтобы сделать наименьшее количество соединений (трубы не резать)?

Учитывая, что количество как одних, так и других труб может изменяться, количество 7 – метровые трубы обозначаем через х, 5 – метровые – через у

Тогда 7х – длина 7 – метровых труб, 5у – длина 5 – метровых труб.

Отсюда получаем неопределённое уравнение:

7х+5у=167

Выпазив, например, переменную у через переменную х , получим:

Методом перебора легко найти соответствующие пары значений х и у , которые удовлетворяют уравнению 7х+5у=167

(1;32), (6;25), (11;18), (16;11), (21;4).

Из этих решений наиболее выгодное последнее, т. е. х=21; у=4.

Многие старинные способы отгадывания чисел и дат рождения основываются на решении диофантовых уравнений. Так, например, чтобы отгадать дату рождения (месяц и число) собеседника, достаточно узнать у него сумму, получаемую от сложения двух произведений: числа даты (х ) на 12 и номера месяца (у ) на 31.

2. Пусть сумма произведений, о которых идёт речь, равна 330. Найти дату рождения.

Решим неопределённое уравнение

12 х + 31 у = 330.

С помощью метода рассеивания получим:

х = 43 – 31 у 4 ,

у = 6 – 12 у 4 .

Ввиду ограничений, легко констатировать, что единственным решением является

у 4 = 1, х = 12, у = 6.

Итак, дата рождения: 12-е число 6-го месяца, т.е. 12 июня.

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

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

• Пример №1 (простой)
• Пример №2 (сложный)

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

• Задача про кур, кроликов и их лапы
• Задача про продавщицу и сдачу

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

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

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

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

Жил Диофант, по-видимому, в 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.

Пусть z=1. Тогда y=2, x=-5. 2 * (-5)+7 * 2=4

Пусть z=5. Тогда y=-6, x=23. 2 * (23)+7 * (-6)=4

” В этом примере важно понять, как мы перешли от уравнения с коэффициентами 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=1. Тогда y=5, x=24. 13 * (14)-36 * 5=2

Пусть 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 нам подходят.

Ответ

Шестью способами.

Подготовила Татьяна Яковлева

Сегодня предлагаю поразмышлять над некоторой интересной математической задачкой.
А именно, давайте-ка для разминки решим следующее линейной уравнение:

«Чего сложного?» - спросите вы. Действительно, лишь одно уравнение и целых четыре неизвестных. Следовательно, три переменных есть свободные, а последняя зависит от оных. Так давайте выразим скорее! Например, через переменную , тогда множество решений следующее:

где - множество любых действительных чисел.

Что же, решение действительно оказалось слишком тривиальным. Тогда будем нашу задачу усложнять и делать её более интересной.

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

где - множество целых чисел.

Теперь решение, полученное в начале статьи, «не проканает», так как мы рискуем получить как рациональное (дробное) число. Так как же решить это уравнение исключительно в целых числах?

Заинтересовавшихся решением данной задачи прошу под кат.

А мы с вами продолжаем. Попробуем произвести некоторые элементарные преобразования искомого уравнения:

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

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

Обращу внимание, что это говорит нам о том, что какие бы не были (в рамках диофантовых уравнений), всё равно останется целым числом, и это прекрасно.

Вспоминая, что справедливо говорить, что . А подставив заместо полученный выше результат получим:

Тут мы также видим, что что какие бы не были , всё равно останется целым числом, и это по-прежнему прекрасно.

Тогда в голову приходит гениальная идея: так давайте же объявим как свободные переменные, а будем выражать через них! На самом деле, мы уже это сделали. Осталось только записать ответ в систему решений:

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

Подставим в исходное уравнение:

Тождественно, круто! Давайте попробуем ещё разок на другом примере?

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

Как мы помним, наша задача сделать такие преобразования, чтобы в нашем уравнении оказалась неизвестная с единичным коэффициентом при ней (чтобы затем выразить её через остальные без любого деления). Для этого мы должны снова что-нибудь взять «за скобку», самое быстрое - это брать коэффициенты из уравнения которые самые близкие к единице. Однако нужно понимать, что за скобку можно взять только лишь то число, которое обязательно является каким-либо коэффициентом уравнения (ни больше, ни меньше), иначе наткнемся на тавтологию/противоречие или дроби (иными словами, нельзя чтобы свободные переменные появились где-то кроме как в последней замене). Итак:

Введем замену , тогда получим:

Вновь возьмем за скобку и наконец получим в уравнении неизвестную с единичным коэффициентом:

Введем замену , тогда:

Выразим отсюда нашу одинокую неизвестную :

Из этого следует, что какие бы мы не взяли, все равно останется целым числом. Тогда найдем из соотношения :

Аналогичным образом найдем из соотношения :

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

Таким образом, осталось ответить на вопрос - а любое ли подобное уравнение можно так решить? Ответ: нет, если уравнение в принципе нерешаемо. Такое возникает в тех случаях, если свободный член не делится нацело на НОД всех коэффициентов при неизвестных. Иными словами, имея уравнение:

Для его решения в целых числах достаточно выполнение следующего условия:

(где - наибольший общий делитель).

Доказательство

Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи. Увидеть его вы можете, например, в чудесной книге В. Серпинского «О решении уравнений в целых числах» в §2.

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

В заключение стоит сказать, что также можно добавить ограничения на каждый член уравнения в виде неравенства на оного (тогда к системе решений добавляется система неравенств, в соответствии с которой нужно будет скорректировать ответ), а также добавить ещё чего-нибудь интересное. Ещё не стоит забывать и про то, что алгоритм решения является строгим и поддается записи в виде программы для ЭВМ.

С вами был Петр,
спасибо за внимание.

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

Шаги

Часть 1

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

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

   • Если уравнение дано в другой форме, приведите его к стандартной форме с помощью основных алгебраических действий. Например, дано уравнение 23 x + 4 y − 7 x = − 3 y + 15 {\displaystyle 23x+4y-7x=-3y+15} . Приведите подобные члены и запишите уравнение так: 16 x + 7 y = 15 {\displaystyle 16x+7y=15} .

2. Упростите уравнение (если можно). Когда вы запишете уравнение в стандартной форме, посмотрите на коэффициенты A , B {\displaystyle A,B} и C {\displaystyle C} . Если у этих коэффициентов есть НОД, разделите на него все три коэффициента. Решение такого упрощенного уравнения также будет решением исходного уравнения.

   • Например, если все три коэффициента четные, разделите их как минимум на 2. Например:
     • 42 x + 36 y = 48 {\displaystyle 42x+36y=48} (все члены делятся на 2)
     • 21 x + 18 y = 24 {\displaystyle 21x+18y=24} (теперь все члены делятся на 3)
     • 7 x + 6 y = 8 {\displaystyle 7x+6y=8} (это уравнение больше нельзя упростить)

3. Проверьте, можно ли решить уравнение. В некоторых случаях можно сразу заявить, что уравнение не имеет решений. Если коэффициент «С» не делится на НОД коэффициентов «А» и «В», у уравнения нет решений.

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

4. Проанализируйте полученный результат. Когда вы найдете НОД коэффициентов A {\displaystyle A} и B {\displaystyle B} , сравните его с коэффициентом C {\displaystyle C} исходного уравнения. Если C {\displaystyle C} делится на НОД A {\displaystyle A} и B {\displaystyle B} , уравнение имеет целочисленное решение; в противном случае у уравнения нет решений.

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

   Часть 3

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

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

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

   2. Обратите внимание на последний шаг, где есть остаток. Перепишите уравнение этого шага так, чтобы изолировать остаток.

      • В нашем примере последний шаг с остатком - это шаг 6. Остаток равен 1. Перепишите уравнение шага 6 следующим образом:
        • 1 = 3 − (1 ∗ 2) {\displaystyle 1=3-(1*2)}

   3. Изолируйте остаток предыдущего шага. Этот процесс представляет собой пошаговое «перемещение вверх». Каждый раз вы будете изолировать остаток в уравнении предыдущего шага.

      • Изолируйте остаток уравнения шага 5:
        • 2 = 5 − (1 ∗ 3) {\displaystyle 2=5-(1*3)} или 2 = 5 − 3 {\displaystyle 2=5-3}

   4. Сделайте замену и упростите. Обратите внимание, что уравнение шага 6 содержит число 2, а в уравнении шага 5 число 2 изолировано. Поэтому вместо «2» в уравнении шага 6 подставьте выражение шага 5:

      • 1 = 3 − 2 {\displaystyle 1=3-2} (уравнение шага 6)
      • 1 = 3 − (5 − 3) {\displaystyle 1=3-(5-3)} (вместо 2 подставили выражение)
      • 1 = 3 − 5 + 3 {\displaystyle 1=3-5+3} (раскрыли скобки)
      • 1 = 2 (3) − 5 {\displaystyle 1=2(3)-5} (упростили)

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

      • Последним рассмотренным шагом был шаг 5. Поэтому перейдите к шагу 4 и изолируйте остаток в уравнении этого шага:
        • 3 = 18 − (3 ∗ 5) {\displaystyle 3=18-(3*5)}
      • Подставьте это выражение вместо «3» в последнее уравнение:
        • 1 = 2 (18 − 3 ∗ 5) − 5 {\displaystyle 1=2(18-3*5)-5}
        • 1 = 2 (18) − 6 (5) − 5 {\displaystyle 1=2(18)-6(5)-5}

   6. Продолжите процесс подстановки и упрощения. Этот процесс будет повторяться до тех пор, пока вы не достигнете первоначального шага алгоритма Евклида. Цель процесса - записать уравнение с коэффициентами 87 и 64 исходного уравнения, которое нужно решить. В нашем примере:

      • 1 = 2 (18) − 7 (5) {\displaystyle 1=2(18)-7(5)}
      • 1 = 2 (18) − 7 (23 − 18) {\displaystyle 1=2(18)-7(23-18)} (подставили выражение из шага 3)
        • 1 = 2 (18) − 7 (23) + 7 (18) {\displaystyle 1=2(18)-7(23)+7(18)}
        • 1 = 9 (18) − 7 (23) {\displaystyle 1=9(18)-7(23)}
      • 1 = 9 (64 − 2 ∗ 23) − 7 (23) {\displaystyle 1=9(64-2*23)-7(23)} (подставили выражение из шага 2)
        • 1 = 9 (64) − 18 (23) − 7 (23) {\displaystyle 1=9(64)-18(23)-7(23)}
        • 1 = 9 (64) − 25 (23) {\displaystyle 1=9(64)-25(23)}
      • 1 = 9 (64) − 25 (87 − 64) {\displaystyle 1=9(64)-25(87-64)} (подставили выражение из шага 1)
        • 1 = 9 (64) − 25 (87) + 25 (64) {\displaystyle 1=9(64)-25(87)+25(64)}
        • 1 = 34 (64) − 25 (87) {\displaystyle 1=34(64)-25(87)}

   7. Перепишите полученное уравнение в соответствии с исходными коэффициентами. Когда вы вернетесь к первому шагу алгоритма Евклида, вы увидите, что полученное уравнение содержит два коэффициента исходного уравнения. Перепишите уравнение так, чтобы порядок его членов соответствовал коэффициентам исходного уравнения.

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