С опушки леса в чащу ведет множество тропинок. Они извилисты, они сходятся, расходятся вновь и снова пересекаются одна с другой. На прогулке можно только заметить обилие этих тропинок, походить по некоторым из них и проследить их направление в глубь леса. Для серьезного изучения леса нужно идти по тропинкам, пока они вообще различимы среди сухой хвои и кустарников.
Поэтому мне захотелось написать проект, который можно рассматривать как описание одной из возможных прогулок по опушке современной математики.
Окружающий мир, потребности народного хозяйства, а зачастую, и повседневные хлопоты ставят перед человеком все новые и новые задачи, решение которых не всегда очевидно. Порою тот или иной вопрос имеет под собой множество вариантов ответа, из-за чего происходят затруднения в решении поставленных задач. Как выбрать правильный и оптимальный вариант?
С этим же вопросом напрямую связано решение неопределенных уравнений. Такие уравнения, содержащие две или более переменных, для которых требуется найти все целые или натуральные решения, рассматривались еще в глубокой древности. Например, греческий математик Пифагор (IV век до н. э.). александрийский математик Диофант (II-III век н. э.) и лучшие математики более близкой нам эпохи - П. Ферма (XVII век), Л. Эйлер (XVIII век), Ж. Л. Лагранж (XVIII век) и другие.
Участвуя в Российском заочном конкурсе > г. Обнинска, Международном конкурсе - игре > и олимпиаде Уральского Федерального округа часто сталкиваюсь с такими задачами. Это связано с тем, что их решение носит творческий характер. Проблемы, возникающие при решении уравнений в целых числах, вызваны как сложностью, так и тем, что в школе им уделяется мало времени.
Диофант представляет одну из наиболее трудных загадок в истории науки. Нам не известно ни время, когда он жил, ни предшественники, которые работали бы в той же области. Труды его подобны сверкающему огню среди непроницаемой тьмы.
Промежуток времени, когда мог жить Диофант, составляют полтысячелетия! Нижняя грань определяется без труда: в своей книге о многоугольных числах Диофант неоднократно упоминает математика Гипсикла Александрийского который жил в середине 2-ого в. до н. э.
С другой стороны, в комментариях Теона Александрийского к > знаменитого астронома Птолемея помещен отрывок из сочинения Диофанта. Теон жил в середине 4-ого в. н. э. Этим определяется верхняя грань этого промежутка. Итак, 500 лет!
Французский историк науки Поль Таннри, издатель наиболее полного текста Диофанта, попытался сузить этот промежуток. В библиотеке Эскуриала он нашел отрывки из письма Михаила Пселла, византийского ученого Х1 в. , где говорится, что ученейший Анатолий после того как собрал наиболее существенные части этой науки речь идет о введении степеней неизвестного и об их (обозначении), посвятил их своему другу Диофанту. Анатолий Александрийский действительно составил >, отрывки которой приводят в дошедшей до нас сочинений Ямблих и Евсений. Но Анатолий жил в Александрии в середине 111-го в до н. э и даже более точно - до 270 года, когда он стал епископом Лаодакийским. Значит, его дружба с Диофантом, которого все называют Александрийским, должна была иметь место до этого. Итак, если знаменитый Александрийский математик и друг Анатолия по имени Диофант составляют одно лицо, то время жизни Диофанта - середина 111-го века нашей эры.
Зато место жительства Диофанта хорошо известно - Александрия, центр научной мысли и эллинистического мира.
До наших времен дошла одна из эпиграмм Палатинской Антологии:
Прах Диофанта гробница покоит: дивись ей - и камень
Мудрым искусством его скажет усопшего век.
Волей богов шестую часть жизни он прожил ребенком
И половину шестой встретил с пушком на щеках.
Только минула седьмая, с подругою он обручился.
С нею пять лет проведя, сына дождался мудрец.
Только полжизни отцовской возлюбленный сын его прожил.
Отнят он был у отца ранней могилой своей.
Дважды два года родитель оплакивал тяжкое горе.
Тут и увидел предел жизни печальной своей.
Используя современные методы решения уравнений можно сосчитать, сколько лет прожил Диофант.
Пусть Диофант прожил x лет. Составим и решим уравнение:
Умножим уравнение на 84, чтобы избавиться от дробей:
Таким образом, Диофант прожил 84 года.
Наиболее загадочным представляется творчество Диофанта. До нас дошло шесть из тринадцати книг, которые были объединены в >, стиль и содержание этих книг резко отличаются от классических античных сочинений по теории чисел и алгебры, образцы которых мы знаем по > Евклида, его >, леммам из сочинений Архимеда и Аполлония. >, несомненно, явилась результатом многочисленных исследований, которые остались совершенно неизвестными.
Мы можем только гадать о её корнях, и изумляться богатству и красоте её методов и результатов.
> Диофанта это сборник задач (всего 189), каждая из которых снабжена решением. Задачи в ней тщательно подобраны и служат для иллюстрации вполне определенных, строго продуманных методах. Как это было принято в древности, методы не формулируются в общем виде, а повторяются для решения однотипных задач.
Достоверно известно своеобразное жизнеописание Диофанта, которое по преданию было высечено на его надгробии и представляло задачу-головоломку:
Эта головоломка служит примером тех задач, которые решал Диофант. Он специализировался на решении задач в целых числах. Такие задачи в настоящее время известны под названием диофантовых.
Исследования диофантовых уравнений обычно связано с большими трудностями.
В 1900 году на всемирном конгрессе математиков в Париже один из крупнейших математиков мира Давид Гильберт выделил 23 проблемы из различных областей математики. Одной из этих проблем была проблема решения диофантовых уравнений. В проблеме заключалось следующее: можно ли разрешить уравнение с произвольным числом неизвестных и целыми коэффициентами, определённым способом - с помощью алгоритма. Задача состоит в следующем: для заданного уравнения надо найти все целые или натуральные значения переменных, входящих в уравнение, при которых оно превращается в истинное равенство. Диофант придумал для таких уравнений много разнообразных приёмов решения. Ввиду бесконечного разнообразия диофантовых уравнений общего алгоритма для их решения не существует, и практически для каждого уравнения приходится изобретать индивидуальный приём.
Диофантовым уравнением 1-ой степени или линейным диофантовым уравнением с двумя неизвестными называется уравнение вида: ax+by=c, где a,b,c-целые, НОД(a,b)=1.
Приведу формулировки теорем, на основании которых может быть составлен алгоритм решения неопределенных уравнений первой степени от двух переменных в целых числах.
Теорема 1. Если в уравнении, то уравнение имеет, по крайней мере, одно решение.
Доказательство:
Можно считать, что а >0. Решив уравнение относительно х, получим: х=с-вуа. Докажу, что если в эту формулу вместо у подставлять все натуральные числа, меньшие а и 0, т. е. числа 0;1;2;3;. ;а-1, и каждый раз совершать деление, то все а остатков будут различны. Действительно, подставлю вместо у числа m1 и m2, меньшие а. В результате получу две дроби: с-вm1а и с-вm2а. Выполнив деление и обозначив неполные частные через q1и q2, а остатки через r1 и r2, найду с-вm1а=q1+ r1а, с-вm2а= q2+ r2а.
Предположу, что остатки r1 и r2 равны. Тогда вычитая из первого равенства второе получу: с-вm1а- с-вm2а= q1-q2, или в(m1 - m2)а=q1-q2.
Т. к. q1-q2 - целое число, то и левая часть должна быть целой. Стало быть, вm1 - m2 должно делиться на а, т. е. разность двух натуральных чисел, каждое из которых меньше а, должна делиться на а, что невозможно. Значит, остатки r1 и r2 равны. Т. е. все остатки различны.
Т. о. я получила а различных остатков, меньших а. Но различные а натуральных чисел, не превосходящие а - это числа, 0;1;2;3;. ;а-1. Следовательно, среди остатков непременно найдется один и только один, равный нулю. Значение у, подстановка которого в выражение (с-ву)а дает остаток 0, и превращает х=(с-ву)а в целое число. Что и требовалось доказать.
Теорема 2. Если в уравнении, и с не делится на, то уравнение целых решений не имеет.
Доказательство:
Пусть d=НОД(а;в), так, что а=md, b=nd, где m и n- целые числа. Тогда уравнение примет вид: mdх+ ndу=с, или d(mх+ nу)=с.
Допустив, что существуют целые числа х и у, удовлетворяющие уравнению, получаю, что коэффициент с делится на d. Полученное противоречие доказывает теорему.
Теорема 3. Если в уравнении, и, то оно равносильно уравнению, в котором.
Теорема 4. Если в уравнении, то все целые решения этого уравнения заключены в формулах:
где х0, у0 - целое решение уравнения, - любое целое число.
Сформулированные теоремы позволяют составить следующий алгоритм решения в целых числах уравнения вида.
1. Найти наибольший общий делитель чисел a и b, если и с не делится на, то уравнение целых решений не имеет; если и, то
2. Разделить почленно уравнение на, получив при этом уравнение, в котором.
3. Найти целое решение (х0, у0) уравнения путем представления 1 как линейной комбинации чисел и;
4. Составить общую формулу целых решений данного уравнения где х0, у0 - целое решение уравнения, - любое целое число.
2. 1 МЕТОД СПУСКА
Многие > основаны на методах решения неопределенных уравнений. Например, фокус с угадыванием даты рождения.
Предложите Вашему знакомому угадать его день рождения по сумме чисел равных произведению даты его рождения на 12 и номера месяца рождения на 31.
Для того чтобы угадать день рождения Вашего знакомого нужно решить уравнение: 12х + 31y = А.
Пусть Вам назвали число 380, т. е. имеем уравнение 12х + 31y = 380. Для того чтобы найти х и y можно рассуждать так: число 12х + 24y делится на 12, следовательно, по свойствам делимости (теорема 4. 4), числа 7y и 380 должны иметь одинаковые остатки при делении на 12. Число 380 при делении на 12 дает остаток 8, следовательно 7y при делении на 12 тоже должно давать в остатке 8, а так как y - это номер месяца, то 1
Уравнение, которое мы решили, является диофантовым уравнением 1-ой степени с двумя неизвестными. Для решения таких уравнений может быть использован, так называемый метод спуска. Алгоритм этого метода рассмотрю на конкретном уравнении 5x + 8y = 39.
1. Выберу неизвестное, имеющее наименьший коэффициент (в нашем случае это х), и выражу его через другое неизвестное:. Выделю целую часть:. Очевидно, что х будет целым, если выражение окажется целым, что, в свою очередь, будет иметь место тогда, когда число 4 - 3y без остатка делится на 5.
2. Введу дополнительную целочисленную переменную z следующим образом: 4 - 3y = 5z. В результате получу уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами. Решать его буду уже относительно переменной y:. Выделяя целую часть, получу:
Рассуждая аналогично предыдущему, ввожу новую переменную u: 3u = 1 - 2z.
3. Выражу неизвестную с наименьшим коэффициентом, в этом случае переменную z: =. Требуя, чтобы было целым, получу: 1 - u = 2v, откуда u = 1 - 2v. Дробей больше нет, спуск закончен.
4. Теперь необходимо >. Выражу через переменную v сначала z, потом y и затем x: z = = = 3v - 1; = 3 - 5v.
5. Формулы x = 3+8v и y = 3 - 5v, где v - произвольное целое число, представляют общее решение исходного уравнения в целых числах.
Замечание. Таким образом, метод спуска предполагает сначала последовательное выражение одной переменой чрез другую, пока в представлении переменной не останется дробей, а затем, последовательное > по цепочке равенств для получения общего решения уравнения.
2. 2 МЕТОД ПЕРЕБОРА
В клетке сидят кролики и фазаны, всего у них 18 ног. Узнать, сколько в клетке тех и других?
Составлю уравнение с двумя неизвестными, в котором х - число кроликов, а у - число фазанов:
4х + 2у = 18, или 2х + у = 9.
Ответ. 1)1 кролик и 7 фазанов; 2) 2 кролика и 5 фазанов; 3) 3 кролика и 3 фазана; 4) 4 кролика и 1 фазан.
1. ПРАКТИЧЕСКАЯ ЧАСТЬ
3. 1 Решение линейных уравнений с двумя неизвестными
1. Решить уравнение 407х - 2816y = 33 в целых числах.
Воспользуюсь составленным алгоритмом.
1. Используя алгоритм Евклида, найду наибольший общий делитель чисел 407 и 2816:
2816 = 407·6 + 374;
407 = 374·1 + 33;
374 = 33·11 + 11;
Следовательно (407,2816) = 11, причем 33 делится на 11.
2. Разделю обе части первоначального уравнения на 11, получим уравнение 37х - 256y = 3, причем (37, 256) = 1
3. С помощью алгоритма Евклида найду линейное представление числа 1 через числа 37 и 256.
256 = 37·6 + 34;
Выражу 1 из последнего равенства, затем последовательно поднимаясь по равенствам буду выражать 3; 34 и полученные выражения подставлю в выражение для 1.
1 = 34 - 3·11 = 34 - (37 - 34·1) ·11 = 34·12 - 37·11 = (256 - 37·6) ·12 - 37·11 =
83·37 - 256·(- 12)
Таким образом, 37·(- 83) - 256·(- 12) = 1, следовательно пара чисел х0 = - 83 и у0 = - 12 есть решение уравнения 37х - 256y = 3.
4. Запишу общую формулу решений первоначального уравнения где t - любое целое число.
Ответ. (-83c+bt; -12с-at), t є Z.
Замечание. Можно доказать, что если пара (х1,y1) - целое решение уравнения, где, то все целые решения этого уравнения находятся по формулам: х=х1+bty=y1-at
2. Решить уравнение 14x - 33y=32 в целых числах.
Решение: x = (32 + 33y) : 14
(14 [. ] 2+ 5)y + (14 [. ] 2 + 4) = 14 [. ] 2y + 5y + 14[. ] 2 + 4 = 14(2y + 2) + 5y + 4; 2y + 2 = p; p є Z
Перебор от 1 до 13
При y = 2; (5 [. ] 2 + 4): 14
Подставлю в исходное уравнение y = 2
14x = 32 +33 [. ] 2
14x = 32 + 66 x = 98: 14 = 7
Найду все целые решения по найденному частному:
14(x - 7) + 98 - 33 (y -2) - 66 = 32
14(x - 7) - 33(y - 2)=0
14(x - 7) = 33(y - 2) -> 14(x - 7) : 33 -> (x - 7): 33 -> x = 33k + 7; k є Z
Подставлю в исходное уравнение:
14(33k + 7) - 33y = 32
14. 33k + 98 - 33y = 32 y = 14k + 2; x = 33k + 7, где k є Z. Эти формулы задают общее решение исходного уравнения.
Ответ. (33k + 7; 14k + 2), k є Z.
3. Решить уравнение x - 3y = 15 в целых числах.
Найду НОД(1,3)=1
Определю частное решение: x=(15+3y):1 используя метод перебора, нахожу значение y=0 тогда x=(15+3 [. ] 0) =15
(15; 0) - частное решение.
Все остальные решения находятся по формулам: x=3k + 15, k є Z y=1k+0=k, k є Z при k=0, получаю частное решение (15;0)
Ответ: (3k+15; k), k є Z.
4. Решить уравнение 7x - y = 3в целых числах.
Найду НОД(7; -1)=1
Определю частное решение: x = (3+y):7
Используя метод перебора, находим значение y є y = 4, x = 1
Значит, (1;4) - частное решение.
Все остальные решения нахожу по формулам: x = 1k + 1, k є Z y = 7k + 4, k є Z
Ответ: (k+1;7k+4); k є Z.
5. Решить уравнение 15x+11 y = 14 целых числах.
Найду НОД(15; -14)=1
Определю частное решение: x = (14 - 11y):15
Используя метод перебора, нахожу значение y є y = 4, x = -2
(-2;4) - частное решение.
Все остальные решения нахожу по формулам: x = -11k - 2, k є Z y =15k + 4, k є Z
Ответ: (-11k-2; 15k+4); k є Z.
6. Решить уравнение 3x - 2y = 12 целых числах.
Найду НОД(3; 2)=1
Определю частное решение: x = (12+2y):3
Используя метод перебора, нахожу значение y є y = 0, x = 4
(4;0) - частное решение.
Все остальные решения нахожу по формулам: x = 2k + 4, k є Z y = 3k, k є Z
Ответ: (2k+4; 3k); k є Z.
7. Решите в целых числах уравнение xy = x + y.
Имею ху - х - у + 1 = 1 или (х - 1)(у - 1) = 1
Поэтому х - 1 = 1, у - 1 = 1, откуда х = 2, у = 2 или х - 1 = - 1, у - 1 = - 1, откуда х = 0, у = 0 других решений в целых числах данное уравнение не имеет.
Ответ. 0;0;(2;2).
8. Решите в целых числах уравнение 60х - 77у = 1.
Разрешу это уравнение относительно х: х = (77у + 1) / 60 = (60у + (17у +1)) / 60 = у + (17у + 1) / 60.
Пусть (17у + 1) / 60 = z, тогда у = (60z - 1) / 17 = 3z + (9z - 1) / 17. Если обозначить (9z - 1) / 17 через t, то z = (17t + 1) / 9 = 2t + (- t + 1) / 9. Наконец, пусть (- t + 1) / 9 = n, тогда t = 1- 9n. Так как я нахожу только целые решения уравнения, то z, t, n должны быть целыми числами.
Таким образом, z = 2 - 18n + 2 = 2 - 17n, а поэтому у = 6 - 51n + 1 - 9n = 7 - 60n, х = 2 - 17n +7 - 60n = 9 - 77n. Итак, если х и у - целые решения данного уравнения, то найдется такое целое число n, что х = 9 - 77n, y = 7 - 60n. Обратно если у = 9 - 77n, х = 7 - 60n, то, очевидно, х, у - целые. Проверка показывает, что они удовлетворяют исходному уравнению.
Ответ. (9 - 77n; 7 - 60n)); n є Z.
9. Решить уравнение 2x+11y =24 в целых числах.
Найду НОД(2; 11)=1
Определю частное решение: x = (24-11y):2
Используя метод перебора, нахожу значение y є y = 0, x = 12
(12;0) - частное решение.
Все остальные решения нахожу по формулам: x = -11k + 12, k є Z y = 2k + 0=2k, k є Z
Ответ:(-11k+12; 2k); k є Z.
10. Решить уравнение 19x - 7y = 100 в целых числах.
Найду НОД(19; -7)=1
Определю частное решение: x = (100+7y):19
Используя метод перебора, нахожу значение y є y = 2, x = 6
(6;2) - частное решение.
Все остальные решения нахожу по формулам: x = 7k + 6, k є Z y = 19k + 2, k є Z
Ответ:(7k+6; 19k+2); kє Z.
11. Решить уравнение 24x - 6y = 144 в целых числах
Найду НОД(24; 6)=3.
Уравнение не имеет решений, потому что НОД(24; 6)!=1.
Ответ. Решений нет.
12. Решить уравнение в целых числах.
Преобразую отношение коэффициентов при неизвестных.
Прежде всего, выделю целую часть неправильной дроби;
Правильную дробь заменю равной ей дробью.
Тогда получу.
Проделаю такие же преобразования с полученной в знаменателе неправильной дробью.
Теперь исходная дробь примет вид:
Повторяя те же рассуждения для дроби,получаю.
Выделяя целую часть неправильной дроби, приду к окончательному результату:
Я получила выражение, которое называется конечной цепной или непрерывной дробью. Отбросив последнее звено этой цепной дроби - одну пятую, превращу получающуюся при этом новую цепную дробь в простую и вычту ее из исходной дроби.
Приведу полученное выражение к общему знаменателю и отброшу его, тогда
Из сопоставления полученного равенства с уравнением следует, что, будет решением этого уравнения и согласно теореме все его решения будут содержаться в,.
Ответ. (9+52t; 22+127t), t є Z.
Полученный результат наводит на мысль о том, что и в общем случае для нахождения решения уравнения надо разложить отношение коэффициентов при неизвестных в цепyую дробь, отбросить ее последнее звено и проделать выкладки, подобные тем, которые были проведены выше.
13. Решить уравнение 3ху + 2х + 3у = 0 в целых числах.
3ху + 2х + 3у =3ху + 2х + 3у + 2 - 2 = 3у(х + 1) + 2(х + 1) - 2 =
=(х + 1)(3у + 2) - 2,
(х + 1)(3у + 2) = 2,
3у + 2 = 1 или 3у + 1 = 2 или 3у + 1 = -1 или 3у + 1 = -2 х + 1 = 2, х + 1 =1, х + 1 = -2, х + 1 = -1; х = 2 или х = 0 или х = -3 или х = -2 у cent z, у = 0, у = -1, у cent z.
Ответ: (0;0);(-3;-1).
14. Решить уравнение у - х - ху = 2 в целых числах.
Решение: у - ху - х + 1 = 3, (у + 1)(1 - х) = 3,
3 = 1·3 = 3·1 = (-1)·(-3) = (-3)·(-1).
у + 1 = 1 или у + 1 = 3 или у + 1 = -1 или у + 1 = -3
1 - х =3, 1 - х =1, 1 - х = -3, 1 - х = -1.
у = 0 или у = 2 или у = -2 или у = -4 х =-2, х = 0, х = 4, х = 2
Ответ: (-2;0);(0;2);(2;-4);(4;-2).
15. Решить уравнение у + 4х + 2ху = 0 в целых числах.
Решение: у + 4х + 2ху + 2 - 2 = 0, (2х + 1)(2 + у) = 2,
2 = 1∙2 = 2∙1 = (-2)∙(-1) = (-1)∙(-2).
2х + 1= 1 или 2х + 1= 2 или 2х + 1= -1 или 2х + 1= -2
2 + у = 2, 2 + у = 1, 2 + у = -2, 2 + у = -1; у = 0 или у = -1 или у = -4 или у = -3 х = 0, х cent Z, х = -1, х cent Z.
Ответ: (-1;-4);(0;0).
16. Решить в целых числах уравнение 5х + 10у = 21.
5(х + 2у) = 21, т. к. 21 != 5n, то корней нет.
Ответ. Корней нет.
17. Решить уравнение 3х + 9у = 51в натуральных числах.
3(х + 3у) = 3∙17, х = 17 - 3у, у = 1, х = 14; у = 2, х = 11; у = 3, х = 8; у = 4, х = 5; у = 5, х = 2; у = 6, х = -1, -1cent N.
Ответ:(2;5);(5;4);(8;3);(11;2; (14;1).
18. Решить уравнение 7х+5у=232 в целых числах.
Решу это уравнение относительно того из неизвестных, при котором находится наименьший (по модулю) коэффициент, т. е. в данном случае относительно у: у=232-7х5.
Подставлю в это выражение вместо х числа: 0;1;2;3;4. Получаю: х=0, у=2325=4625, х=1, у=232-75=45, х=2, у=232-145=43,6, х=3, у=232-215=42,2, х=4, у=232-285=40,8
Ответ. (1;45).
19. Решить в целых числах уравнение 3x + 4y + 5xy = 6.
Имею 3∙4 + 5∙6 = 42 = mn
Делители 42: - +- (1, 2, 3, 6, 7, 14, 21, 42).
x = m - 45, y = n - 35 нахожу, что при m = -1, -6, 14, -21 n = -42, -7, 3, -2 решениями будут: x = -1, -2, 2, -5 y = -9, -2, 0, -1.
Итак, данное уравнение имеет 4 решения в целых числах и ни одного в натуральных.
Ответ. -1;-9;-2;-2;2;0;(-5;-1).
20. Решить уравнение 8х+65у=81в натуральных числах.
81⋮НОД(8;65)=>
8х=81-65у х=81-65у8=16+65-65у8=2+65(1-у)8.
Пусть 1-у8=t, t Є Z. х=2+65t>0у=1-8t>0
65t>-2-8t>-1 t>-265 t t=0.
При t=0 х=2у=1
Ответ. (2;1).
21. Найти целые неотрицательные решения уравнения 3х+7у=250.
250⋮НОД(3;7) =>уравнение можно решить в целых числах.
х=250-7у3=243+7-7у3=81+7(1-у)3.
Пусть 1-у3=t, t Є Z.
х=81+7t>=0у=1-3t>=0
7t>=-81-3t>=-1 t>=-817t=-1147t t=-11;-10;. ;0.
х=81+7tу=1-3t t=-11 х=4у=34 t=-10 х=11у=31 t=-9 х=18у=28 t=-8 х=25у=25 t=-7 х=32у=22 t=-6 х=39у=19 t=-5 х=46у=16 t=-4 х=53у=13 t=-3 х=60у=10 t=-2 х=67у=7 t=-1 х=74у=4 t=0 х=81у=1
Ответ. 11;31;18;28;25;25;32;22;39;19;46;16;53;13;60;10;67;7;74;4;81;1.
22. Решить уравнение ху+х+у3=1988 в целых числах.
Умножим обе части уравнения на 3. Получим:
3х+3ху+у=5964
3х+3ху+у+1=5965
(3х+1)+(3ух+у)=5965
(3х+1) + у(3х+1)=5965
(3х+1)(у+1)=5965
5965=1∙5965 или 5965=5965∙1 или 5965=-1∙(-5965) или 5965=-5965∙(-1) или 5965=5∙1193 или 5965=1193∙1 или 5965=-5∙(-1193) или 5965=-1193∙(-5)
1)3х+1=1у+1=5965 2) 3х+1=5965у+1=1 х=0у=5964 х=1988у=0
3) 3х+1=5у+1=1193 4) 3х+1=1193у+1=5 решений в целых числах нет решений в целых числах нет
5) 3х+1=-1у+1=-5965 6) 3х+1=-5965у+1=-1 решений в целых числах нет решений в целых числах нет
7) 3х+1=-5у+1=-1193 8) 3х+1=-1193у+1=-5 х=-2у=1194 х=-398у=-6
Ответ. 0;5964;1988;0;-2;-1194;(-398;-6).
3. 2 РЕШЕНИЕ ЗАДАЧ
Существует несколько типов задач, чаще всего это задачи олимпиадного характера, которые сводятся к решению диофантовых уравнений. Например: а) Задачи по размену суммы денег определённого достоинства.
б) Задачи на переливание, на деление предметов.
1. Купили 390 цветных карандашей в коробках по 7 и по 12 карандашей. Сколько тех и других коробок купили?
Обозначу: x коробок по 7 карандашей, y коробок по 12 карандашей.
Составлю уравнение:7x + 12y = 390
Найду НОД(7; 12)=1
Определю частное решение: x = (390 - 12y):7
Используя метод перебора, нахожу значение y є y = 1, x = 54
(54;1) - частное решение.
Все остальные решения нахожу по формулам: x = -12k + 54, k є Z y = 7k + 1, k є Z
Я нашла множество решений уравнения. Учитывая условия задачи, определю возможное количество тех и других коробок.
Ответ. Можно купить: 54 коробки по7 карандашей и 1 коробку по 12 карандашей или 42 коробки по 7карандашей и 8 коробок по 12 карандашей, или 30 коробок по 7 карандашей и 15 коробок по 12 карандашей, или 28 коробок по 7 карандашей и 22 коробки по 12 карандашей, или 6 коробок по 7 карандашей и 29 коробок по 12 карандашей.
2. Один катет прямоугольного треугольника на 7 см больше другого, а периметр треугольника равен 30 см. Найдите все стороны треугольника.
Обозначу: x см - один катет, (x+7) см - другой катет, y см - гипотенуза
Составлю и решу диофантово уравнение: x+(x+7)+y=30
Найду НОД(2; 1)=1
Определю частное решение: x = (23 - y):2
Используя метод перебора, нахожу значение y =1 y = 1, x = 11
(11;1) - частное решение.
Все остальные решения уравнения нахожу по формулам: x = -k + 11, k є Z y = 2k + 1, k є Z k
Учитывая, что любая сторона треугольника меньше суммы двух других сторон, приходим к выводу, что существует три треугольника со сторонами 7, 9 и 14; 6, 11 и 13; 5, 13 и 12. По условию задачи дан прямоугольный треугольник. Это треугольник со сторонами 5, 13 и 12 (выполняется теорема Пифагора).
Ответ: Один катет равен 5см, другой - 12 см, гипотенуза - 13 см.
3. Несколько детей собирали яблоки. Каждый мальчик собрал по 21 кг, а девочка по 15 кг. Всего они собрали 174 кг. Сколько мальчиков и сколько девочек собирали яблоки?
Пусть мальчиков x, а девочек y, при этом x и y - натуральные числа. Составлю уравнение:
Решаю методом подбора: x
6 Только при x = 4 второе неизвестное получает целое положительное значение (y = 6). При любом другом значении x число y будет либо дробным, либо отрицательным. Следовательно, задача имеет одно единственное решение.
Ответ. 4 мальчика и 6 девочек.
4. Можно ли сформировать набор из карандашей стоимостью 3 рубля и ручек стоимостью 6 рублей на сумму 20 рублей?
Пусть количество карандашей в наборе x, а ручек - y.
Составлю уравнение:
При любых целых числах x и y левая часть уравнения должна делиться на 3; правая часть при этом не делится на 3. Это означает, что не существует таких целых x и y, которые удовлетворяли бы нашему уравнению. Это уравнение неразрешимо в целых числах. Сформировать такой набор невозможно.
Ответ. Решений нет.
5. Найти натуральное число, которое при делении на 3 дает остаток 2, а при делении на 5 - остаток 3.
Обозначу искомое число через x. Если частное от деления x на 3 обозначу через y, а частное от деления на 5 - через z, то получу: х=3у+2х=5z+3
По смыслу задачи x, y и z должны быть натуральными числами. Значит, нужно решить в целых числах неопределенную систему уравнений.
При любых целых y и z , будет целым и x. Вычту из второго уравнения первое и получу:
5z - 3y + 1 = 0.
Найдя все целые положительные y и z, сразу получу и все целые положительные значения x.
Из этого уравнения нахожу:
Одно решение очевидно: при z = 1 получим y = 2, и x и y целые. Им соответствует решение x = 8.
Найду остальные решения. Для этого введу вспомогательное неизвестное u, полагая z = 1 + u. Получу:
5(1 + u) - 3y + 1 = 0, т. е. 5u = 3y - 6 или 5u = 3(y - 2).
Правая часть последнего уравнения при любом целом y делится на 3. Значит, и левая часть должна делиться на 3. Но число 5 - взаимно-простое с числом 3; поэтому u должно разделиться на 3, т. е. иметь вид 3n, где n - целое число. В этом случае y будет равняться
15n/3 + 2 = 5n + 2, т. е. тоже целому числу. Итак, z = 1 + u = 1 + 3n, откуда x = 5z + 3 = 8 + 15n.
Получилось не одно, а бесконечное множество значений для x: x = 8 + 15n, где n - целое число (положительное или ноль):
Ответ. х=8+15n; n є 0;1;2;.
6. Подданные привезли в дар шаху 300 драгоценных камней: в маленьких шкатулках по 15 штук в каждой и в больших - по 40 штук. Сколько было тех и других шкатулок, если известно, что маленьких было меньше, чем больших?
Обозначу за х количество маленьких шкатулок, а за у - количество больших.
15х+40у=300. Сокращу на 5.
3х+8у=60 х=60-8у3 х=60-6у-2у3
Х=20-2у-2у3
Чтобы значение дроби было целым числом, надо чтобы 2у было кратным 3, т. е. 2у=3с.
Выражу переменную у и выделю целую часть:
Z должно быть кратно 2, т. е. z=2u.
Выражу переменные х и у через u:
Х=20-2у-2у3
Х=20-2∙3u-2∙3u3
Составлю и решу систему неравенств:
Выпишу целые решения: 1; 2. Теперь найду значения х и у при u=1; 2.
1) х1=20-8∙1=20-8=12 у1=3∙1=3
2) х2=20-8∙2=20-16=4 у2=3∙2=6
Ответ. 4 маленькие шкатулки; 6 больших шкатулок.
7. Даны два автомобиля Урал 5557, автомобили отправили в рейс Краснотурьинск - Пермь - Краснотурьинск. Всего понадобилось 4 т дизельного топлива и 2 водителя, чтобы выполнить этот рейс. Нужно определить транспортные затраты, а именно стоимость 1 т дизельного топлива и оплату труда водителей, выполняющих этот рейс, если известно, что всего затрачено 76000 р.
Пусть х рублей - стоимость 1 т дизельного топлива, а у рублей - оплата труда водителей. Тогда (4х + 2у) рублей - затрачено на выполнение рейса. А по условию задачи затрачено 76000 р.
Получу уравнение:
Для решения этого уравнения метод перебора окажется трудоемким процессом. Так что воспользуюсь методом >.
Выражу переменную у через х: , выделю целую часть, получу: (1).
Чтобы значение дроби было целым числом, нужно чтобы, 2х было кратно 4. Т. е. 2х = 4z, где z - целое число. Отсюда:
Значение х подставлю в выражение (1):
Т. к. х, у 0, то 19000 z 0, следовательно, придавая z целые значения от 0 до 19000, получу следующие значения x и y: z
Из настоящих данных о транспортных затратах известно, что 1 т дизельного топлива (х) стоит 18000 р. , а оплата труда водителей, выполняющих рейс (у) составляет 10000 р. (данные взяты приближенно). По таблице найдем, что значению х, равному 18000 и значению у, равному 10000 соответствует значение z, равное 9000, действительно: ;.
8. Сколькими способами можно набрать сумму 27р. , имея достаточно много двухрублёвых и пятирублёвых монет?
Обозначу: x двухрублёвых монет и y пятирублёвых монет
Составлю уравнение, учитывая условие задачи 2x +5y = 27.
Найду НОД(2;5)=1
Определю частное решение: x = (27-5y):2
Используя метод перебора, нахожу значение y є y = 1, x = 11
(11;1) - частное решение.
Все остальные решения находятся по формулам: x = -5k + 11, k є Z y = 2k + 1, k є Z
Данное уравнение имеет множество решений. Найдём все способы, с помощью которых можно набрать сумму 27 рублей предложенными монетами. k
Ответ. Существует три способа, которыми можно набрать данную сумму, имея достаточно много двухрублёвых и пятирублёвых монет.
9. Допустим, в аквариуме живут осьминоги и морские звёзды. У осьминогов по 8 ног, а у морских звёзд - по 5. Всего конечностей насчитывается 39. Сколько в аквариуме животных?
Пусть х - количество морских звёзд, у - количество осьминогов. Тогда у всех осьминогов по 8у ног, а у всех звёзд 5х ног.
Составлю уравнение: 5х + 8у = 39.
Замечу, что количество животных не может выражаться нецелым или отрицательным числами. Следовательно, если х - целое неотрицательное число, то и у=(39 - 5х)/8 должно быть целым и неотрицательным, а, значит, нужно, чтобы выражение 39 - 5х без остатка делилось на 8. Простой перебор вариантов показывает, что это возможно только при х = 3, тогда у = 3.
Ответ: (3; 3).
10. На мебельной фабрике изготовляют табуреты с тремя и с четырьмя ножками. Мастер сделал 18 ножек. Какое количество табуретов можно изготовить так, чтобы использовать все ножки?
Пусть x - количество трехногих табуретов, а у - количество четырехногих. Тогда, 3x + 4y = 18.
Имею, 4y =18 - 3x; y = 3(6 - x):4.
Получаю: x = 2; y = 3 или x = 6; y = 0.
Других решений нет, так как x 6.
Ответ. 2;3;(6;0).
11. Можно ли разместить 718 человек в 4-х и 8 - ми местных каютах, так что бы в каютах не было свободных мест?
Пусть 4-х местных кают - х, а 8-ми местных - у, тогда:
2(х + 2у) = 309
Ответ. Нельзя.
12. Доказать, что на прямой 124х + 216у = 515 нет ни одной точки с целочисленными координатами.
НОД(124;216) = 4, 515 != 4n, значит, целочисленных решений нет.
Ответ. Решений нет.
13. Стоимость товара 23 рубля, покупатель имеет только 2-х рублевые, а кассир 5-ти рублевые монеты. Можно ли осуществить покупку без предварительного размена денег?
Пусть х - количество 2-х рублевых монет, у - количество 5-ти рублевых монет, тогда 2х - 5у = 23, где х,у є N.
Получаю: 2х = 23 + 5у, откуда х =23 + 5у2 =11 + 2у + (1 + у)2 х будет целым, если 1 + у2 есть число целое.
1 + у2 = t, где t Euro Z, тогда у = 2t - 1.
x = 11 + 2y + 1 + у2 = 11 + 4t - 2 + 1 + 2t-12 = 5t + 9.
T. o. x = 5t + 9, a y = 2t - 1, где t є z.
Задача имеет множество целочисленных решений. Простейшее из них при t = 1, x =14, y = 1, т. е. покупатель даст четырнадцать 2-х рублёвых монет и получит сдачу одну 5-ти рублёвую монету.
Ответ. Можно.
14. При ревизии торговых книг магазина одна из записей оказалась залитой чернилами и имела такой вид:
> Невозможно было разобрать число проданных метров, но было несомненно, что число это не дробное; в вырученной сумме можно было различить только три последние цифры, да установить еще, что перед ними были три какие-то другие цифры. Можно ли по этим данным восстановить запись?
Пусть число метров было х, тогда стоимость товара в копейках - 4936х. Три залитые цифры в сумме обозначим за у, это число тысяч копеек, а вся сумма в копейках выразится так (1000у + 728).
Получаю уравнение 4936х = 1000у + 728, поделю его на 8.
617х - 125у = 91, где х,у є z, x,y
125у =617х - 91 у = 5х - 1 +34 - 8х125 = 5х - 1 + 2 17 - 4х125 =
5х - 1 + 2t, где t = 17 - 4х125, t Euro Z.
Из уравнения t = (17 - 4х)/125 получаю х = 4 - 31t + 1 - t4 =
4 - 31t + t1, где t1 = 1 - t4, отсюда t = 1 - 4t1, a x = 125t1 - 27, y = 617t1 - 134.
По условию знаю, что 100
100 = 234/617 и t1
Значит, было отпущено 98 метров на сумму 4837,28 рублей. Запись восстановлена.
Ответ. Отпущено 98 метров.
15. Требуется на один рубль купить 40 штук почтовых марок - копеечных, 4- копеечных и 12 - копеечных. Сколько марок каждого достоинства можно купить?
Можно составить два уравнения: x + 4у + 12z = 100 и x + y + z = 40, где х - число копеечных марок, у - 4-копеечных, z - 12-копеечных. Вычитаю из первого уравнения второе получаю:
3у + 11z = 60, y = 60 - 11z3 = 20 - 11· z3.
Пусть z3 = t, z = 3t, где t Euro Z. Тогда получаю, если х + у + z = 40 и z = 3t, а у = 20 - 11t, х = 20 + 8t.
Т. к. х >= 0, у >= 0, z >= 0, то 0
Тогда соответственно получаю: t = 0, х = 20, у = 20, z= 0; t = 1, х = 28, у = 9, z = 3.
Итак, покупка марок может быть произведена только двумя способами, а если поставить условие, чтобы была куплена хотя бы одна марка каждого достоинства, - только одним способом.
Ответ. 28 марок по 1 копейке, 9 марок по 4 копейки и 3 марки по 12 копеек.
16. Ученику дали задание из 20 задач. За каждую верно решенную он получает 8 баллов, за каждую, не решенную, с него снимают 5 баллов. За задачу, за которую он не брался - 0 баллов. Ученик в сумме набрал 13 баллов. Сколько задач он брался решать?
Пусть верно решенных задач - х, а неверно решенных - у, не рассмотренных - z.
Тогда х + у + z = 20, а 8х - 5у = 13.
у = 8х - 135= х - 2 +3(х - 1)5 = х - 2 + 3t, где t = х - 15, а х = 5t + 1.
По условию х + у
Ответ: ученик брался решать 13 задач, 6 решил, с 7 не справился.
17. Иванушка Дурачок бьется со Змеем Горынычем, у которого 2001 голова. Махнув мечем налево, Иван срубает 10 голов, а взамен вырастают 16. Махнув, мечем направо - срубает15, вырастают - 6. Если все головы срублены - новых не вырастает. Махать можно в произвольном порядке, но если голов меньше 15, то только налево, а если меньше 10, то вообще нельзя. Может ли Иванушка Дурачок победить Змея Горыныча?
Переформулирую задачу: можно ли срубить 1986 голов? Тогда, оставшиеся 15, Иван срубит одним ударом направо и новых не вырастет.
Пусть х - число ударов направо, а у - число ударов налево, тогда 1986 - 9х + 6у = 0.
Поделю всё уравнение на 6, получу
3х - 2у = 662.
у = 3х - 6622= х - 331 + х2.
Пусть х2 = t, тогда x = 2t, a y = 3t - 331.
Т. к. х >= 0, у >= 0, то t >= 111, отсюда t = 111, х = 222, у = 2.
Получаю: ударив 220 раз направо, Иван срубает 1980 голов и у Змея остаётся 21 голова; затем 2 удара налево и у Змея вырастают 12 голов, всего их становится 33; следующие 2 удара направо лишают Змея 18 голов и оставшиеся 15 Иван срубает последним ударом направо и новых голов уже не вырастает.
Ответ: 220 ударов направо, 2 удара налево и ещё 3 удара направо.
18. У игрального кубика грани пронумерованы - 1, 2, 3, 4, 5, 6. Из 5 таких кубиков сложили башню и сосчитали сумму очков на всех видимых гранях, после того как сняли верхний куб сумма уменьшилась на 19, какое число оказалось на верхней грани верхнего куба?
Сумма очков одного куба - 21.
Пусть х - количество очков на нижней грани верхнего куба, а у - количество очков на верхней грани следующего куба. При снятии верхнего куба, пропадают очки 5 граней верхнего куба, сумма очков которых (21 - х), а появляется грань на которой у очков, значит, сумма очков уменьшилась на (21 - х) - у, а по условию это 19, отсюда:
(21 - х) - у = 19, х + у = 2.
Отсюда у = 2 - х, а по условию 1
19. Некто купил 30 птиц за 30 монет одного достоинства. За каждых 3 воробьёв уплачена одна монета, за 2 снегиря - 1 монета, за 1 голубя - 2 монеты. Сколько птиц каждого вида было?
Пусть воробьёв было - х, снегирей - у, а голубей - z. Тогда, согласно условию х + у + z = 30 и 13x + 12y + 2z = 30.
Получаю х + у + z = 30 и 2x + 3y + 12z = 180, или y + 10z = 120, y = 120 - 10z, где по условию х
Отсюда следующие варианты (0;20;10); (9;10;11); (18;0;12).
Ответ: воробьев - 0, снегирей - 20, голубей - 10; воробьев - 9, снегирей - 10, голубей - 11; воробьев - 18, снегирей - 0, голубей - 12.
20. Найти все двухзначные числа, каждое из которых, будучи уменьшено на 2, равно упятеренному произведению своих цифр.
Пусть ху искомые двузначные числа.
Для уравнения ху - 2 = 5ху, или (10х + у) - 5ху = 2 S = 0 и все натуральные решения найду из множества (х; 2).
Т. к. х - первая цифра двухзначных чисел, то она может принимать только 9 значений.
Т. о. , искомыми числами будут: 12, 22, 32,. , 92.
Ответ. 12; 22, 32; 42; 52; 62; 72; 82; 92.
21. Кусок проволоки длиной 102 см нужно разрезать на части длиной 15 см и 12 см так, чтобы была использована вся проволока. Как это сделать?
Пусть х- число частей проволоки длиной 15 см, у- число частей проволоки длиной 12 см. Составлю уравнение:
15х+12у=102 /:3
4х+3у=34 х=34-4у5=6+4-4у5=6+4(1-у)5.
Пусть 1-у5=t х=6+4t>0у=1-5t>0=> 4t>-6-5t>-1 => t>-1,5t t=0;-1.
Если t=0, то х=6у=1
Если t=-1, то х=2у=6
Ответ. Задача имеет два решения:
1) 102=15∙6+12∙1; 2) 102=15∙2+12∙6.
22. Пете в 1987 году было столько лет, какова сумма цифр года его рождения. В каком году он родился?
Пусть Петя родился в 19ху году. Тогда в 1987 году ему было 1987-19ху, или (1+9+х+у) лет. Имеем уравнение:
87-(10х+у)=10+х+у
77-11х=2у у=77-11х2=38-11х-12.
Учитывая, что х и у - цифры десятичной системы счисления, то подбором находим: х=3, у=1.
Ответ. Петя родился в 1970 году.
23. Некто покупает в магазине вещь стоимостью 19 р. У него имеются лишь 15-трехрублевок, у кассира же лишь 20-пятирублевок. Можно ли расплатиться и как?
Задача сводится к решению в целых положительных числах диофантова уравнения: 3x - 5y = 19, где x
Ввиду того, что x>0 и y > 0 и учитывая условия задачи, легко установить, что 0
Отсюда вытекает 2 возможных значения: x
Ответ. 1) 19=3∙8-1∙5 2) 19=3∙13-4∙5.
24. Можно ли отвесить 28 г некоторого вещества на чашечных весах, имея только 4 гири весом в 3 г и 7 гирь весом в 5г?
Для этого нужно решить уравнение:
x = 9 - 2(3y1 - 1) + y1 = 11-5y1.
Итак, x = 11 - 5 y1 y = 3 y1 - 1.
Из условий задачи вытекает, что y1 нельзя давать отрицательные значения. Далее должно быть y1
Ответ. 1 гиря в 3 г и 5 гирь в 5 г.
25. Покупатель приобрел в магазине на 21 р. товара. Но у него в наличии денежные знаки только 5 - рублевого достоинства, а у кассира - 3 - рублевого. Требуется знать, можно ли при наличии денег расплатиться с кассиром и как именно?
Пусть x - число 5 - рублевок, y - 3 - рублевок.
По условию x > 0, y > 0, значит.
Кроме того, t - четное, иначе ни x, ни y не будет целыми.
При t = 4, 6, 8,. имеем: t
Ответ. 6;3;8;8;12;13;15;18;18;23;21;28;24;33;27;38;(30;43).
26. Имеется 110 листов бумаги. Требуется из них сшить тетради по 8 листов и по 10 листов в каждой. Сколько надо сшить тех и других?
Пусть x - число 8 - листовых тетрадей, y - число 10 - листовых тетрадей.
Значит t = 0 или t = - 1
Ответ. 5;7;(10;3).
27. Многие старинные способы отгадывания чисел и дат рождения основываются на решении диофантовых уравнений. Тех, например, чтобы отгадать дату рождения (месяц и число) собеседника, достаточно узнать у него сумму, получаемую от сложения двух произведений: числа даты (x) на 12 и номера месяца (y) на 31.
Пусть сумма произведений, о которых идет речь, равна 330. Найти дату рождения.
Решим неопределенное уравнение: y = 2y1 + y2 = 2(2y2 + y3) + y2 = 5y2 + 2y3 = 5(2y3 - 6) + 2y3 = 12y3 - 30 x = 27 - 3(12y3 - 30) + 2y2 + y3 = 27 - 36y3 + 90 + 2(2y3 - 6) + y3 =
27 - 36y3 + 90 + 5y3 - 12 = 105 - 31y3 x = 12y3 - 30, y = 105 - 31y3
Итак, дата рождения: 12 число 6 - го месяца.
28. Можно ли двухрублевыми и пятирублевыми монетами набрать сумму в 51 рубль? Если можно, то сколько существует способов?
Пусть было х - двухрублевых монет, а пятирублевых - у монет.
Пусть 1+у2=z, тогда
=> z = 1, 2, 3, 4, 5
Ответ: 5 способов.
29. Можно ли разложить две сотни яиц в коробки по 10 и по 12 штук? Если можно, то найдите все такие способы.
Пусть было х коробок по 10 штук и у коробок по 12 штук. Составлю уравнение: z = 1, 2, 3
Ответ: 14;5;8;10;(2;15)
30. Представьте число 257 в виде суммы двух натуральных слагаемых: а) одно из которых кратное 3, а другое - 4; б) одно из которых кратное 5, а другое - 8.
Ответ: 1) 249 и 8; 2) 225 и 32.
В задачах на неопределенные уравнения я столкнулась с самыми разнообразными случаями: задача может быть совсем неразрешимой (Задача 4), может иметь бесконечное множество решений (Задача 2), может иметь несколько определенных решений; в частности, она может иметь одно единственное решение (Задача 1).
ЗАКЛЮЧЕНИЕ
Цель, которую я поставила перед собой, мной реализована. Работа над проектом вызвала интерес и увлекла меня. Эта работа потребовала от меня не только определенных математических знаний и настойчивости, но и дала мне возможность почувствовать огромную радость самостоятельного открытия.
Диофантовы уравнения встречаются в олимпиадных заданиях, поэтому они развивают логическое мышление, повышают уровень математической культуры, прививают навыки самостоятельной исследовательской работы в математике.
При решении уравнений и задач, сводящихся к диофантовым уравнениям, применяются свойства простых чисел, метод разложения многочлена на множители, метод перебора, метод спуска и алгоритм Евклида. На мой взгляд, метод спуска самый сложный. А симпатичнее для меня оказался метод перебора.
В работе мною решено 54 задачи.
Эта работа способствовала более глубокому пониманию школьной программы и расширению кругозора.
Данный материал будет полезен учащимся, интересующихся математикой. Его можно использовать на некоторых уроках и на факультативных занятиях.
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Объект исследования.
Исследования касаются одного из наиболее интересных разделов теории чисел - решения уравнений в целых числах.
Предмет исследования.
Решение в целых числах алгебраических уравнений с целыми коэффициентами более чем с одним неизвестным представляет собой одну из труднейших и древнейших математических задач и не достаточно глубоко представлена в школьном курсе математики. В своей работе я представлю достаточно полный анализ уравнений в целых числах, классификацию данных уравнений по способам их решения, описание алгоритмов их решения, а также практические примеры применения каждого способа для решения уравнений в целых числах.
Цель.
Познакомиться со способами решения уравнений в целых числах.
Задачи:
Изучить учебную и справочную литературу;
Собрать теоретический материал по способам решения уравнений;
Разобрать алгоритмы решения уравнений данного вида;
Описать способы решения;
Рассмотреть примеры решения уравнений с применением данных способов.
Гипотеза:
Столкнувшись с уравнениями в целых числах в олимпиадных заданиях, я предположила, что трудности в их решении обусловлены тем, что далеко не все способы их решения мне известны.
Актуальность:
Решая примерные варианты заданий ЕГЭ, я заметила, что часто встречаются задания на решение уравнений первой и второй степени в целых числах. Кроме того олимпиадные задания различных уровней также содержат уравнения в целых числах или задачи, которые решаются с применением умений решать уравнения в целых числах. Важность знания способов решения уравнений в целых числах и определяет актуальность моих исследований.
Методы исследования
Теоретический анализ и обобщение сведений научной литературы об уравнениях в целых числах.
Классификация уравнений в целых числах по методам их решения.
Анализ и обобщение методов решения уравнений в целых числах.
Результаты исследования
В работе описаны способы решений уравнений, рассмотрен теоретический материал теоремы Ферма, теорема Пифагора, алгоритма Евклида, представлены примеры решений задач и уравнений различных уровней сложности.
2.История уравнений в целых числах
Диофант - ученый - алгебраист Древней Греции, по некоторым данным он жил до 364 года н. э. Он специализировался на решении задач в целых числах. Отсюда и пошло название Диофантовы уравнения. Наиболее известной, решенной Диофантом, является задача «о разложении на два квадрата». Ее эквивалентом является известная всем теорема Пифагора. Жизнь и деятельность Диофанта протекала в Александрии, он собирал и решал известные и придумывал новые задачи. Позднее он объединил их в большом труде под названием «Арифметика». Из тринадцати книг, входивших в состав «Арифметики», только шесть сохранились до Средних веков и стали источником вдохновения для математиков эпохи Возрождения.«Арифметика» Диофанта — это сборник задач, каждая включает в себя решение и необходимое пояснение. В собрание входят разнообразные задачи, а их решение часто в высшей степени остроумно. Диофанта интересуют только положительные целые и рациональные решения. Иррациональные решения он называет «невозможными» и тщательно подбирает коэффициенты так, чтобы получились искомые положительные, рациональные решения.
Для решения уравнений в целых числах применяется теорема Ферма. История доказательства которой достаточно интересная. Над полным доказательством Великой теоремы работало немало выдающихся математиков, и эти усилия привели к получению многих результатов современной теории чисел. Считается, что теорема стоит на первом месте по количеству неверных доказательств.
Замечательный французский математик Пьер Ферма высказал утверждение, что уравнение при целом n ≥ 3 не имеет решений в целых положительных числах x, y, z (xyz = 0 исключается положительностью x, y, z.Для случая n = 3 эту теорему в X веке пытался доказать среднеазиатский математик ал-Ходжанди, но его доказательство не сохранилось. Несколько позже сам Ферма опубликовал доказательство частного случая для n = 4.
Эйлер в 1770 доказал теорему для случая n = 3, Дирихле и Лежандр в 1825 — для n = 5,Ламе — для n = 7. Куммер показал, что теорема верна для всех простых n, меньших 100, за возможным исключением 37, 59, 67.
В 1980-х годах появился новый подход к решению проблемы. Из гипотезы Морделла, доказанной Фальтингсом в 1983 году, следует, что уравнение
при n > 3 может иметь лишь конечное число взаимно простых решений.
Последний, но самый важный, шаг в доказательстве теоремы был сделан в сентябре 1994 года Уайлсом. Его 130-страничное доказательство было опубликовано в журнале «AnnalsofMathematics». Доказательство основано на предположении немецкого математика Герхарда Фрая о том, что Великая теорема Ферма является следствием гипотезы Таниямы — Симуры (это предположение было доказано Кеном Рибетом при участии Ж.‑П.Серра.).Первый вариант своего доказательства Уайлс опубликовал в 1993 году (после 7 лет напряжённой работы), но в нём вскоре обнаружился серьёзный пробел; с помощью Ричарда Лоуренса Тейлора пробел удалось достаточно быстро ликвидировать. В 1995 году был опубликован завершающий вариант. 15 марта 2016 года Эндрю Уайлз получает премию Абеля. В настоящее время премия составляет 6 миллионов норвежских крон, то есть примерно 50 миллионов рублей. По словам Уайлса, присуждение премии стало для него «полной неожиданностью».
3.Линейные уравнения в целых числах
Линейные уравнения - самые простые из всех диофантовых уравнений.
Уравнение вида ах=b, где a и b - некоторые числа, а х- неизвестная переменная, называется линейным уравнением с одной неизвестной. Здесь требуется найти только целые решения уравнения. Можно заметить, что если а ≠ 0, то целочисленное решение уравнение будет иметь только в том случае, когда b нацело делится на а и это решение х= b/ф. Если же а=0, то целочисленное решение уравнение будет иметь тогда, когда b=0 и в этом случае х любое число.
т.к. 12 нацело делится на 4, то
Т.к. а=о и b=0, то х любое число
Т.к. 7 нацело не делится на 10, то решений нет.
4. Способ перебора вариантов .
В способе перебора вариантов необходимо учитывать признаки делимости чисел, рассмотреть все возможные варианты равенства конечного перебора. Этот способ можно применить решая данные задачи:
№1 Найти множество всех пар натуральных чисел, которые являются решением уравнения 49x+69y=602
Выражаем из уравнения х =,
Т.к. x и y натуральные числа, то х = ≥ 1, умножаем все уравнение на 49, чтобы избавиться от знаменателя:
Переносим 602 в левую сторону:
51y ≤ 553, выражаем y, y= 10
Полный перебор вариантов показывает, что натуральными решениями уравнения являются x=5, y=7.
Ответ:(5,7).-
№2 Решить задачу
Из цифр 2, 4, 7 следует составить трёхзначное число, в котором ни одна цифра не может повторяться более двух раз.
Найдем количество всех трехзначных чисел, которые начинаются с цифры 2: (224, 242, 227, 272, 247, 274, 244, 277) - их 8.
Аналогично находим все трехзначные цифры начинающиеся с цифр 4 и 7: (442, 424, 422, 447, 474, 427, 472, 477).
(772, 774, 727, 747, 722, 744, 724, 742) - их тоже по 8 чисел. Следует всего 24 числа.
Ответ: 24 числа.
5. Цепная дробь и алгоритм Евклида
Цепной дробью называется выражение обыкновенной дроби в виде
где q 1 - целое число, а q 2 , … ,qn - натуральные числа. Такое выражение называется цепной (конечной непрерывной) дробью. Различают конечные и бесконечные цепные дроби.
Для рациональных чисел цепная дробь имеет конечный вид. Кроме того, последовательность a i — это ровно та последовательность частных, которая получается при применении алгоритма Евклида к числителю и знаменателю дроби.
Решая уравнения цепной дробью, я составила общий алгоритм действий для данного способа решения уравнений в целых числах.
Алгоритм
1) Составить отношение коэффициентов при неизвестных в виде дроби
2) Преобразовать выражение в неправильную дробь
3) Выделить целую часть неправильной дроби
4) Правильную дробь заменить равной ей дробью
5) Проделать 3,4 с полученной в знаменателе неправильной дробью
6) Повторять 5 до конечного результата
7) У полученного выражения отбросить последнее звено цепной дроби, превратить получающуюся при этом новую цепную дробь в простую и вычесть ее из исходной дробь.
Пример №1 Решить в целых числах уравнение 127x- 52y+ 1 = 0
Преобразуем отношение коэффициентов при неизвестных.
Прежде всего, выделим целую часть неправильной дроби; = 2 +
Правильную дробь заменим равной ей дробью.
Откуда = 2+
Проделаем такие же преобразования с полученной в знаменателе неправильной дробью.
Теперь исходная дробь примет вид: .Повторяя те же рассуждения для дроби получим Выделяя целую часть неправильной дроби, придем к окончательному результату:
Мы получили выражение, которое называется конечной цепной или непрерывной дробью. Отбросив последнее звено этой цепной дроби - одну пятую, превратим получающуюся при этом новую цепную дробь в простую и вычтем ее из исходной дроби:
Приведем полученное выражение к общему знаменателю и отбросим его.
Откуда 127∙9-52∙22+1=0. Из сопоставления полученного равенства с уравнением 127x- 52y+1 = 0 следует, что тогда x= 9, y= 22 - решение исходного уравнения, и согласно теореме все его решения будут содержаться в прогрессиях x= 9+ 52t, y= 22+ 127t, где t=(0; ±1; ±2…..).Полученный результат наводит на мысль о том, что и в общем случае для нахождения решения уравнения ax+by+c=0 надо разложить отношение коэффициентов при неизвестных в цепную дробь, отбросить ее последнее звено и проделать выкладки, подобные тем, которые были приведены выше.
Для доказательства этого предположения будут нужны некоторые свойства цепных дробей.
Рассмотрим несократимую дробь. Обозначим через q 1 частное и через r 2 остаток от деления a на b. Тогда получим:
Тогда b=q 2 r 2 +r 3 ,
Точно так же
r 2 =q 3 r 3 +r 4 , ;
r 3 =q 4 r 4 +r 5 ,;
………………………………..
Величины q 1 , q 2 ,… называются неполными частными. Приведенный выше процесс образования неполных частных называется алгоритмом Евклида . Остатки от деления r 2 , r 3 ,…удовлетворяют неравенствам
т.е. образуют ряд убывающих неотрицательных чисел.
Пример№2 Решить уравнение170х+190у=3000 в целых числах
После сокращения на 10 уравнение выглядит так,
Для нахождения частного решения воспользуемся разложением дроби в цепную дробь
Свернув предпоследнюю подходящую к ней дробь в обыкновенную
Частное решение данного уравнения имеет вид
Х 0 = (-1)4300∙9=2700, y 0 =(-1)5300∙8=-2400,
а общее задается формулой
х=2700-19k, y= -2400+17k.
откуда получаем условие на параметр k
Т.е. k=142, x=2, y=14. .
6. Метод разложения на множители
Метод перебора вариантов неудобный способ, так как бывают случаи когда найти перебором всецелые решения, невозможно, так как таких решений бесконечное множество. Метод разложения на множители очень интересный прием и встречается он как и в элементарной математике так и в высшей.
Суть состоит в тождественном преобразовании. Смысл любого тождественного преобразования - это запись выражения в другом виде с сохранением его сути. Рассмотрим примеры применения данного метода.
№1 Решить уравнение в целых числах y 3 - x 3 = 91.
Используя формулы сокращенного умножения, разложим правую часть уравнения на множители:
(y - x)(y 2 + xy + x 2) = 91
Выписываем все делители числа 91: ± 1; ± 7; ± 13; ± 91
Замечаем, что для любых целых x и y число
y 2 + yx + x 2 ≥ y 2 - 2|y||x| + x 2 = (|y| - |x|) 2 ≥ 0,
следовательно, оба сомножителя в левой части уравнения должны быть положительными. Тогда исходное уравнение равносильно совокупности систем уравнений:
Решив системы, отбираем те корни, которые являются целыми числами.
Получаем решения исходного уравнения: (5; 6), (-6; -5); (-3; 4),(-4;3).
Ответ: (5; 6); (-6; -5); (-3; 4); (-4;3).
№2 Найти все пары натуральных чисел, удовлетворяющих уравнению х 2 -у 2 = 69
Разложим левую часть уравнения на множители и запишем уравнение в виде
Т.к. делителями числа 69 являются числа 1, 3, 23 и 69, то 69 можно получить двумя способами: 69=1·69 и 69=3·23. Учитывая, что х-у > 0, получим две системы уравнений, решив которые мы сможем найти искомые числа:
Выразив одну переменную и подставив ее в второе уравнение находим корни уравнений.Первая система имеет решение x=35;y=34 , а вторая система имеет решение x=13, y=10.
Ответ: (35; 34), (13; 10).
№3 Решить уравнение х+у =ху в целых числах:
Запишем уравнение в виде
Разложим левую часть уравнения на множители. Получим
Произведение двух целых чисел может равняться 1 только в двух случаях: если оба они равны 1 или -1. Получим две системы:
Первая система имеет решение х=2, у=2, а вторая система имеет решение х=0, у=0.Ответ: (2; 2), (0; 0).
№4 Доказать, что уравнение (x - y) 3 + (y - z) 3 + (z - x) 3 = 30 не имеет решений в целых числах.
Разложим левую часть уравнения на множители и обе части уравнения разделим на 3, в результате получим уравнение:
(x - y)(y - z)(z - x) = 10
Делителями 10 являются числа ±1, ±2, ±5, ±10. Заметим также, что сумма сомножителей левой части уравнения равна 0. Нетрудно проверить, что сумма любых трех чисел из множества делителей числа 10, дающих в произведении 10, не будет равняться 0. Следовательно, исходное уравнение не имеет решений в целых числах.
7. Метод остатков
Основная задача метода - находить остаток от деления обоих частей уравнения на целое число, на основе полученных результатов. Часто полученная информация уменьшает возможности множеств решений уравнения. Рассмотрим примеры:
№1 Доказать, что уравнение x 2 = 3y + 2 не имеет решений в целых числах.
Доказательство.
Рассмотрим случай, когда x, y ∈ N. Рассмотрим остатки от деления обоих частей на 3. Правая часть уравнения дает остаток 2 при делении на 3 при любом значении y. Левая же часть, которая является квадратом натурального числа, при делении на 3 всегда дает остаток 0 или 1. Исходя из этого получаем, что решения данного уравнения в натуральных числах нет.
Рассмотрим случай, когда одно из чисел равно 0. Тогда очевидно, решений в целых числах нет.
Случай, когда y - целое отрицательное не имеет решений, т.к. правая часть будет отрицательна, а левая - положительна.
Случай, когда x - целое отрицательное, также не имеет решений, т.к. попадает под один из рассмотренных ранее случаев ввиду того, что (-x) 2 = (x) 2 .
Получается, что указанное уравнение не имеет решений в целых числах, что и требовалось доказать.
№2 Решите в целых числах 3 х = 1 + y 2 .
Не сложно заметить, что (0; 0) — решение данного уравнения. Остаётся доказать, что других целых корней уравнение не имеет.
Рассмотрим случаи:
1) Если x∈N, y∈N, то З делится на три без остатка, а 1 + y 2 при делении на 3 дает
остаток либо 1, либо 2. Следовательно, равенство при натуральных
значениях х, у невозможно.
2) Если х— целое отрицательное число,y∈Z , тогда 0< 3 х < 1, а 1 + y 2 ≥ 0 и
равенство также невозможно. Следовательно, (0; 0) — единственное
Ответ: (0; 0).
№3 Решить уравнение 2х 2 -2ху+9х+у=2 в целых числах:
Выразим из уравнения то неизвестное, которое входит в него только в первой степени, то есть переменную у:
2х 2 +9х-2=2ху-у, откуда
Выделим у дроби целую часть с помощью правила деления многочлена на многочлен «углом». Получим:
Очевидно, разность 2х-1 может принимать только значения -3, -1, 1 и 3.
Осталось перебрать эти четыре случая, в результате чего получаем решения: (1;9), (2;8), (0;2), (-1;3)
Ответ: (1;9), (2;8), (0;2), (-1;3)
8.Пример решения уравнений с двумя переменными в целых числах как квадратных относительно одной из переменных
№1 Решить в целых числах уравнение 5х 2 +5у 2 + 8ху+2у-2х +2=0
Данное уравнение можно решить методом разложения на множители, однако этот способ применительно к данному уравнению достаточно трудоёмкий. Рассмотрим более рациональный способ.
Запишем уравнение в виде квадратного относительно переменной х:
5x 2 +(8y-2)x+5y 2 +2y+2=0
Находим его корни.
Данное уравнение имеет решение тогда и только тогда, когда дискриминант
этого уравнения равен нулю, т.е. - 9(у+1) 2 =0, отсюда у= - 1.
Если у= -1,то х= 1.
Ответ: (1; — 1).
9.Пример решения задач с помощью уравнений в целых числах.
№ 1. Решить в натуральных числах уравнение : где n>m
Выразим переменную n через переменную m:
Найдем делители числа 625: это 1; 5; 25; 125; 625
1) если m-25 =1, то m=26, n=25+625=650
2) m-25 =5, то m=30, n=150
3) m-25 =25, то m=50, n=50
4) m-25 =125, то m=150, n=30
5) m-25 =625, то m=650, n=26
Ответ: m=150, n=30
№ 2. Решить уравнение в натуральных числах: mn +25 = 4m
Решение: mn +25 = 4m
1) выразим переменную 4m через n:
2) найдем натуральные делители числа 25: это 1; 5; 25
если 4-n =1, то n=3, m=25
4-n=5, то n=-1, m=5; 4-n =25, то n=-21, m=1 (посторонние корни)
Ответ: (25;3)
Помимо заданий решить уравнение в целых числах, встречаются задания на доказательство того факта, что уравнение не имеет целых корней.
При решении таких задач, необходимо помнить следующие свойства делимости:
1) Если n Z; n делится на 2, то n = 2k, k ∈ Z.
2) Если n ∈ Z; n не делится на 2, то n = 2k+1, k ∈ Z.
3) Если n ∈ Z; n делится на 3, то n = 3k, k ∈ Z.
4) Если n ∈ Z; n не делится на 3, то n = 3k±1, k ∈ Z.
5) Если n ∈ Z; n не делится на 4, то n = 4k+1; n = 4k+2; n = 4k+3. k ∈ Z.
6) Если n ∈ Z; n(n+1) делится на 2, то n (n+1)(n+2) делится на 2;3;6.
7) n; n+1 - взаимно простые.
№3 Доказать, что уравнение x 2 - 3у = 17 не имеет целых решений.
Доказательство:
Пусть x; y - решения уравнения
x 2 = 3(у+6)-1 Т.к. y ∈ Z то y+6 ∈ Z , значит 3(y+6) делится на 3, следовательно, 3(y+6)-1 не делится на 3, следовательно, x 2 не делится на 3, следовательно, x не делится на 3, значит x = 3k±1, k ∈ Z.
Подставим это в исходное уравнение.
Получили противоречие. Значит у уравнения нет целых решений, что и требовалось доказать.
10.Формула Пика
Формула Пика была открыта австрийским математиком Георгом Пиком в 1899 году. Формула связанна с уравнениями в целых числах тем, что из многоугольников берут только целые узлы, как и целые числа в уравнениях.
При помощи этой формулы можно находить площадь фигуры построенной на листе в клетку (треугольник, квадрат, трапеция, прямоугольник, многоугольник).
В этой формуле будем находить целые точки внутри многоугольника и на его границе.
В задачах, которые будут на ЕГЭ есть целая группа заданий, в которых дан многоугольник построенный на листе в клетку и стоит вопрос о нахождении площади. Масштаб клетки это один квадратный сантиметр.
Пример№1
М - количество узлов на границе треугольника (на сторонах и вершинах)
N - количество узлов внутри треугольника.
*Под «узлами» имеется ввиду пересечение линий. Найдём площадь треугольника:
Отметим узлы:
M = 15 (обозначены красным)
N = 34 (обозначены синим)
Пример №2
Найдём площадь многоугольника: Отметим узлы:
M = 14 (обозначены красным)
N = 43 (обозначены синим)
12.Метод спуска
Один из методов решений уравнений в целых числах - метод спуска - опирается на теорему Ферма.
Методом спуска называется метод, который заключается в построении одного решения бесчисленной последовательности решений с неограниченно убывающим положительным z.
Алгоритм этого метода рассмотрим на примере решения конкретного уравнения.
Пример 1. Решить уравнение в целых числах 5x + 8y = 39.
1) Выберем неизвестное, имеющее наименьший коэффициент (в нашем случае это х), и выразим его через другое неизвестное:
2) Выделим целую часть: Очевидно, что х будет целым, если выражение окажется целым, что, в свою очередь, будет иметь место тогда, когда число 4 - 3y без остатка делится на 5.
3) Введем дополнительную целочисленную переменную z следующим образом: 4 -3y = 5z. В результате получим уравнение такого же типа, как и первоначальное, но уже с меньшими коэффициентами.
4) Решаем его уже относительно переменной y, рассуждая точно также как в п.1, 2: Выделяя целую часть, получим:
5) Рассуждая аналогично предыдущему, вводим новую переменную u: 3u = 1 - 2z.
6) Выразим неизвестную с наименьшим коэффициентом, в этом случае переменную z: . Требуя, чтобы было целым, получим: 1 - u = 2v, откуда u = 1 - 2v. Дробей больше нет, спуск закончен (процесс продолжаем до тез пор, пока в выражении для очередной переменной не останется дробей).
7) Теперь необходимо «подняться вверх». Выразим через переменную v сначала z, потом y и затем x:
8) Формулы x = 3+8v и y = 3 - 5v, где v - произвольное целое число, представляют общее решение исходного уравнения в целых числах.
Таким образом, метод спуска предполагает сначала последовательное выражение одной переменой чрез другую, пока в представлении переменной не останется дробей, а затем, последовательное «восхождение» по цепочке равенств для получения общего решения уравнения.
12.Заключение
В результате исследования подтвердилась гипотеза о том, что трудности при решении уравнений в целых числах обусловлены тем, что далеко не все способы их решения были мне известны. В ходе исследований мне удалось отыскать и описать малоизвестные способы решения уравнений в целых числах, проиллюстрировать их примерами. Результаты моих исследований могут быть полезны всем ученикам, интересующимся математикой.
13.Библиография
Книжные ресурсы:
1. Н. Я. Виленкин и др., Алгебра и математический анализ/10класс, 11 класс// М., «Просвещение», 1998 год;
2. А. Ф. Иванов и др., Математика. Учебно-тренировочные материалы для подготовки к экзамену// Воронеж, ГОУВПО ВГТУ, 2007 год
3. А. О. Гельфонд, Математика, теория чисел// Решение уравнений в целых числах// Книжный дом «ЛИБРОКОМ»
Ресурсы сети интернет:
4. Демонстрационные варианты контрольных измерительных материалов единого государственного экзамена по математике http://fipi.ru/
5. Примеры решений уравнений в целых числахhttp://reshuege.ru
6. Примеры решений уравнений в целых числахhttp://mat-ege.ru
7.История Диофантовых уравнений http://www.goldenmuseum.com/1612Hilbert_rus.html
8. История Диофанта http://nenuda.ru/%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F-%D1%81-%D0%B4%D0%B2%D1%83%D0%BC%D1%8F-%D0%BD%D0%B5%D0%B8%D0%B7%D0%B2%D0%B5%D1%81%D1%82%D0%BD%D1%8B%D0%BC%D0%B8-%D0%B2-%D1%86%D0%B5%D0%BB%D1%8B%D1%85-%D1%87%D0%B8%D1%81%D0%BB%D0%B0%D1%85.htm
9.История Диофантовых уравненийhttp://dok.opredelim.com/docs/index-1732.html
10. История Диофанта http://www.studfiles.ru/preview/4518769/
4.1. Линейное диофантово уравнение с двумя неизвестными
В этом разделе рассматривается линейное уравнение
где `a`, `b`, `c` - целые числа, причём `ab!=0` (иначе это уравнение с не более одной неизвестной).
Уравнения с целыми числами с двумя (и более) неизвестными наряду с большим количеством других интересных задач рассматривал в своей книге «Арифметика» греческий математик Диофант Александрийский (III в.). Такие уравнения были впоследствии названы его именем.
Докажите, что монетами в `2` и `5` рублей можно заплатить любую натуральную сумму рублей, кроме `1` и `3`.
Пусть сумма, которую нужно составить, равняется рублей, и мы заплатим её `x` монетами по `2` рубля и монетами по `5` рублей.
Отсюда получим уравнение `2x+5y=n`. Выразим `x` через `y`: `x=(n-5y)/2`.
Наша задача - найти хотя бы одно решение этого уравнения в целых неотрицательных числах. Если `n` делится на `2`, то в качестве такого решения можно взять `y=0`, `x=n//2`. Если же `n` не делится на `2`, то можно взять `y=1`, `x=(n-5)/2`. Здесь `x` не будет являться отрицательным, если `b>=5`. Таким образом, любую натуральную сумму рублей, кроме `1` и `3` можно заплатить монетами в `2` и `5` рублей.
Замечание
Если же в этой задаче разрешить давать сдачу (также только монетами `2` и `5` рублей), то тогда можно будет с учётом сдачи заплатить любую сумму рублей.
Перейдём к решению уравнения `ax+by=c`.
Уравнение `ax+by=c` имеет бесконечное множество целочисленных решений, если `c` делится на `"НОД"(a,b)` и не имеет целочисленных решений в противном случае.
Условие «`c` делится на `"НОД"(a,b)`», частности, всегда выполнено, когда числа `a` и `b` взаимно просты.
Диофантово уравнение `ax+by=c` можно решать по следующему алгоритму:
1.
Разделим обе части уравнения `ax+by=c` на `"НОД"(a,b)`. Числа `a` и `b`, поделённые на свой НОД, станут взаимно простыми. Если число `c`, разделённое нацело на `"НОД"(a,b)`, не является целым, то уравнение решений не имеет (слева стоит целое число, справа - нецелое).
Таким образом, мы пришли к равносильному уравнению `bar(a)x+bar(b)y=bar(c)`, где `"НОД"(bar(a),bar(b))=1`.
2. Итак, пусть теперь есть уравнение `ax+by=c`, где числа `a` и `b` являются взаимно простыми. Найдём какое-то одно (так называемое «частное») решение этого уравнения - `(x_0,y_0)` . Это можно сделать путём подбора или с помощью алгоритма Евклида (см. конец этого раздела).
3. Выпишем ответы: x = x 0 - b t y = y 0 + a t , t ∈ ℤ . \left\{\begin{array}{l}x=x_0-bt\\y=y_0+at\end{array}\right.,\:t\in\mathbb{Z}.
Почему все ответы имеют такой вид?
Пусть `(x_0,y_0)` - решение уравнения `ax+by=c`. Рассмотрим выражение `a(x-x_0)+b(y-y_0)`. Оно равняется нулю:
`a(x-x_0)+b(y-y_0)=ax+by-(ax_0+by_0)=c-c=0`.
Таким образом, числа `x-x_0` и `y-y_0` являются решениями уравнения `aX+bY=0`. Перепишем это уравнение в виде `aX=-bY`. Так как числа `a` и `b` - взаимно просты, число `Y` должно делиться на число `a`, т. е. `Y=at` при каком-то целом `t`. Подставим `Y` в уравнение `aX=-bY`, получим `aX=-bat`, что в свою очередь после сокращения на `a` преобразуется к виду `X=-bt`.
Итак, x - x 0 = - b t , y - y 0 = a t , \left\{\begin{array}{l}x-x_0=-bt,\\y-y_0=at,\end{array}\right. откуда и получаем выписанные в п. 3 ответы.
Решите уравнение `10x+4y=100`.
Разделим обе части уравнения на `"НОД"(10,4)=2`, получив уравнение `5x+2y=50`. Подбором получаем частное решение `x_0=10`, `y_0=0`.
Затем выпишем все решения этого уравнения: x = 10 - 2 t y = 5 t , t ∈ ℤ . \left\{\begin{array}{l}x=10-2t\\y=5t\end{array}\right.,\:t\in\mathbb{Z}.
x = 10 - 2 t y = 5 t , t ∈ ℤ . \left\{\begin{array}{l}x=10-2t\\y=5t\end{array}\right.,\:t\in\mathbb{Z}.
Опишем процесс нахождения «частного» решения с помощью алгоритма Евклида на примере диофантова уравнения `7x+18y=2`.
Найдите частное решение уравнения `7x+18y=2`.
Для начала найдём частное решение уравнения `7x+18y=1`, затем, домножим полученное решение на `2`, получим частное решение уравнения `7x+18y=2`.
Найдём `"НОД"(18,7)` с помощью алгоритма Евклида. `18=7*2+4`, поэтому `"НОД"(18,7)= "НОД"(7,4)`. Будем записывать каждое новое число, к которому мы приходим, выполняя алгоритм Евклида, в виде `7x+18y`. Так, `4 = 18 - 7*2`.
Затем `"НОД"(7,4) = "НОД"(4,3)`, где `3 = 7 - 4 = 7- (18 -7*2) = 7*3 - 18`.
Наконец, `"НОД"(4,3) = "НОД"(3,1) = 1`, причём
`1 = 4 - 3 = (18 - 7×2) - (7*3 -18) = 18*2 - 7×5`.
Вот, мы получили частное решение уравнения `7x+18y=1:` `x=-5, y=2`.
Отсюда частное решение уравнения `7x+18y=2` имеет вид `x_0=-10, y_0=4`.
Решая задачу другими способами, можно найти и другие частные решения.
Например, `x_0=8, y_0=-3`.
`x=-10, y=4`.*
4.2. Примеры решения нелинейных уравнений
Пример 21 (ЕГЭ, тренировочный вариант)
Группу школьников нужно перевезти из летнего лагеря одним из двух способов: либо двумя автобусами типа А за несколько рейсов, либо тремя автобусами типа В за несколько рейсов, причём в этом случае число рейсов каждого автобуса типа В будет на один меньше, чем рейсов каждого автобуса типа А. В каждом из случаев автобусы заполняются полностью. Какое максимальное количество школьников можно перевезти при указанных условиях, если в автобус типа В входит на `7` человек меньше, чем в автобус типа А.
Пусть в автобус типа В входит `x` человек (тогда в автобус типа А входит `x+7` человек), и автобусы типа B должны совершить `y` рейсов (тогда автобусы типа A должны совершить `y+1` рейс). По условию задачи составим выражение для количества детей, перевезённых обоими способами:
`2(x+7)(y+1)=3xy`.
Выразим переменную этого выражения через `y`.
`14y+2x+14-xy=0`; `x=(14y+14)/(y-2)`.
Выделим целую часть числа:
`(14y+14)/(y-2)`; `x=(14y+14)/(y-2)=14+42/(y-2)`.
Напомним, число `x` должно быть целым, отсюда получаем, что число `(y-2)` должно быть делителем числа `42`.
Переберём все делители числа `42` и выясним, какое максимальное количество детей `(3xy)` можно увезти:
| `y-2` | ||||||||
| `y` | ||||||||
| `x` | ||||||||
| `3xy` |
Максимальное количество школьников, которое можно перевезти согласно условиям задачи, равно `1980`.
Решите в целых числах уравнение `xy=5(x+y)`.
Перепишем уравнение в виде: `xy-5x-5y=0`;
`x(y-5)-5(y-5)-25=0`; `(x-5)(y-5)=25`.
Заметим, что `25` можно разложить на множители (в том числе отрицательные) только следующими способами:
`25=1*25=5*5=(-1)*(-25)=(-5)*(-5)`.
Из каждого из разложений получаем решения.
`(x,y)=(6,30);(30,6);(10,10);(4,-20);(-20,4);(0,0)`.
Решите в целых числах уравнение `x^2=2y^2+xy+7`.
Перепишем это уравнение в виде: `(x+y)(x-2y)=7`.
Это разложение можно получить следующим образом: запишем выражение `x^2-xy-2y^2=0` и вынесем `y^2` за скобки: `y^2[(x/y)^2-x/y-2]`.
Т. к. `(x+y)` и `(x-2y)` - целые числа, то нужно посмотреть на разложение числа `7` на два целых множителя. Возможные разложения выпишем в таблицу:
| `x+y=` | `7` | `1` | `-7` | `-1` |
| `x-2y=` | `1` | `7` | `-1` | `-7` |
Получаются `4` системы линейных уравнений. Решим одну из них (первую):
x + y = 7 , x - 2 y = 1 . \left\{\begin{array}{l}x+y=7,\\x-2y=1.\end{array}\right.
Получим: `x=5, y=2`.
Остальные системы выписываются аналогично, и все полученные решения будут являться целыми.
`(x,y)=(5,2);(-5,-2);(3;-2);(-3,2)`.
В обоих примерах мы раскладывали многочлен на множители и использовали свойства делимости.
Решите в целых числах уравнение `x^3-xy-7x+2y+23=0`.
В это уравнение переменная `y` входит в первой степени, выразим её через `x:`
`x^3+y(2-x)-7x+23=0, y=(x^3-7x+23)/(x-2)`.
Сделаем замену: `t=x-2`. Тогда `x=t+2`; `x^3=t^3+6t^3+12t+8` и, следовательно,
Разложив левую часть, получим `(1+x)(1+x^2)=2^y`.
Т. к. числа `x` и `x^2` - натуральные, `1+x>=2`; `1+x^2>=2`, значит, оба числа - `(1+x)` и `(1+x^2)` являются натуральными степенями двойки. Пусть `1+x=2^t`. Выразив из этого уравнения `x`, получим, `1+x^2=2^(2t)-2*2^t+2`. Это число также должно являться степенью двойки.
Если `t=1`, то `(x,y)=(1,2)` - решения нашего уравнения.
Если `t=2`, то `1+x^2=10`, что не является степенью двойки; решений в данном случае нет.
Если `t>=3`, то `2*2^t-2>0` и `2^(2t)-2*2^t+2<2^(2t)`. Докажем, что `2^(2t)-2*2^t+2>2^(2t-1)`. Это неравенство можно переписать в виде
`2^(2t-1)=2^(2t)-2^(2t-1)>2*2^t-2; 2^(2t-2)>2^t-1`.
Последнее неравенство является верным, т. к. при `t>=3` верно `2t-2>t`, что приведёт к неравенству `2^(2t-2)-2^t>0> -1`.
Таким образом, мы получили, что число `1+x^2=2^(2t)-2*2^t+2` заключено строго между двумя соседними степенями двойки, `2^(2t-1)<2^(2t)-2*2^t+2<2^(2t)`, а, значит, само степенью двойки не является. Противоречие, решений при `t>=3` нет.
Задача 12.
Решите в целых числах 5х²+ 5у² + 8ху + 2у – 2у + 2 = 0 .
Решение.
Если попытаться решить данное уравнение методом разложения на множители, то это достаточно трудоёмкая работа, поэтому это уравнение можно решить более изящным методом. Рассмотрим уравнение, как квадратное относительн о х 5х²+(8у-2)х+5у²+2у +2=0 , х1,2 = (1 – 4у ±√(1 – 4у) ² - 5(5у² + 2у + 2))/5 = (1 – 4у ±√ -9(у + 1)²)/5.
Данное уравнение имеет решение тогда, когда дискриминант равен нулю, т.е. –9(у + 1) = 0 , отсюда у = -1 . Если у = -1 , то х =1 .
Ответ.
Задача 13.
Решите в целых числах 3(х² + ху + у²)= х + 8у
Решение.
Рассмотрим уравнение, как квадратное относительно х 3х ² + (3у - 1)х + 3у² - 8у = 0. Найдём дискриминант уравнения D = =(3у – 1) ² - 4 * 3(3у² - 8у) = 9у² - 6у + 1 – 36у² + 96у = -27у² + 90у + 1.
Данное уравн ение имеет корни, если D ³ 0 , т. е. –27у² + 90 у + 1³ 0
(-45 + √2052)/ (-27) £ у £ (-45 -√2052)/ (-27) (4)
Так как у Î Z , то условию (4) удовлетворяют только 0, 1, 2, 3 . Перебирая эти значения, получим, что уравнение в целых числах имеет решения (0; 0) и (1; 1) .
Ответ.
(0; 0) , (1; 1) .
Задача 14.
Решите уравнение 5х² - 2ху + 2у² - 2х – 2у + 1= 0.
Решение.
Рассмотрим данное уравнение как квадратное относительно х с коэффициентами, зависящими от у, 5х² - 2(у + 1)х + 2у² – 2у + 1= 0.
Найдём четверть дискриминанта D/4=(y+1)²-5(2y²-2y+1)=-(3y-2)² .
Отсюда следует, что уравнение имеет решение только тогда, когда -(3у – 2)² = 0 , отсюда следует у = ⅔, затем находим х = ⅓.
Ответ.
(⅓; ⅔).
Метод остатков.
Задача 15.
Решите в целых числах 3ª = 1 + у²
Решение.
Видно, что (0; 0) – решение данного уравнения. Докажем, что других решений нет.
Рассмотрим случаи:
1) х Î N, y Î N (5)
Если х Î N , то 3ª делится на 3 без остатка, а у² + 1 при делении на 3 даёт остаток либо 1 , либо 2 . Следовательно, равенство (5) при натуральных значениях х и у невозможно.
2)Если х – целое отрицательное число, y Î Z, тогда 0<3ª<1, а 1+у²³0 и равенство (5)также невозможно. Следовательно, (0; 0) – единственное решение.
Ответ.
Задача 16.
Докажите, что система уравнений
ì х² - у² = 7
î z² - 2y² = 1
не имеет решений в целых числах.
Решение.
Предположим, что система разрешена. Из второго уравнения z²=2у+1, т. е. z²– нечётноё число и z -нечётное, значит z=2m+1 . Тогда y²+2m²+2m , значит, у² - чётное числои у – чётное, y = 2n, n Î Z.
x²=8n³+7, т. е. х² - нечётное число и х - нечётное число, х=2k+1, k Î Z.
Подставим значения х и у в первое уравнение, получим 2(k² + k - 2n³) = 3, что невозможно, так как левая часть делится на 2 , а правая нет.
Значит, наше предположение неверно, т.е. система не имеет решений в целых числах.
Метод бесконечного спуска.
Решение уравнений методом бесконечного спуска проходит по следующей схеме: предположив, что уравнение имеет решения, мы строим некоторый бесконечный процесс, в то время, как по самому смыслу задачи этот процесс должен на чём–то кончаться.
Часто метод бесконечного спуска применяется в более простой форме. Предположив, что мы уже добрались до естественного конца, видим, что «остановиться» не можем.
Задача 17.
Решить в целых числах 29х + 13у + 56z = 17 (6)
Выразим неизвестное, коэффициент при котором наименьший, через остальные неизвестные.
у=(17-29х-56z)/13=(1-2x-4z)+(4-3x-4z)/13 (7)
Обозначим (4-3x-4z)/13 = t1 (8)
Из (7) следует, что t1 может принимать только целые значения. Из (8) имеем 13t1 + 3x + 4z = 14 (9)
Получим новое диофантово уравнение, но с меньшими, чем в (6) коэффициентами. Применим к (9) те же соображения: x=(4-13t1-4z)/3= =(1-4t1-z) + (1-t1-z)/3
(1-t1-z)/3 = t2 , t2 – целое, 3t2+t1+z = 1 (10)
В (10) коэффициент при z – неизвестном исходного уравнения равен 1 – это конечный пункт «спуска». Теперь последовательно выражаем z , x , y через t1 и t2 .
ì z = -t1 – 3t2 + 1
í x = 1 – 4t1 + t1 + 3t2 = 1 +t2 = -t1 + 4t2
î y = 1 + 6t1 – 8t2 + 4t1 + 12t2 – 4 + t1= 11t1 + 4t2 - 3
Итак,ì x = -3t1 + 4t2
í y = 11t1 + 4t2 - 3
î z = -t1 – 3t2 + 1
t1, t2 - любые целые числа – все целые решения уравнения (6)
Задача 18.
Решить в целых числах x³ - 3y³ - 9z³ = 0 (11)
Решение.
Видно, что левая часть уравнения (11) не поддаётся никаким преобразованиям. Поэтому исследуя характер целых чисел x³=3(y³-z³). Число x³ кратно 3 , значит и число х кратно 3 , т. е. х = 3х1 (12) Подставим (12) в (11) 27х1³-3у³-9z³=0, 9x1³-y³-3z³=0 (13)
y³=3(3x1³-z³). Тогда у³ кратно 3 , значит и у кратно 3 , т. е. у=3у1 (14). Подставим (14) в (13) 9х1³ -27у1³ - 3z³=0 . Из этого уравнения следует, что z³ кратно 3, а значит и z кратно 3 , т.е. z=3z1 .
Итак, оказалось, что числа, удовлетворяющие уравнению (11), кратны трём, и сколько раз мы не делили бы их на 3 , получаем числа, кратные трём. Единственное целое число, удовлетворяющее трём. Единственное целое число, удовлетворяющее этому условию, будет нуль, т. е. решение данного уравнения (0; 0; 0)
