Линейные диофантовы уравнения

НЕКОТОРЫЕ ДИОФАНТОВЫУРАВНЕНИЯ

 

 

Курсовая работа

студента III курса ФМФ

Матаева Евгения Викторовича

Научный руководитель:

к.ф.-м.н. Валицкас А.И.

 

Оценка: ____________

 

Тобольск – 2011

Содержание

Введение……………………………………………………………………........3

§ 1. Линейные диофантовы уравнения…………………………………..4

§ 2. Диофантово уравнение x² – y² = a………………………………….....9

§ 3. Диофантово уравнение x² + y² = a…………………………………... 12

§ 4. Уравнение х²+ х + 1 = 3×у²…………………………………………….. 16

§ 5. Пифагоровы тройки………………………………………………….. 19

§ 6. Великая теорема Ферма………………………………………………23

Заключение……………………………………………………………….….....29

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

 

ВВЕДЕНИЕ

Диофантово уравнение – это уравнение вида P(x₁, …, x_n) = 0, где левая часть представляет собой многочлен от переменных x₁, …, x_n с целыми коэффициентами. Любой упорядоченный набор (u₁; …; u_n) целых чисел со свойством P(u₁, …, u_n) = 0 называется (частным) решением диофантова уравнения P(x₁, …, x_n) = 0. Решить диофантово уравнение – значит найти все его решения, т.е. общее решение этого уравнения.

Нашей целью будет научиться находить решения некоторых диофантовых уравнений, если эти решения имеется.

Для этого, необходимо ответить на следующие вопросы:

а. Всегда ли диофантово уравнение имеет решение, найти условия существования решения.

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

Примеры: 1. Диофантово уравнение 5×x – 1 = 0 не имеет решений.

2. Диофантово уравнение 5×x – 10 = 0 имеет решение x = 2, которое является единственным.

3. Уравнение ln x – 8×x² = 0 не является диофантовым.

4. Часто уравнения вида P(x₁, …, x_n) = Q(x₁, …, x_n), где P(x₁, …, x_n), Q(x₁, …, x_n) – многочлены с целыми коэффициентами, также называют диофантовыми. Их можно записать в виде P(x₁, …, x_n) – Q(x₁, …, x_n) = 0, который является стандартным для диофантовых уравнений.

5. x² – y² = a – диофантово уравнение второй степени с двумя неизвестными x и y при любом целом a. Оно имеет решения при a = 1, но не имеет решений при a = 2.

 

Линейные диофантовы уравнения

Пусть a₁, …, a_n, с Î Z. Уравнение вида a₁×x₁ + … + a_n×x_n = c называется линейным диофантовым уравнением с коэффициентами a₁, …, a_n, правой частью c и неизвестными x₁, …, x_n. Если правая часть с линейного диофантова уравнения нулевая, то такое диофантово уравнение называется однородным.

Наша ближайшая цель – научиться находить частные и общие решения линейных диофантовых уравнений с двумя неизвестными. Очевидно, что любое однородное диофантово уравнение a₁×x₁ + … + a_n×x_n = 0 всегда имеет частное решение (0; …; 0).

Очевидно, что линейное диофантово уравнение, все коэффициенты которого равны нулю, имеет решение только в случае, когда его правая часть равна нулю. В общем случае имеет место следующая

Теорема (о существовании решения линейного диофантова уравнения). Линейное диофантово уравнение a₁×x₁ + … + a_n×x_n = c, не все коэффициенты которого равны нулю, имеет решение тогда и только тогда, когда НОД(a₁ , …, a_n) | c.

Доказательство. Необходимость условия очевидна: НОД(a₁, …, a_n) | a_i (1 £ i £ n), так что НОД(a₁, …, a_n) | (a₁×x₁ + … + a_n×x_n), а значит, делит и

c = a₁×x₁ + … + a_n×x_n.

Пусть D = НОД(a₁, …, a_n), с = D×t и a₁×u₁ + … + a_n×u_n = D – линейное разложение наибольшего общего делителя чисел a₁, …, a_n. Умножая обе части на t, получим a₁×(u₁×t) + … + a_n×(u_n×t) = D×t = c, т.е. целочисленная

n -ка (x₁×t; …; x_n×t) является решением исходного уравнения с n неизвестными.

Теорема доказана.

Эта теорема даёт конструктивный алгоритм для нахождения частных решений линейных диофантовых уравнений.

Примеры: 1. Линейное диофантово уравнение 12×x+21×y = 5 не имеет решений, поскольку НОД(12, 21) = 3 не делит 5.

2. Найти частное решение диофантова уравнения 12×x+21×y = 6.

Очевидно, что теперь НОД(12, 21) = 3 | 6, так что решение существует. Запишем линейное разложение НОД(12, 21) = 3 = 12×2 + 21×(–1). Поэтому пара (2; –1) – частное решение уравнения 12×x+21×y = 3, а пара (4; –2) – частное решение исходного уравнения 12×x+21×y = 6.

3. Найти частное решение линейного уравнения 12×x + 21×y – 2×z = 5.

Так как (12, 21, –2) = ((12, 21), –2) = (3, –2) = 1 | 5, то решение существует. Следуя доказательству теоремы, вначале найдём решение уравнения (12,21)×х–2×у=5, а затем, подставив линейное разложение наибольшего общего делителя из предыдущей задачи, получим решение исходного уравнения.

Для решения уравнения 3×х – 2×у = 5 запишем линейное разложение НОД(3, –2) = 1 = 3×1 – 2×1 очевидно. Поэтому пара чисел (1; 1) является решением уравнения 3×x – 2×y = 1, а пара (5; 5) – частным решением диофантова уравнения 3×х – 2×у = 5.

Итак, (12, 21)×5 – 2×5 = 5. Подставляя сюда найденное ранее линейное разложение (12, 21) = 3 = 12×2 + 21×(–1), получим (12×2+21×(–1))×5 – 2×5 = 5, или 12×10 + 21×(–5) – 2 5 = 5, т.е. тройка целых чисел (10; –5; 5) является частным решением исходного диофантова уравнения 12×x + 21×y – 2×z = 5.

Теорема (о структуре общего решения линейного диофантова уравнения). Для линейного диофантова уравнения a₁×x₁ + … + a_n×x_n = c справедливы следующие утверждения:

(1) если = (u₁; …; u_n), = (v₁; …; v_n) – его частные решения, то разность (u₁ – v₁; …; u_n – v_n) – частное решение соответствующего однородного уравнения a₁×x₁ + … + a_n×x_n = 0,

(2) множество частных решений линейного диофантова однородного уравнения a₁×x₁ + … + a_n×x_n = 0 замкнуто относительно сложения, вычитания и умножения на целые числа,

(3) если M – общее решение данного линейного диофантова уравнения, а L – общее решение соответствующего ему однородного диофантова уравнения, то для любого частного решения = (u₁; …; u_n) исходного уравнения верно равенство M = + L.

Доказательство. Вычитая равенство a₁×v₁ + … + a_n×v_n = c из равенства a₁×u₁ + … + a_n×u_n = c, получим a₁×(u₁ – v₁) + … + a_n×(u_n – v_n) = 0, т. е. набор

(u₁ – v₁; …; u_n – v_n) – частное решение линейного однородного диофантова уравнения a₁×x₁ + … + a_n×x_n = 0. Таким образом, доказано, что

" = (u₁; …; u_n), = (v₁; …; v_n) Î M Î L.

Это доказывает утверждение (1).

Аналогично доказывается утверждение (2):

" , Î L " z Î Z Î L Ù z× Î L.

Для доказательства (3) вначале заметим, что M Í + L. Это следует из предыдущего: " Î M Î +L.

Обратно, если = (l₁; …; l_n) Î L и = (u₁; …; u_n) Î M, то Î M:

a₁×(u₁ + l₁)+ …+a_n×(u_n + l_n) = (a₁×u₁ + … + a_n×u_n)+(a₁×l₁ + … + a_n×l_n) = c + 0 = c.

Таким образом, + L Í M, и в итоге M = + L.

Теорема доказана.

Доказанная теорема имеет наглядный геометрический смысл. Если рассмотреть линейное уравнение a₁×x₁ + … + a_n×x_n = c, где х_i Î R, то как известно из геометрии, оно определяет в пространстве Rⁿ гиперплоскость, полученную из плоскости L c однородным уравнением a₁×x₁+ … +a_n×x_n=0, проходящей через начало координат, сдвигом на некоторый вектор Î Rⁿ. Поверхность вида + L называют также линейным многообразием с направляющим пространством L и вектором сдвига . Таким образом, доказано, что общее решение М диофантова уравнения a₁×x₁ + … + a_n×x_n = c состоит из всех точек некоторого линейного многообразия, имеющих целые координаты. При этом координаты вектора сдвига тоже целые, а множество L решений однородного диофантова уравнения a₁×x₁ + … + a_n×x_n = 0 состоит из всех точек направляющего пространства с целыми координатами. По этой причине часто говорят, что множество решений произвольного диофантова уравнения образует линейное многообразие с вектором сдвига и направляющим пространством L.

Пример: для диофантова уравнения х – у = 1 общее решение M имеет вид (1+у; у), где у Î Z, его частное решение = (1; 0), а общее решение L однородного уравнения х – у = 0 запишется в виде (у; у), где у Î Z. Таким образом, можно нарисовать следующую картинку, на которой решения исходного диофантова уравнения и соответствующего однородного диофантова уравнения изображены жирными точками в линейном многообразии М и пространстве L соответственно.

2. Найти общее решение диофантова уравнения 12×x + 21×y – 2×z = 5.

Частное решение (10; –5; 5) этого уравнения было найдено ранее, найдём общее решение однородного уравнения 12×x + 21×y – 2×z = 0, эквивалентного диофантову уравнению 12×x + 21×y = 2×z.

Для разрешимости этого уравнения необходимо и достаточно выполнение условия НОД(12, 21) = 3 | 2×z, т.е. 3 | z или z = 3×t для некоторого целого t. Сокращая обе части на 3, получим 4×x + 7×y = 2×t. Частное решение (2; –1) диофантова уравнения 4×x + 7×y = 1 найдено в предыдущем примере. Поэтому (4×t; –2×t) – частное решение уравнения 4×x + 7×y = 2×t при любом

t Î Z. Общее решение соответствующего однородного уравнения

(7×u; –4×u) уже найдено. Таким образом, общее решение уравнения 4×x + 7×y = 2×t имеет вид: (4×t + 7×u; –2×t – 4×u), а общее решение однородного уравнения 12×x + 21×y – 2×z = 0 запишется так:

(4×t + 7×u; –2×t – 4×u; 3×t).

Нетрудно убедиться, что этот результат соответствует сформулированной выше без доказательства теореме о решениях однородного диофантова уравнения а₁×х₁ + … + а_n×х_n = 0: если Р = , то Р× и

(u; t)×P – общее решение рассматриваемого однородного уравнения.

Итак, общее решение диофантова уравнения 12×x + 21×y – 2×z = 5 выглядит так: (10 + 4×t + 7×u; –5 – 2×t – 4×u; 5 + 3×t).

3. На примере предыдущего уравнения проиллюстрируем другой метод решения диофантовых уравнений от многих неизвестных, который состоит в последовательном уменьшении максимального значения модулей его коэффициентов.

12×x + 21×y – 2×z = 5 Û 12×x + (10×2 + 1)×y – 2×z = 5 Û

Û 12×x + y – 2×(z – 10×y) = 5 Û

Û .

Таким образом, общее решение рассматриваемого уравнения можно записать и так: (x; 5 – 12×x + 2×u; 50 – 120×x + 21×u), где x, u – произвольные целые параметры.

§ 2. Диофантово уравнение x² – y² = a

Примеры: 1. При a = 0 получаем бесконечное число решений: x = y или x = –y для любого y Î Z.

2. При a = 1 имеем x² – y² = 1 Û (x + y)×(x – y) = 1. Таким образом, число 1 разложено в произведение двух целых множителей x + y и x – y (важно, что x, y – целые!). Поскольку у числа 1 всего два разложения в произведение целых множителей 1 = 1×1 и 1 = (–1)×(–1), то получаем две возможности: .

3. Для a = 2 имеем x² – y² = 2 Û (x + y)×(x – y) = 2. Действуя аналогично предыдущему, рассматриваем разложения

2=1×2=2×1=(–1)×(–2)=(–2)×(–1), составляем системы: , которые, в отличие от предыдущего примера, не имеют решений. Так что нет решений и у рассматриваемого диофантова уравнения x² – y² = 2.

4. Предыдущие рассмотрения наводят на некоторые выводы. Решения уравнения x² – y² = a находятся по разложению a = k×m в произведение целых чисел из системы . Эта система имеет целые решения тогда и только тогда, когда k + m и k – m чётны, т.е. когда числа k и m одной чётности (одновременно чётны или нечётны). Таким образом, диофантово уравнение x² – y² = a имеет решение тогда и только тогда, когда a допускает разложение в произведение двух целых множителей одной чётности. Остаётся только найти все такие a.

Теорема (об уравнении x² – y² = a). (1) Уравнение x² – y² = 0 имеет бесконечное множество решений .

(2) Любое решение уравнения получается имеет вид , где a = k×m – разложение числа a в произведение двух целых множителей одной чётности.

(3) Уравнение x² – y² = a имеет решение тогда и только тогда, когда a 2 (mod 4).

Доказательство. (1) уже доказано.

(2) уже доказано.

(3) (Þ) Пусть вначале диофантово уравнение x² – y² = a имеет решение. Докажем, что a 2 (mod 4). Если a = k×m – разложение в произведение целых чисел одной чётности, то при чётных k и m имеем k = 2×l, m = 2×n и a = k×m = 4×l×n º 0 (mod 4). В случае же нечётных k, m их произведение a также нечётно, разность a – 2 нечётна и не делится на 4, т.е. снова

a 2 (mod 4).

(Ü) Если теперь a 2 (mod 4), то можно построить решение уравнения x² – y² = a. Действительно, если a нечётно, то a = 1×a – разложение в произведение целых нечётных чисел, так что – решение диофантова уравнения. Если же a чётно, то ввиду a 2 (mod 4) получаем, что 4 | a, a = 4×b = 2×(2×b) – разложение в произведение целых чётных чисел, так что – решение диофантова уравнения.

Теорема доказана.

Примеры: 1. Диофантово уравнение x² – y² = 2012 не имеет решений, т.к. 2010 = 4×502 + 2 º 2 (mod 4).

2. Диофантово уравнение x² – y² = 2011 имеет решения, т.к.

2011 º 3 (mod 4). Имеем очевидные разложения

2011 = 1×2011 = 2011×1 = (–1)×(–2011) = (–2011)×(–1),

по каждому из которых находим решения (комбинации знаков любые). Других решений нет, т.к. число 2011 простое (?!).

§ 3. Диофантово уравнение x² + y² = a

Примеры: 1. 0 = 0² + 0², 1 = 0² + 1², k² = 0² + k². Таким образом, очевидно, любой квадрат тривиальным образом представим в виде суммы двух квадратов.

2. 2 = 1² + 1², 5 = 1² + 2², 8 = 2² + 2², 10 = 1² + 3², 13 = 2² + 3², 17 = 1² + 4², 18 = 3² + 3², 20 = 2² + 4², …

3. Решений нет для a = 3, 6 = 2×3, 7, 11, 12 = 2²×3, 14 = 2×7, 15 = 3×5, 19, 21 = 3×7, 22 = 2×11, 23, 24 = 3×2³, …

Анализ приведённых результатов способен навести на мысль, что отсутствие решений каким-то образом связано с простыми числами вида

4×n+3, присутствующими в разложении на множители чисел, не представимых в виде сумм двух квадратов.

Теорема (о представлении натуральных чисел суммами двух квадратов). Натуральное число a представимо в виде суммы двух квадратов тогда и только тогда, когда в его каноническом разложении простые числа вида 4×n + 3 имеют чётные показатели степеней.

Доказательство. Вначале докажем, что если натуральное число a представимо в виде суммы двух квадратов, то в его каноническом разложении все простые числа вида 4×n + 3 должны иметь чётные показатели степеней. Предположим, вопреки доказываемому, что a = р^2×k+1×b = x²+y², где

р – простое число вида 4×n+3 и b p. Представим числа х и у в виде

х = D×z, y = D×t, где D = НОД(x, y) = р^s×w, p w; z, t, s Î N ₀. Тогда получаем равенство р^2×k+1×b = D²×(z² + t²) = р^2×s×w²×(z² + t²), т.е. р^2×(k–s)+1×b = w²×(z² + t²). В левой части равенства присутствует p (нечётная степень не равна нулю), значит, на простое число p делится один из множителей в правой части. Поскольку p w, то р | (z² + t²), где числа z, t взаимно просты. Это противоречит следующей лемме (?!).