Решение уравнений в целых числах
СОДЕРЖАНИЕ:
|
|
|
|
|
|
|
|
|
Р А З Р А Б О Т К А П Р О Г Р А М М |
|
|
|
ВВЕДЕНИЕ
Мой курсовой проект посвящен одному из наиболее интересных разделов теории чисел - решению уравнений в целых числах.
Решение в целых числах алгебраических уравнений с целыми коэффициентами более чем с одним неизвестным представляет собой одну из труднейших проблем теории чисел.
Проблема решения уравнений в целых числах решена до конца только для уравнений второй степени с двумя неизвестными. Отметим, что для уравнений любой степени с одним неизвестным она не представляет сколько-нибудь существенного интереса, так как эта задача может быть решена с помощью конечного числа проб. Для уравнений выше второй степени с двумя или более неизвестными весьма трудна не только задача нахождения всех решений в целых числах, но даже и более простая задача установления существования конечного или бесконечного множества таких решений.
В своем проекте я постаралась изложить некоторые основные результаты, полученные в теории; решения уравнений в целых числах. Теоремы, формулируемые в нем, снабжены доказательствами в тех случаях, когда эти доказательства достаточно просты.
1. УРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ
Рассмотрим уравнение первой степени с одним неизвестным
-

(1)
Пусть
коэффициенты
уравнения
и
- целые числа.
Ясно, что решение
этого уравнения
будет целым
числом только
в том случае,
когда
нацело делится
на
.
Таким
образом, уравнение
(1) не всегда
разрешимо в
целых числах;
так, например,
из двух уравнений
и
первое имеет
целое решение
,
а второе в целых
числах неразрешимо.
С тем же
обстоятельством
мы встречаемся
и в случае уравнений,
степень которых
выше первой:
квадратное
уравнение
имеет целые
решения
,
;
уравнение
в целых числах
неразрешимо,
так как его
корни
,иррациональны.
Вопрос о нахождении целых корней уравнения n-ой степени с целыми коэффициентами
-

(2)
решается
легко. Действительно,
пусть
- целый корень
этого уравнения.
Тогда
-
,
.
Из последнего
равенства
видно, что
делится
без остатка;
следовательно,
каждый целый
корень уравнения
(2) является
делителем
свободного
члена уравнения.
Для нахождения
целых решений
уравнения надо
выбрать те из
делителей
,
которые при
подстановке
в уравнение
обращают его
в тождество.
Так, например,
из чисел 1, -1, 2 и
-2, представляющих
собой все делители
свободного
члена уравнения
-
,
только -1
является корнем.
Следовательно
это уравнение,
имеет единственный
целый корень
.
Тем же методом
легко показать,
что уравнение
в целых числах неразрешимо.
Значительно больший интерес представляет решение в целых числах уравнении с многими неизвестными.
2. УРАВНЕНИЯ ПЕРВОЙ СТЕПЕНИ С ДВУМЯ НЕИЗВЕСТНЫМИ
Рассмотрим уравнение первой степени с двумя неизвестными
-
,(3)
где
и
- целые числа,
отличные от
нуля, а
- произвольное
целое. Будем
считать, что
коэффициенты
и
не имеют общих
делителей,
кроме единицы.
Действительно,
если общий
наибольший
делитель этих
коэффициентов
отличен от
единицы, то
справедливы
равенства
,
;
уравнение (3)
принимает вид
и может
иметь целые
решения только
в том случае,
когда
делится на
.
Таким образом,
в случае
- все коэффициенты
уравнения (3)
должны делиться
нацело на
,
и, сокращая (3)
на
,
придем к уравнению
-
,
коэффициенты
которого
и
взаимно просты.
Рассмотрим
сначала случай,
когда
.
Уравнение (3)
перепишется
так:
-
.(3')
Решая это
уравнение
относительно
,
получим
-
.
Ясно, что
будет принимать
целые значения
в том и только
в том случае,
когда
делится
на
без остатка.
Но всякое целое
,
кратное
,
можно записать
в виде
-
,
где
принимает
произвольные
целые значения
.
Подставим это
значение
в предыдущее
уравнение,
тогда
-
,
и мы получаем формулы, содержащие все целые решения уравнения (3'):
-
,
.
Перейдем
теперь к случаю
.
Покажем,
прежде всего,
что для нахождения
всех целых
решений уравнения
(3) достаточно
найти какое-нибудь
одно его решение,
т. е. найти такие
целые числа
,
,
для которых
-
,
Т е о р е м
а I.
Пусть а и b
взаимно просты
и
-
какое-нибудь
решение уравнения
-
,(3)
Тогда формулы
-
,

(4)
при
дают все решения
уравнения (3).
Д о к а з а
т е л ь с т в о.
Пусть
- произвольное
решение уравнения
(3). Тогда из равенств
-
и

получаем
-
;
.
Так как
-
целое
число и числа
и
взаимно просты,
то
должно нацело
делиться на
,
т. е.
имеет вид
-
,
где
- целое. Но тогда
-
,
и получаем
-
,
.
Таким образом
доказано, что
всякое решение
имеет вид (4).
Остается еще
проверить, что
всякая пара
чисел
,
получаемая
по формулам
(4) при целом
,
будет
решением уравнения
(3).
Чтобы
провести та
кую проверку,
подставим
величины
,
в левую часть
уравнения (3):
-
,
но так как
-решение,
то
и, следовательно,
,
т.е.
- решение уравнения
(3), чем теорема
полностью
доказана.
Итак, если
известно одно
решение уравнения
,
то все остальные
решения найдутся
из арифметических
прогрессий,
общие члены
которых имеют
вид:
,
.
3аметим,
что в случае,
когда
,
найденные
раньше формулы
решений
-
,

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

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

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

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

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


Величины
,
,…
называются
неполными
частными.
Приведенный
выше процесс
образования
неполных частных
называется
алгоритмом
Евклида. Остатки
от деления
,
,…удовлетворяют
неравенствам
-
,(5)
т. е. образуют ряд убывающих неотрицательных чисел.
Так как
количество
неотрицательных
целых чисел,
не превосходящих
b,
не может
быть бесконечным,
то на некотором
шаге процесс
образования
неполных частных
оборвется из-за
обращения в
ноль очередного
остатка r.
Пусть
- последний
отличный от
нуля остаток
в ряде (5); тогда
и алгоритм
Евклида для
чисел a
и b
примет вид
(6)
Перепишем полученные равенства в виде

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



