Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

4. Непрерывные дроби. Диофантовы уравнения

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

Например, в применении к числам 840 и 611 алгорифм Евклида дает ряд равенств

840 = 1*611 + 229, 611 = 2*229 + 153, 229 = 1*153 + 76, 153 = 2*76 + 1,

которые, между прочим, показывают, что (840, 611) = 1. Но из этих равенств, с другой стороны, получаются следующие:


Комбинируя последние равенства, мы приходим к следующему разложению числа


Выражение вида


где все числа а целые положительные, называется непрерывной дробью. Алгорифм Евклида дает метод для представления всякого рационального числа в виде такой непрерывной дроби.

Упражнение. Разложите в непрерывные дроби рациональные числа


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

ах + by = с, (8)

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

Прежде всего этот алгорифм позволит нам определить d = (a, b); затем, как мы знаем, при надлежащем выборе целых чисел k и l выполняется равенство

ak + bl = d. (9)

Итак, уравнение (8) имеет частное решение х = k, у = l в том случае, если с = d. Вообще, если с есть кратное d:

с = d*q,

то из равенства (9) мы выводим

a(kq) + b(lq) = dq = с,

так что в этом случае уравнение (8) имеет частное решение х = х* = kq, у = у* = lq. Обратно, если уравнение (8) имеет при данном с хоть одно решение х, у, то с должно быть кратным d = (а, b): действительно, d делит и а и b, следовательно, должно делить с. Мы доказали, таким образом, что уравнение (8) имеет (хоть одно) решение в том и только в том случае, если с кратно (а, b).

Посмотрим теперь, как, зная одно решение х = х*, у = у* уравнения (8), определить все прочие решения. Пусть х = х', у = у' есть какое-либо другое решение; тогда х = х' - х*, у = у' - у* есть решение "однородного" уравнения

ах + by = 0. (10)

Действительно, из равенств

ах' + by' = с и аx* + by* = с

посредством вычитания получаем:

а(х' - х*) + b(у' - у*) = 0.

Обращаясь теперь к уравнению (10), мы видим, что общее его решение имеет вид где r - произвольное целое число. (Предоставляем доказательство читателю в качестве упражнения. Указание. Разделите на (а, b) и воспользуйтесь упражнением на стр. 72.) Затем окончательно будем иметь общее решение уравнения (8):


Подведем итоги. Линейное диофантово уравнение ах + by = с, где a, b и с - целые числа, имеет целые решения в том и только в том случае, если с кратно (а, b). В этом случае частное решение х = x*, у = у* может быть найдено посредством алгорифма Евклида, а общее имеет вид:


где r - произвольное целое число.

Примеры. Уравнение 3х + 6у = 22 не имеет целых решений, так как (3, 6) = 3 не делит 22.

Уравнение 7х + 11y = 13 имеет частное решение х = -39, у = 26, которое находится с помощью следующих вычислений:

11 = 1*7 + 4, 7 = 1*4 + 3, 4 = 1*3 + 1, (7, 11) = 1, 1 = 4 - 3 = 4 - (7 - 4) = 2*4 - 7 = 2(11 - 7) - 7 = 2*11 - 3*7.

Отсюда следует

7*(-3)+ 11*(2) = 1,
7*(-39) + 11*(26) = 13.

Остальные решения даются формулами:

х = - 39 + 11r,
у = 26 - 7r,

где r - произвольное целое число.

Упражнение. Решите диофантовы уравнения:

a) 3x - 4у = 29;

b) 11x + 12y = 58;

c) 153x - 34y = 51.

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Зачем математики ищут простые числа с миллионами знаков?

Задача построения новых оснований математики - унивалентные основания

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru