Общее линейное уравнение с n неизвестными

КУРСОВАЯ РАБОТА

по дисциплине «Фундаментальная и компьютерная алгебра»

Решение систем линейных уравнений в целых числах

ОГУ 38.04.08. 3515. 022 00

Руководитель

доцент

_______ Носов В.В.

«__» _____________ 2016 г.

Студент группы 15МКН(ба)АПКМ

_______ Роговая Е. О.

«__» _____________ 2016 г.

Оренбург 2016

СОДЕРЖАНИЕ:

Введение

Уравнение с одним неизвестным.

Уравнения с двумя неизвестными.

Обобщенное уравнение с n неизвестными.

Системы двух уравнений с двумя неизвестными.

5.Системы трёх уравнений с тремя неизвестными.

Заключение.

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

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

(1) Пусть коэффициенты уравнения a и b - целые числа, тогда

Решение этого уравнения будет целым числом тогда и только тогда, когда

. Таким образом, уравнение (1) не всегда разрешимо в целых числах; так, например, из двух уравнений

первое имеет целое решение, а второе в целых числах неразрешимо. 2. Уравнения с двумя неизвестными Рассмотрим уравнение первой степени с двумя неизвестными

(2), где

- целые числа, отличные от нуля, а

- произвольное целое. Будем считать, что коэффициенты

не имеют общих делителей, кроме единицы. Действительно, если НОД

, то справедливы равенства

; уравнение (2) принимает вид

и может иметь целые решения только в том случае, когда . Следовательно все коэффициенты уравнения (2) должны делиться нацело на . Сокращая (2) на , придем к уравнению

, где

Рассмотрим сначала случай, когда . Уравнение (2) примет вид:

(2')

Решая это уравнение относительно , получим

Очевидно, что будет принимать целые значения если делится на . Но всякое целое , кратное , можно записать в виде

где принимает произвольные целые значения . Подставим это значение в предыдущее уравнение, тогда

и мы получаем формулы, содержащие все целые решения уравнения (2'):

Перейдем теперь к случаю .

Покажем, прежде всего, что для нахождения всех целых решений уравнения (2) достаточно найти какое-нибудь одно его решение, т. е. найти такие целые числа , , для которых

Теорема. Пусть а и b взаимно просты и - какое-нибудь решение уравнения

(2)

Тогда формулы

(3)

при дают все решения уравнения (2).

Доказательство. Пусть x,y - произвольное решение уравнения (2). Тогда из равенств

получаем

;

Так как - целое число и числа и взаимно просты, то должно нацело делиться на , т. е. имеет вид

где - целое. Но тогда

и получаем

Таким образом доказано, что всякое решение x, y имеет вид (3). Остается еще проверить, что всякая пара чисел x, y, получаемая по формулам (3) при целом , будет решением уравнения(2).Чтобы провести такую проверку, подставим величины , в левую часть уравнения (2):

но так как - решение, то и, следовательно, , т.е. - решение уравнения (2), что и требовалось доказать.

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

, .

Критерии:

1) При взаимно простых коэффициентах и при b=1 диофантово уравнение имеет решение в целых числах.

2) Если , то существуют такие целые числа x и y, что имеет место равенство

3) Если в уравнении (4) , то уравнение (4) имеет, по крайней мере, одно целое решение.

4) Если в уравнении (5) и c не делится на d, то уравнение целых решений не имеет.

5)Если в уравнении (6) и , то оно равносильно уравнению (6’), в котором .

6) Если пара целых чисел , удовлетворяет уравнению (6), где - целые числа, отличные от нуля и , то

, , (7)

где t – произвольное целое число, является общим решением этого уравнения в целых числах.

Общее линейное уравнение с n неизвестными

Теорема. При взаимно простых коэффициентах диофантово уравнение имеет решение в целых числах.

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

Обозначим через M множество тех положительных чисел b, для которых уравнение имеет решение в целых числах. M, очевидно, не пусто, так как при заданных можно подобрать целые значения , такие, чтобы было положительным числом.

В множестве M существует наименьшее число (M – подмножество натуральных чисел), которое мы обозначим через d Обозначим через - целые числа, такие, что

Пусть , где ; тогда

Мы подобрали целые значения: , такие, что , но , а d - наименьшее положительное число в M, т. е. r не может быть положительным, r=0, . Аналогично получаем: .

Мы видим, что d – общий делитель чисел , следовательно, поскольку )=1, , то уравнение разрешимо в целых числах.

Теорема. Пусть d - наибольший общий делитель коэффициентов . Диофантово уравнение имеет решение тогда и только тогда, когда . Число решений такого уравнения равно либо нулю, либо бесконечности.

Докажем последовательно все три утверждения теоремы.

1) Пусть . Для уравнения , где , существуют целые числа: удовлетворяющие ему, т.е. . Тогда т. е. - решение уравнения.

2) Пусть теперь d не делит b. Тогда левая часть уравнения при любых целых делится на d, а правая на d не делится, так что равенство при целых значениях невозможно.

3) Если - упорядоченная последовательность чисел, удовлетворяющих уравнению, то, например, при также удовлетворяют этому уравнению и, таким образом, либо совсем не будет решений, либо их будет бесконечное множество.

Если хоть одна пара коэффициентов взаимно простая, то d= 1, и уравнение имеет бесчисленное множество решений.