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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: материалы конференции. Предмет: Математика. Добавлен: 13.03.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


Введение

Линейным диофантовым уравнением называется уравнение с нескол
ькими неизвестными вида а1х1 + ... + аnхn = с, где (известные) коэффициенты а1,..., аn и с -- целые числа, а неизвестные х1, …xn также являются целыми числами. К решению подобных уравнений сводятся разнообразные текстовые задачи, в которых неизвестные величины выражают количество предметов того или иного рода и потому являются натуральными (или неотрицательными целыми) числами.
Теория решения подобных уравнений является классическим разделом элементарной математики. В ней не приходится писать сложные и громоздкие формулы, а необходимо проводить аккурат-ные рассуждения, базирующиеся на определенных понятиях теории чисел и связанные в стройную логическую конструкцию. В рамках этой теории можно дать исчерпывающее решение рассматриваемого класса задач с четко описанным алгоритмом получения ответа.
Конкретные задачи такого рода были решены еще в Древнем Вавилоне около 4 тысяч лет тому назад. Древнегреческий мысли-тель Диофант, который жил около 2 тысяч лет тому назад, в своей книге «Арифметика» решил большое число таких и более сложных уравнений в целых числах и в сущности описал общие методы их решения.
В школьных учебниках эта тема затрагивается вскользь, да и то лишь в 8-м классе, в то время как задачи, где требуется решать уравнения описанного типа, относительно часто предлагаются на вступительных экзаменах.
В настоящей брошюре на примерах решения конкретных экза-менационных задач МГУ им. М.И. Ломоносова мы расскажем об основных результатах и методах теории линейных диофантовых уравнений. Поскольку, за редким исключением, на экзаменах предлагаются уравнения с двумя неизвестными, мы ограничим-ся этим случаем, то есть будем рассматривать уравнения вида
ах + Ьу = с. Это позволит упростить теоретические рассмотрения, не ограничивая, в сущности, общности описываемых методов (мы продемонстрируем это в задаче 13 на примере конкретного уравне-ния вида ах + Ьу + сz = d.
Следует отметить, что каждая конкретная задача в целых числах может решаться с помощью раз-ных методов. Целью нашей работы является демонстрация возможностей теории линейных диофан-товых уравнений.
Однородные уравнения
Прежде всего, мы рассмотрим однородные линейные уравнения, то есть уравнения вида
ах + by = 0, все члены которых являются одночленами первой степени.
Если коэффициенты а и Ь имеют общий делитель d, то обе части уравнения ах + by = 0 можно сократить на d. Поэтому, не нарушая общности, можно считать, что числа а и b -- взаимно про-стые.
Рассмотрим, например, уравнение 80х + 126y = 0.
Разложим коэффициенты а = 80 и b=126 на простые множители: а = 24 * 5, b = 2 * З2 * 7. Наибольший общий делитель чисел а = 80 и b = 126 равен 2, и после сокращения на 2 мы получим уравнение
40x + 63y = 0, (1)
в котором коэффициенты а = 40 = 23 * 5 и b = 63 = З2 * 7 являются взаимно простыми целыми чис-лами.
Разложение на простые множители коэффициентов уравнения, которое мы использовали для сокраще-ния на наибольший общий делитель, можно использовать и для завершения решения. Пере-пишем уравнение (1) в виде:
23*5*х = -32*7*у.(2)
Левая часть уравнения (2) делится на 23 * 5. Поэтому и правая часть, которая равна левой, должна делиться на 23 * 5, а это возможно тогда и только тогда, когда неизвестная у делится на 23 * 5:
у = 23 * 5 * u = 40u,(3)
где и -- некоторое целое число.
Аналогичные рассуждения применимы и к правой части урав-нения (2). Правая часть делится на
З2 * 7. Поэтому и левая часть, которая равна правой, должна делиться на З2 * 7, а это возможно тогда и только тогда, когда неизвестная х делится на З2 * 7:
x = З 2 * 7 * v = 63v,(4)
где v -- некоторое целое число.
Равенства (3) и (4) фактически вводят новые целочисленные неизвестные u, v вместо основных неизвестных х, у. Для новых неизвестных уравнение (2) примет вид: u = -v. Множество решений этого уравнения состоит из бесконечного количества пар:
(-3; 3), (-2; 2), (-1; 1), (0; 0), (1; -1), (2; -2), (3; -3), ...
Иначе говоря, этому уравнению удовлетворяют все пары (-u; u) вида (-n; n), где n -- произволь-ное целое число, и только они. Пе-ременная n в этих формулах является своеобразным «номером» решения.
Возвращаясь к основным неизвестным х и у, мы получим, что множество решений уравнения (2) можно записать в виде: хп = 63n, у = -40n, где n -- произвольное целое число.
Как ясно из приведенного решения (2), оно совершенно не привя-зано к точным значениям коэффициен-тов а и b и не изменится, если вместо чисел а = 40, b = 63 рассмотреть произвольные взаимно про-стые числа. Таким образом, справедлива следующая теорема, которая дает полное решение диофантовых уравнений вида ах + by = 0.
Теорема 1. Если числа а и b -- взаимно простые, то уравне-ние ах + by = 0 имеет бесконечно много решений в целых чис-лах, которые находятся во взаимно однозначном соответствии с множест-вом целых чисел Z (то есть могут быть занумерованы целыми числами) и описываются формулой: хп = bn, yn = -an, где n Z -- «номер» решения.
Эта теорема часто встречается при решении разнообразных за-дач на целые числа, и мы рекомен-дуем абитуриентам запомнить ее формулировку.
В качестве простого примера применения теоремы 1 рассмотрим следующую задачу.
Задача 1. Найти все целочисленные решения уравне-ния
х2 + 5y2 + 34z2 + 2ху - 10xz - 22уz - 0.
Решение. Рассмотрим уравнение
х2 + 5у2 + 34z2 + 2ху - 10xz - 22yz = 0
как квадратное уравнение относительно одной неизвестной х:
х2 + 2х(у - 5г) + by2 + 34z2 - 22yz = 0.
Тогда
= (y-5z)2-(5y2+34z2-22yz)=-(2y-3z)2.
Если это уравнение имеет решение, то дискриминант должен быть неотрицательным, что воз-можно только в случае - 3z = 0. Тогда дискриминант равен нулю, и уравнение имеет единствен-ное решение х = 5z- у.
Итак, исходное уравнение равносильно системе
Общее решение первого уравнения в целых числах дается форму-лами у = Зn, z = 2n, где n Z. Из второго уравнения теперь можно найти х (причем х автоматически будет целым числом): х = In.
Таким образом, исходное уравнение имеет бесконечно много целочисленных решений, которые могут быть описаны формулой (х; у; z) -- (7n; Зn; 2n), n Z.
Ответ: (х; у, z) = (7n; Зn; 2n), n e Z.
Общие линейные уравнения
В этом разделе мы будем рассматривать диофантовы уравнения вида ах + by = с.
Прежде всего отметим, что, вообще говоря, такое уравнение может и не иметь целочисленных реше-ний.
Действительно, допустим, что уравнение ах + by = с имеет реше-ние. Если коэффициенты а и b имеют общий делитель d > 1, то число ах + by, которое стоит в левой части, можно без остатка разде-лить на d. Поэтому и правую часть уравнения, то есть свободный член с, можно без остатка разделить на d. Иначе говоря, справедлива следующая теорема.
Теорема 2. Если наибольший общий делитель d коэффициентов а и b больше 1, а свободный член с не делится на d, то уравнение ах + by = с не имеет решений в целых числах.
Это простое утверждение часто используется, например, для доказательства иррациональности чисел, записанных с помощью радикалов.
Задача 2. Дока-зать, что число не является рациональным числом.
Решение. Допустим противное, что -- число рациональное.
Тогда существуют натуральные т, п такие, что .
Избавляясь от радикала и дроби, получим:
2n3 = т3(5)
Разложим числа т и n на простые множители (мы явно указы-ваем только простой множитель 2):
т = 2х*...
n = 2y*...
где х, у -- неотрицательные целые числа (отсутствие простого мно-жителя 2 в разложении озна-чает, что соответствующий показатель степени равен нулю).
Тогда равенство (5) примет вид:
23y + 1*... = 2*...
В силу единственности разложения натурального числа на про-стые множители
Зу + 1 = 3x 3(х - у) = 1.
Последнее уравнение является линейным диофантовым уравнени-ем вида ах + Ьу = с, причем коэффи-циенты а = 3, b = -3 делятся на 3, в то время как свободный член с = 1 -- нет. Значит, это уравнение не имеет целочисленных решений, что означает ложность исходного предположения о рациональности числа .
.Будем теперь рассматривать только такие уравнения вида ах + by = с, в которых свободный член с делится на d = НОД(а; b). После деления обеих частей уравнения на d мы получим уравнение того же вида, но уже со взаимно простыми коэффициентами при неизвестных. Только такие уравнения мы будем рассматривать ниже в этом разделе.
В этом случае со стороны теоремы 2 нет препятствий к тому, что-бы уравнение имело целочислен-ные решения. Но отсюда, конечно, не следует, что решения обязаны быть.
На самом деле ответ на этот вопрос положительный.
Теорема 3. Любое уравнение ах + by = с, где НОД(а; b) = 1, имеет хотя бы одно решение в целых числах.
Доказательство. Уравнение ах + by = с имеет решение тогда и только тогда, когда число с входит в область значений М функции f(x; у) = ах + by от двух целочисленных аргументов х, у. Поэтому наша теорема фактически утверждает, что М = Z. Именно этот факт мы и будем доказывать.
Прежде всего отметим, что множество М содержит бесконечно мно-го чисел, например, 0= f (0; 0), а = f (1; 0), -а = f (-1; 0), а + b = f (1; 1) и т.д. Поскольку f(-x; -у) = -f(x; у), это множество имеет вид:
{..., -и2, -п1, 0, n1, n2,...},
где n1 < n2 < ... -- натуральные числа.
Рассмотрим наименьшее положительное число из М, то есть n1 и докажем, что оно равно 1. Для этого разделим число |а| на n1 с остатком, то есть найдем такие целые числа q (неполное частное) и r (остаток), что |а| = n1q + r, причем 0 r п . Поскольку число n1 принадлежит множеству М, для некоторых целых х0 и у0 верно равенство n] = ах0 + bу0. Кроме того,
| а | = sgn (a) * а,
где sgn(а) = +1, если а > О, и sgn(а) = -1, если а < 0.
Тогда
г = | а | - n1g = sgn (а) *а - (ах0 + by0) -q = ax + by,
где x: = sgn(а) - x0q, у = -y0q -- некоторые целые числа. Поэтому неотрицательное целое число г также принадлежит множеству М. Если бы число г было положительным, то условие 0 < r < n , кото-рому удовлетворяет г как остаток от деления на л,, означало бы, что в множестве М есть положительное число, меньшее, чем n1 чего быть не может. Значит, r = 0, то есть | а| (а вместе с ним и а) делится без остатка на n1.
Аналогичные рассуждения показывают, что и b делится без остатка на n1. Следовательно, n1 -- общий делитель чисел а и b, a поскольку эти числа взаимно простые, число n1 равно 1.
Функция f(x; y) = ax + by обладает свойством: f(kx; ky) = k * f(x; у). Поэтому если некоторое число с М, то и число kc M. Как мы установили, 1 М. Значит, и любое целое число k входит в М, то есть М = Z. Это и означает справедливость нашей теоремы.
Имея в виду более сложные задачи, мы в качестве простого следствия из доказанной теоремы 3 получим еще одну важную теорему.
Теорема 4. Если числа а и b -- целые, то множество значений функции f(x; y) = ax + by от двух целочис-ленных аргументов х и у совпадает с множеством чисел, кратных d = НОД(а; b), то есть с множеством {..., --2d, --d, 0, d, 2d, ...}.
Доказательство. Так как d = НОД(а; b), числа а и b можно запи-сать в виде: а = da', b = db', причем числа а', b' -- взаимно простые. Тогда f(x; у) = d *(а'х + bу). В силу теоремы 3, любое целое число n можно представить в виде а'х + b'у. Поэтому множество чисел, которые могут быть записаны в виде ах + by, есть {..., -2d, -d, 0, d, 2d, ...}.
Приведенное доказательство теоремы 3 дает удобный метод нахождения частного (то есть конкрет-ного) решения при решении конкретных уравнений вида ах + by = с (если а и b взаимно простые целые числа):
1) нужно образовать две последовательности чисел:
-..., -2а, -а, О, а, 2а, ... и -..., -2b, -b, О, b, 2b, ...
(обычно достаточно выписать по несколько членов в обе стороны), и расположить их друг под другом так, чтобы положительные члены одной стояли под отрицательными членами другой;
2) затем в уме находить всевозможные суммы пар членов этих последовательностей, пока не най-дем пару, дающую в сумме с.
Рассмотрим, например, уравнение - bу =1. Выпишем ряды чисел, кратных коэффициентам а = 2 и b = -5:
Из этой таблицы ясно, что второе число из первой строки (то есть -4), которое соответствует х = -2, и третье число из второй строки (то есть 5), которое соответствует у = -1, и дают в сумме 1. Та-ким образом, уравнение 2х- bу = 1 имеет частное решение х0 = -2, у0 = -1. Конечно, эту пару можно найти и проще, просто подставляя в исходное урав-нение в уме небольшие числа с тем, чтобы полу-чить верное равенст-во. Для несложных уравнений обычно поступают именно так.
В ряде случаев приходится выписывать довольно много (несколь-ко десятков) членов последовательно-стей ах и by. Тогда, конечно, описанный прием не очень удобен, так как требует больших затрат времени. В этой ситуации обычно рекомендуют использовать ал-горитм Евклида для нахождения наибольшего общего делителя коэффициентов а и b (само доказательство замечатель-ной теоремы 3 также может быть получено с помощью алгоритма Евклида). Мы продемонст-рируем этот алгоритм при решении задачи 6.


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.