Решение уравнений в целых числах
СОДЕРЖАНИЕ:
|
|
|
|
|
|
|
|
|
Р А З Р А Б О Т К А П Р О Г Р А М М |
|
|
|
ВВЕДЕНИЕ
Мой курсовой проект посвящен одному из наиболее интересных разделов теории чисел - решению уравнений в целых числах.
Решение в целых числах алгебраических уравнений с целыми коэффициентами более чем с одним неизвестным представляет собой одну из труднейших проблем теории чисел.
Проблема решения уравнений в целых числах решена до конца только для уравнений второй степени с двумя неизвестными. Отметим, что для уравнений любой степени с одним неизвестным она не представляет сколько-нибудь существенного интереса, так как эта задача может быть решена с помощью конечного числа проб. Для уравнений выше второй степени с двумя или более неизвестными весьма трудна не только задача нахождения всех решений в целых числах, но даже и более простая задача установления существования конечного или бесконечного множества таких решений.
В своем проекте я постаралась изложить некоторые основные результаты, полученные в теории; решения уравнений в целых числах. Теоремы, формулируемые в нем, снабжены доказательствами в тех случаях, когда эти доказательства достаточно просты.
1. УРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ
Рассмотрим уравнение первой степени с одним неизвестным
|
(1) |
Пусть коэффициенты уравнения и - целые числа. Ясно, что решение этого уравнения
будет целым числом только в том случае, когда нацело делится на Таким образом, уравнение (1) не всегда разрешимо в целых числах; так, например, из двух уравнений и первое имеет целое решение
С тем же обстоятельством мы встречаемся и в случае уравнений, степень которых выше первой: квадратное уравнение имеет целые решения в целых числах неразрешимо, так как его корни
Вопрос о нахождении целых корней уравнения n-ой степени с целыми коэффициентами
|
|
(2) |
решается легко. Действительно, пусть - целый корень этого уравнения. Тогда
Из последнего равенства видно, что делится без остатка; следовательно, каждый целый корень уравнения (2) является делителем свободного члена уравнения. Для нахождения целых решений уравнения надо выбрать те из делителей
только -1 является корнем. Следовательно это уравнение, имеет единственный целый корень
в целых числах неразрешимо.
Значительно больший интерес представляет решение в целых числах уравнении с многими неизвестными.
2. УРАВНЕНИЯ ПЕРВОЙ СТЕПЕНИ С ДВУМЯ НЕИЗВЕСТНЫМИ
Рассмотрим уравнение первой степени с двумя неизвестными
|
(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)
Перепишем полученные равенства в виде
Заменяя значение в первой строке этих равенств соответствующим значением из второй строки значение - выражением из третьей, строки и т. д., получим разложение в цепную дробь:
Выражения, получающиеся из цепной дроби при отбрасывании всех ее звеньев, начиная с некоторого звена, назовем подходящими дробями. Первая: подходящая дробь получится при отбрасывании всех звеньев, начиная с :
Вторая подходящая дробь
и т. д.
В силу способа образования подходящих дробей возникают очевидные неравенства:
Запишем k-ю подходящую дробь в виде
и найдем закон образования числителей и знаменателей подходящих дробей, Преобразуем первые подходящие дроби :
, ;
; ; ;
;
;
Отсюда получаем:
; .
Применяя индукцию, докажем, что соотношения того же вида
, (7).
выполняются для всех
Действительно, пусть равенства (7) выполняются для некоторого величины на перейдет в
Заменяя здесь на
Отсюда, так как
Таким образом, из выполнения равенств (7) для некоторого следует выполнение их для Но для равенства (7) - выполняется и, следовательно, их справедливость установлена для всех
Покажем теперь, что разность соседних подходящих дробей удовлетворяет соотношению
(8)
Действительно,
Пользуясь формулами (7), преобразуем числитель полученной дроби:
Выражение, стоящее в скобках, получается из исходного заменой на
Отсюда следует, что
Если разложение в цепную дробь имеет звеньев, то п-я подходящая дробь совпадает с получим
(9)
Вернемся теперь к решению уравнения
(10)
Перепишем соотношение (9) в виде
Приводя к общему знаменателю и отбрасывая его, получим
Умножим это соотношение на
Отсюда следует, что пара чисел
(11)
является решением уравнения (10) и согласно теореме все решения этого уравнения имеют вид
Полученный результат полностью решает вопрос о нахождении всех целочисленных решений уравнения первой степени с двумя неизвестными. Перейдем теперь к рассмотрению некоторых уравнений второй степени.
3. ПРИМЕРЫ УРАВНЕНИЙ ВТОРОЙ СТЕПЕНИ С ТРЕМЯ НЕИЗВЕСТНЫМИ
П р и м е р I. Рассмотрим уравнение второй степени с тремя неизвестными:
(12)
Геометрически решение этого уравнения в целых числах можно истолковать как нахождение всех пифагоровых треугольников, т. е. прямоугольных треугольников, у которых и катеты выражаются целыми числами.
Обозначим через общий наибольший делитель чисел и
и уравнение (12) примет вид
Отсюда следует, что делится на и, значит, кратно
Теперь уравнение (12) можно записать в виде
сокращая на , получим
.
Мы пришли к уравнению того же вида, что и исходное, причем теперь величины и не имеют общих делителей, кроме 1. Таким образом, при решении уравнения (12) можно ограничиться случаем, когда и взаимно просты. Итак, пусть и (например, ) будет нечетной. Перенося в правую часть уравнения (12), получим
. (13)
Обозначим через общий наибольший делитель выражений и Тогда
, (14)
где и взаимно просты.
Подставляя в (13) значения и , получим
.
Так как числа и не имеют общих делителей, то полученное равенство возможно только в том случае, когда и будут полными квадратами:
Но тогда
и
(15)
Найдем теперь и из равенств (14). Сложение этих равенств дает:
; . (16)
Вычитая второе из равенств (14) из первого, получим
(17)
В силу нечетности из (15) получаем, что и также нечетны. Более того,
и
следовало бы, что величины и имеют общий делитель связаны с взаимно простыми числами и равенствами
и в силу этого сами взаимно просты; , так как
Подставляя в равенства (15) - (17) , получим формулы:
(18)
дающие при нечетных взаимно простых и все свободные от общих делителей тройки целых положительных чисел (12). Простой подстановкой , и в уравнение (12) легко проверить, что при любых числа (18) удовлетворяют этому уравнению.
Для начальных значений и формулы (18) приводят к следующим часто встречающимся равенствам:
Как уже было сказано, формулы (18) дают только те решения уравнения
в которых числа и не имеют общих делителей. Все остальные целые положительные решения-этого уравнения получаются умножением решений, содержащихся в формулах (18), на произвольный общий множитель .
Тем же путем, каким мы получили все решения уравнения (12), могут быть получены и все решения других уравнений того же типа.
П р и м е р II. Найдем все решения уравнения
(19)
в целых положительных попарно взаимно простых числах .
Заметим, что если есть решение уравнения (19) и не имеют общего делителя, отличного от 1, то они и попарно взаимно просты. Действительно, если и кратны простому числу
следует, так как его левая часть - целое число, что кратно . То же самое будет, если и или и делятся на
Заметим, что должно быть числом нечетным для того, чтобы общий наибольший делитель был равен 1. Действительно, если четно, то левая часть уравнения (19) будет четным числом и, значит, z также будет четным. Но и будут тогда кратны 4. Отсюда следует, что должно делиться на 4, другими словами, что тоже должно быть четным числом. Значит, если четно, то все числа должны быть четными. Итак, в решении без общего отличного от 1 делителя должно быть нечетным. Отсюда уже следует, что и должно быть тоже нечетным. Перенося в правую часть, мы получаем:
Но и имеют общим наибольшим делителем 2. Действительно, пусть их общий наибольший делитель будет . Тогда
где и - целые числа. Складывая и вычитая эти равенства, мы будем иметь:
Но и нечетны и взаимно просты. Поэтому общий наибольший делитель и будет 2. Отсюда следует, что
Итак, или нечетно. Поэтому или
числа
и
взаимно просты, или взаимно просты числа
и
В первом случае из равенства
следует, что
а во втором случае из равенства
следует
где и целые, - нечетное число и и и находя , мы получаем или
или
где нечетно. Объединяя эти две формы представления решения мы получаем общую формулу
где нечетно. Но для того чтобы и были целыми числами, необходимо, чтобы было четным. Полагая и общие формулы, дающие все решения уравнения (19) в целых положительных без общего делителя, большего 1, числах:
, (19')
где и положительны, взаимно просты и нечетно. При этих условиях величины и выбираются произвольно, но так, чтобы было положительно. Формулы (19') действительно дают все решения в целых положительных и взаимно простых числах , так как, с одной стороны, мы доказали, что в этом случае должны представляться по формулам (19'), а с другой стороны, если мы зададим числа и , удовлетворяющие нашим условиям, то будут действительно взаимно просты и будут решением уравнения (19).
4. ОБЩИЙ СЛУЧАЙ УРАВНЕНИЯ ВТОРОЙ СТЕПЕНИ С ДВУМЯ НЕИЗВЕСТНЫМИ
В этом пункте мы докажем, что при любом целом положительном и иррациональном уравнение
(20)
всегда имеет нетривиальное решение, другими словами существует пара целых чисел , которая ему удовлетворяет. Прежде всего, укажем прием, позволяющий разложить в цепную дробь произвольное положительное число. Пусть - любое положительное число. Тогда всегда существует целое число, которое будет меньше или равно и больше целой части и обозначается и его целой частью называется дробной частью числа и обозначается непосредственно следует соотношение между ними, именно:
или
. (21)
Так как дробная часть числа есть разность между положительным числом и наибольшим целым числом, его не превосходящим, то дробная часть числа всегда меньше единицы и неотрицательна. Например, целая часть есть 5, а дробная его часть есть есть 1, а дробная часть равна равна 3, а дробная часть равна
Введенное нами определение целой части и дробной части положительного числа может быть использовано для разложения этого числа в цепную дробь. Положим:
Тогда
Так как всегда меньше единицы, то всегда больше единицы. Если бы было само целым числом, то его дробная часть равнялась бы нулю, было бы равно бесконечности и мы имели бы равенство . Отвлекаясь от этого частного случая, который исключается тем, что мы разлагаем в непрерывную дробь иррациональное число, мы можем утверждать, что - положительное число, большее единицы. С этим числом мы поступаем так же, как и с
Продолжая этот процесс, мы получаем ряд равенств:
(24)
Этот процесс последовательного образования целых чисел в случае, когда - рациональное число, - другими словами, когда и - целые положительные числа, - как нетрудно заметить, ничем не отличается по своим результатам от получения неполных частных с помощью алгоритма Евклида (см. формулу (6)). Он должен поэтому оборваться при рациональном. При иррациональном этот процесс должен быть бесконечным. Действительно, если бы при каком-нибудь было целым числом, то- отсюда следовало бы, что и т. д. и, наконец, рациональность Из формул (23), делая последовательные замены, исключая мы получим цепную дробь
(24)
которую, так как можно взять сколь угодно большим, можно записывать и в форме бесконечной цепной дроби
Т е о р е м а III. При любом целом положительном и иррациональном уравнение (20)
имеет нетривиальное решение,
Рассмотрим уравнение общего вида,
(25)
где - целое, - целое число, - иррациональное число. При это уравнение всегда имеет бесчисленное множество решений в целых числах и . При произвольных и такое уравнение может вообще не иметь решений.
П р и м е р. Покажем, что уравнение
(26)
вообще не разрешимо в целых числах и Заметим, прежде всего, что квадрат нечетного числа при Делений на 8 всегда дает в остатке 1. Действительно, так как всякое нечетное число а может быть записано в форме - целое число, то
(27)
где - целое число в силу того, что или , или должно быть четным числом. Далее, если - решение уравнения (27),. то и не могут быть числами одинаковой четности. Если бы и были одновременно четными или нечетными, то было бы четным числом и не могло быть равно 1. Если же нечетно, а четно, то при делении на давало бы в остатке 1, делилось бы на 4 и при делении на 4 давало бы в остатке 1. Это невозможно, так как при делении на 4 правая часть тривиально дает в остатке или четно, а нечетно, то делится на 4, на основании (26) может быть записано в форме
и, значит, при делении на 4 дает в остатке 1. Поэтому при делении на 4 должно опять давать в остатке 1, что, как мы уже видели, невозможно. Поэтому не существует целых чисел и
Не останавливаясь на вопросе, при каких условиях, наложенных на , уравнение (25) будет иметь решение, - вопросе трудном и разрешимом с помощью общей теории квадратических иррациональностей в алгебраической теории чисел, - мы остановимся на случае, когда уравнение (25) имеет нетривиальные решения. По-прежнему нетривиальным решением мы будем называть решение , если ; другими словами, пусть
(28)
Рассмотрим при том же уравнение
(29)
Это уравнение имеет бесчисленное множество решений в целых числах при и иррациональном будет:
Так как решение уравнения (29)
.
Равенство (28) в свою очередь может быть переписано в форме
Перемножая почленно эти два последних равенства, мы получаем
(30)
Но
и совершенно так же
.
Воспользовавшись этими двумя равенствами, мы можем переписать равенство (30) в форме
или в форме
.
Этим мы доказали, что если - решение уравнения (25), то этому уравнению будет удовлетворять и пара чисел
, (31)
где - любое решение уравнения (29). Таким образом, мы доказали, что если уравнение (25) имеет хотя бы одно решение, то оно имеет их бесчисленное множество.
Нельзя, конечно, утверждать, что формулами (31) даются все решения уравнения (25). В теории алгебраических чисел доказывается, что все решения уравнения (25) в целых числах можно получить, взяв некоторое конечное и определенное зависящее от и число решений этого уравнения и размножив их с помощью формул (31). Уравнение (25) при А отрицательном или равном квадрату целого числа может иметь не более конечного числа решений. Решение самых общих уравнений второй степени с двумя неизвестными в целых числах, уравнений вида
(32)
где числа А, В, С, D, Е и F - целые, сводится с помощью замен переменных к решению уравнений вида (25) с положительным или отрицательным А. Поэтому характер поведения решений, если они существуют, такой же, как и у уравнения типа (25). Подводя итог всему изложенному, мы можем теперь сказать, что уравнение второй степени с двумя неизвестными типа (32) может не иметь решений в целых числах, может иметь их только в конечном числе и, наконец, может иметь бесконечное множество таких решений, причем эти решения берутся тогда из конечного числа обобщенных геометрических прогрессий, даваемых формулами (31).
ПРОГРАММА №1 (УРАВНЕНИЯ С ОДНИМ НЕИЗВЕСТНЫМ)
|
n |
|
a |
|
c |
|
c/j=(c div j) |
|
d[j]:=-j |
|
d[j]:=j |
|
w:=w*d[j]; x:=x + w*a[i]; |
|
x + c=0 |
|
d[j] |
|
ВЫХОД |
n – степень многочлена;
a – коэффициент при x;
c – свободный член уравнения;
d – делитель свободного члена;
w – вспомогательная переменная
для возведения d в степень
аргумента;
x – сумма возведенных d
в степень аргумента
умноженных на a
program matan_1;
uses crt;
var i,n,c,j,k,x,w,q,p:integer; a,d:array[1..100] of integer;
BEGIN
writeln ('введите степень многочлена');
readln (n);
for i:=1 to n+1 do begin
if i=n+1 then begin writeln ('введите свободный коэффициент');
read (c);end;
if i<>n+1 then begin Writeln ('введите коэффициент при x^',n-i+1);
readln (a[i]); end;end;
w:=1;
for j:=1 to c do begin
if c/j= (c div j) then begin d[j]:=-j;
k:=n;
for i:=1 to n do begin
for q:=1 to k do
w:=w*d[j];
x:=x+w*a[i];
k:=k-1;w:=1;end;
if x+c=0 then begin p:=p+1;
writeln('целый корень уравнения =',d[j]);end;
end; x:=0;end;
for j:=1 to c do begin
if c/j= (c div j) then begin d[j]:=j;
k:=n;
for i:=1 to n do begin
for q:=1 to k do
w:=w*d[j];
x:=x+w*a[i];
k:=k-1;w:=1;end;
if x+c=0 then begin p:=p+1;
writeln('целый корень уравнения =',d[j]);end;
end; x:=0;end;
if p=0 then writeln ('данное уравнение в целых числах неразрешимо');
readln;readln;
END.
ПРОГРАММА №2 (Уравнения первой степени с двумя неизвестными)
program matan_2;
var p,q,t,n,i,k,x,y,w,r,s,d:integer; a,b,c:array[1..1000]of integer;
BEGIN
writeln('вв. при х'); readln(p);
writeln('вв. при y'); readln(q);
writeln('вв. c'); readln(t);
if p<0 then x:=-p else x:=p; if q<0 then y:=-q else y:=q;
n:=0;n:=0;k:=1;
for i:=1 to 10 do begin
if k<>0 then begin n:=n+1;
for i:=n to n do begin
a[i]:=x; b[i]:=y;
c[i]:=x div y;
x:=x-c[i]*y;
k:=k+1;n:=0;r:=r+1;
if (x<y) and (x<>1) then begin w:=y; y:=x; x:=w;end else k:=0;
end;
end;end;
x:=p;y:=q;
for i:=1 to r do begin
a[i]:=x; b[i]:=y;
c[i]:=x div y;
x:=x-c[i]*y;a[i]:=1;b[i]:=1;
if (x<y) and (x<>1) then begin w:=y; y:=x; x:=w;end;
end;
for i:=r downto 1 do begin
b[r]:=0;
b[i]:=c[i]*b[i]+a[i];
if i>1 then b[i-1]:=b[i];
if i>2 then a[i-2]:=b[i-1];
end;
if (p*b[1]+q*a[1]+t)=0 then begin
writeln('корни уравнения x=',b[1],'y=',a[1]);
writeln ('все его решения будут содержаться в прогрессиях');
writeln('x=',b[1],'+',q,'*','t');
writeln('y=',a[1],'+',p,'*','t');end;
readln;
END.
ЗАКЛЮЧЕНИЕ
Сравнивая поведение и характер решений уравнений второй степени с двумя неизвестными в целых числах с поведением решений уравнений первой степени, мы можем установить одно весьма существенное обстоятельство. Именно, если решения уравнения первой степени, когда они существуют, образуют арифметические прогрессии, то решения уравнения второй степени, когда их имеется бесконечно много, берутся из конечного числа обобщенных геометрических прогрессий. Другими словами, в случае второй степени пары целых чисел, которые могут быть решениями уравнения, встречаются значительно реже, чем пары целых чисел, которые могут быть решениями уравнения первой степени. Это обстоятельство не случайно. Оказывается, что уравнения с двумя неизвестными степени выше второй, вообще говоря, могут иметь только конечное число решений. Исключения из этого правила крайне редки.
СПИСОК ЛИТЕРАТУРЫ:
1. Гельфонд А.О. Решение уравнений в целых числах. -4-е изд. –
М.: Наука, 1983. – 64 с. – (Популярные лекции по математике).