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

<910 11 12 13 14 15 >

Пусть 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 соответственно.

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

Теорема (об общем решении диофантова уравнения a×x + b×y =0). Если D = НОД(a, b), и a = D×a₁ , b = D×b₁ , то общее решение линейного однородного диофантова уравнения a×x + b×y = 0 имеет вид

L = {(b₁×t ; –a₁×t) Î Z´Z | t Î Z}.

Доказательство.Очевидно, что любая пара чисел х = b₁×t , у = –a₁×t (t Î Z) удовлетворяет уравнению a×x + b×y = 0 Û a₁×x + b₁×y = 0.

Обратно, ввиду a×x + b×y = 0 Û a₁×x + b₁×y = 0 и взаимной простоты чисел а₁ , b₁ , из b₁ | a₁×x получаем х = b₁×t для некоторого t Î Z.Подставив х в равенство a₁×x = b₁×(–y), найдём y = –a₁×t, что и требовалось.

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

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

Теорема (об общем решении линейного диофантова уравнения с n неизвестными а₁×х₁ + … + а_n×х_n = 0).Для линейного однородного диофантова уравнения a₁×x₁ + … + a_n×x_n= 0 существует такая целочисленная матрица P Î M(n–1, n, Z), что P× , а общее решение этого уравнения зависит от n–1 целочисленного параметра t₁ , … , t_n–1 и имеет вид

M = { ×P | = (t₁ ; … ; t_n-1) Î Z^n–1 }.

Очевидно, что в случае n = 2 матрица Р – это просто строка (b₁ ; –a₁).

Примеры: 1.Решить диофантово уравнение 12×x + 21×y = 6.

В предыдущих примерах было найдено частное решение (4; –2) этого диофантова уравнения. Согласно доказанной теореме, общее решение однородного уравнения 12×x + 21×y = 0 имеет вид (7×t; –4×t), t Î Zили (нужно учесть, что НОД(12; 21) = 3 и 12×x+21×y = 0 Û Û 4×x = 7×(–y)). Поэтому общее решение рассматриваемого диофантова уравнения имеет вид (4 + 7×t;–2 – 4×t), t Î Z или .

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 – произвольные целые параметры.

Упражнение: Докажите, что множества решений, найденные разными способами, совпадают, т.е.

{(10 + 4×t + 7×u ; –5 – 2×t – 4×u ; 5 + 3×t) Î Z³ | u, t Î Z} =

= {(x; 5 – 12×x + 2×u ; 50 – 120×x + 21×u) Î Z³ | x, u Î Z}

4.Ещё пример: решить диофантово уравнение 5×x – 9×y + 14×z = 8.

5×x – 9×y + 14×z = 8 Û 5×x – 9×y +(5×2 + 4)×z = 8 Û

Û 5×(x + 2×z) – 9×y + 4×z = 8 Û

Û Û

Û .

Таким образом, общее решение рассматриваемого уравнения выглядит так: (24 – 14 v + 27×y, y, –8 + 5×v – 9×y), где y, v – произвольные целочисленные параметры.

Упражнения: 1. Найдите всеми возможными способами общие решения следующих диофантовых уравнений: 32×x + 52×y = 22, 13×x + 15×y – 23×z = 1, 2×x + 4×y –6×z – 8×t = 12.

2. Найдите все целые числа x, y, удовлетворяющие диофантову уравнению 23×x – 34×y = 5, для которых величина |x| + |y| а) минимальна, б) не превосходит 100 и максимально возможна.

3. Два весёлых портных ставят метки на ленте длиной 100 м. Первый портной ставит свои метки через каждые 17 см., а второй – через каждые 25 см. На каких расстояниях от начала ленты будет стоять метка первого портного, на расстоянии не более 2 см. от которой второй портной также поставит свою метку ? Укажите последнюю метку первого портного с этим свойством.

4. Докажите, что монетами 3 дублонаи 5 дублоновможно сдать любую сдачу, большую 7 дублонов (количество монет не ограничено).

§ 2. Общее диофантово уравнение от одного переменного

Общее диофантово уравнение от одного переменного имеет следующий вид: a_n×xⁿ + a_n_–1×xⁿ^–1 + … + a₁×x + a₀ = 0, где f(x) = a_n×xⁿ + … + a₁×x + a₀ – многочлен с заданными целыми коэффициентами. Вопрос о решениях этого диофантова уравнения – это вопрос о целых корнях многочлена с целыми коэффициентами.

Теорема (о рациональных корнях многочлена с целыми коэффициентами).Если несократимая дробь a = Î Q является корнем многочлена f(x) = a_n×xⁿ+…+a₁×x+a₀ Î Z[x] степени n с целыми коэффициентами, то p | a₀ и q | a_n .

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

0 = f(a) = =

= ×(a_n×pⁿ + a_n–1×p^n–1×q +…+ a_i×pⁱ×q^n–i +…+ a₁×p×q^n–1 + a₀×qⁿ),

a_n×pⁿ + a_n–1×p^n–1×q + … + a_i×pⁱ×q^n–i + … + a₁×p×q^n–1 + a₀×qⁿ = 0,

a₀×qⁿ = p×( –a_n×p^n–1 – a_n–1×p^n–2×q – … – a₁×q^n–1).

Итак, p | a₀×qⁿ , причём р взаимно просто с q, а значит, и с qⁿ (дробь a несократима !). Поэтому p | a₀ . Аналогично, из равенства

a_n×pⁿ = q×(–a_n–1×p^n–1 – … – a₁×p×q^n–2 – a₀×q^n–1)

получим, что q | a_n .

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

Следствие (о целых корнях многочлена с целыми коэффициентами).Если целое число a Î Z является корнем многочлена f(x) = a_n×xⁿ+…+a₁×x+a₀ степени n с целыми коэффициентами, то a | a₀ .

Доказательство. Целый корень a – это несократимая дробь , так что из теоремы получаем a | a₀ , что и требовалось.

Следствие доказано.

Примеры: 1. Найти все рациональные корни многочлена

f(x) = 2×х⁴ + 5×х³ – х² + 5×х – 3.

По доказанной теореме, если несократимая дробь a = Î Q является корнем этого многочлена, то р | (–3) и q | 2 . Всегда можно считать, что q > 0. Поэтому все возможные значения для p и q таковы p = ±1, ±3; q = 1, 2, а все возможные значения для a соответственно a = = ±1, ±3, ± , ± . Устно убеждаемся, что a =±1 – не корни, a = 3 также не подходит, т.к. “в многочлене много слагаемых с плюсом и мало с минусом”. Легко убедиться, что a = –3 – корень: 2×3⁴–5×3³–3²–5×3–3 = 9(2×9–5×3–1–2) = 9×(18–15–3) = 0. Понизим степень многочлена: 2×х⁴+5×х³–х²+5×х–3 = (х+3)×(2×х³–х²+2×х–1).

Доказанная теорема, применённая к многочлену 2×х³–х²+2×х–1, исключает возможность р = ±3. Значит, нужно только проверить a = ± . Ясно, что a = – корень. Снова понижаем степень: 2×х³–х²+2×х–1 = (х – )×(2×х²+2), и многочлен 2×х²+2 не имеет вещественных корней. Итак, исходный многочлен имеет два рациональных корня: a = и a = –3, один из которых целый.

2. Найти все целые корни многочлена f(x) = 3×x⁴ – 2×x² + x +38.

Ясно, что нужно проверить делители свободного члена 38 = 2×19. Таких делителей четыре: ±1, ±2, ±19, ±38. Проведём вычисления по схеме Горнера:

f_i –2

S_i(1) 3 3 1 2 40

S_i(–1) 3 –3 1 0 38

S_i(2) 3 6 10 21 80

S_i(–2) 3 –6 10 –19

Найден один корень a = –2. Можно понизить степень, взяв коэффициенты частного от деления f(x) на x + 2 из последней строки таблицы:

f(x) = (x + 2)×(3×x³ – 6×x² + 10×x – 19).

Целыми корнями многочлена 3×x³ – 6×x² + 10×x – 19 могут быть только ±1, ±19. Но ±1 уже проверены и корнями не являются, число 19 даёт явно положительное значение, а число –19 явно отрицательное.

Итак, многочлен f(x) = 3×x⁴ – 2×x² + x +38 имеет единственный целый корень a = –2.

§ 3. Диофантово уравнение 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 простое (?!).

§ 4. Диофантово уравнение 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 = р²^×^k⁺¹×b = x²+y², где р – простое число вида 4×n+3 и b p. Представим числа х и у в виде х = D×z, y = D×t, где D = НОД(x, y) = р^s×w, p w; z, t, s Î N₀ . Тогда получаем равенство р²^×^k⁺¹×b = D²×(z² + t²) = р²^×^s×w²×(z² + t²) , т.е. р²^×⁽^k^–^s⁾⁺¹×b = w²×(z² + t²). В левой части равенства присутствует p (нечётная степень не равна нулю), значит, на простое число p делится один из множителей в правой части. Поскольку p w, то р | (z² + t²), где числа z, t взаимно просты. Это противоречит следующей лемме (?!).

Лемма (о делимости суммы двух квадратов на простое число вида 4×n + 3).Если простое число р = 4×n+3 делит сумму квадратов двух натуральных чисел, то оно делит каждое из этих чисел.

Доказательство. От противного. Пусть x² + y² º 0 (mod p), но x 0 или y 0 (mod p). Поскольку x и y симметричны, их можно менять местами, так что можно предполагать, что x p.

Лемма (об обратимости по модулю p). Для любого целого числа x, не делящегося на простое число p, существует обратный элемент по модулю p – такое целое число 1 £ u < p, что x×u º 1 (mod p).

Доказательство. Число x взаимно простое с p, поэтому можно записать линейное разложение НОД(x, p) = 1 = x×u + p×v (u, v Î Z). Ясно, что x×u º 1 (mod p), т.е. u – обратный элемент к x по модулю p. Если u не удовлетворяет ограничению 1 £ u < p, то поделив u с остатком на p, получим остаток r º u (mod p), для которого x×r º x×u º 1 (mod p) и 0 £ r < p.

Лемма об обратимости по модулю p доказана.

Умножая сравнение x² + y² º 0 (mod p) на квадрат u² обратного элемента к x по модулю p, получим

0 = 0×u² º x²×u² + y²×u² = (x×u)² + (y×u)² º 1 + t² (mod p).

Таким образом, для t = y×u выполнено сравнение t² º –1 (mod p), которое и приведём к противоречию. Ясно, что t p : иначе t º 0 (mod p) и 0 º t² º º –1 (mod p), что невозможно. По теореме Ферма имеем t^p^–1 º 1 (mod p), что вместе с t² º –1 (mod p) и p = 4×n + 3 приводит к противоречию:

1 º t^p–1 = t⁴^×^n+3–1 = t²^×⁽²^×ⁿ⁺¹⁾ = (t²)²^×ⁿ⁺¹ º (–1)²^×ⁿ⁺¹ = –1 (mod p).

Полученное противоречие показывает, что допущение о x 0 (mod p) было не верным.

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

Таким образом, доказано, что число, в каноническое разложение которого входит простое число p = 4×n + 3 в нечётной степени, не представимо в виде суммы двух квадратов.

Докажем теперь, что любое число, в каноническом разложении которого простые числа p = 4×n + 3 участвуют только в чётных степенях, представимо в виде суммы двух квадратов.

Идея доказательства основана на следующем тождестве:

(а² + b²)×(c² + d²) = (a×c – b×d)² + (a×d + b×c)² ,

которое можно получить из известного свойства модуля комплексных чисел – модуль произведения равен произведению модулей. Действительно,

|z|×|t| = |z×t| Û |a + b×i|×|c + d×i| = |(a + b×i)×(c + d×i)| Û

Û |a + b×i|²×|c + d×i|² = |(a×c – b×d) + (a×d + b×c)×i|² Û

Û (а² + b²)×(c² + d²) = (a×c – b×d)² + (a×d + b×c)² .

Из этого тождества следует, что если два числа u, v представимы в виде суммы двух квадратов: u = x² + y², v = z² + t², то и их произведение u×v представимо в виде суммы двух квадратов: u×v = (x×z – y×t)² + (x×t + y×z)².

Любое натуральное число a > 1 можно записать в виде a = р₁× … ×р_k×m² , где р_i – попарно различные простые числа, m Î N. Для этого достаточно найти каноническое разложение , записать каждую степень вида r^a в виде квадрата (r^b)² при чётном a = 2×b, или в виде r^a = r×(r^b)² при нечётном a = 2×b + 1, а затем сгруппировать отдельно квадраты и оставшиеся одиночные простые числа. Например,

29250 = 2×3²×5³×13 = 2×5×13×(3×5)² , m = 15.

Число m² обладает тривиальным представлением в виде суммы двух квадратов: m² = 0² + m² . Если доказать представимость в виде суммы двух квадратов всех простых чисел р_i (1 £ i £ k), то используя тождество, будет получено и представление числа a.По условию, среди чисел р₁ , … , р_k могут встретиться только 2 = 1² + 1² и простые числа вида 4×n + 1. Таким образом, осталось получить представление в виде суммы двух квадратов простого числа р = 4×т + 1. Это утверждение выделим в отдельную теорему (см. ниже)

Например, для a = 29250 = 2×5×13×(15)² последовательно получаем:

2 = 1² + 1², 5 = 1² + 2², 13 = 2² + 3²,

2×5 = (1×1 – 1×2)² + (1×2 + 1×1)² = 1² + 3²,

2×5×13 = (1×2 – 3×3)² + (1×3 + 3×2)² = 7² + 9²,

29250 = 2×5×13×(15)² = (7×15)² + (9×15)² = 105² + 135².

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

Критерий Вильсона простоты числа. Число p Î N простое тогда и только тогда, когда (p – 1) ! º –1 (mod p).

Доказательство. (Ü) Если (p – 1) ! º –1 (mod p), но p не простое, то p = m×n, где 1 < < p. Тогда числа m, n участвуют в (p – 1) ! = 1×…×(p–1) в качестве сомножителей. Значит, m×u = (p – 1) ! = –1 + p×t = –1 + m×n×t . По свойствам делимости –1 M m, что невозможно.

(Þ) Пусть теперь p – простое число. Докажем, что (p – 1)! º –1 (mod p). Для p = 2, 3 это очевидно, так что будем считать, что p ³ 5.

Пользуясь леммой об обратимости по модулю p, замечаем, что у каждого множителя x из произведения 1×…×x×…×(p–1) существует элемент обратный 1 £ u < p по модулю p : x×u º 1 (mod p). При этом элемент u тоже участвует в рассматриваемом произведении (p – 1) ! = 1×…×x×…×u×…×(p–1) и разным x отвечают разные обратные: если x×u º 1 º y×u (mod p), где x ³ y, то (x – y)×u º 0 (mod p), т.е. p | (x – y)×u, а значит, p | (x – y) или p | u, что возможно только при x = y, т.к. 0 £ x – y < p, 1 £ u < p.

Может ли оказаться, что x = u ? В этом случае x² º 1 (mod p), т.е. выполнено условие (x + 1)×(x – 1) º 0 (mod p) значит, p | (x + 1)×(x – 1), т.е. либо x + 1 M p, либо x – 1 M p. Это возможно только при x = 1 или x = p – 1.

Из проведённого анализа следует, что числа 2, … , p – 2 можно разбить на такие пары, что произведение чисел внутри каждой из них сравнимо с 1 по модулю p. Таким образом,

(p – 1) ! = 1×2×…×(p–2)×(p–1) = 1×(p–1)×(x₁×u₁)×…×(x_k×u_k) º 1×(–1)×1×…×1 = –1

по модулю p (k = ).

Критерий Вильсона доказан.

Примеры: 1.Для p = 5 имеем

4 ! = 1×2×3×4 = 1×4×(2×3) º 1×(–1)×1 = –1 (mod 5).

2. Для p = 5 имеем

12 ! = 1×2×3×4×5×6×7×8×9×10×11×12 =

= 1×12×(2×7)×(3×9)×(4×10)×(5×8)×(6×11) º 1×(–1)×1×1×1×1×1 = –1 (mod 13).

Теорема (о представлении простого числа 4×n+1 в виде суммы двух квадратов). Любое простое число вида p = 4×n + 1 представимо в виде суммы двух квадратов.

Доказательство. Вначале докажем, что в виде суммы двух квадратов представимо некоторое кратное числа p. Для этого используем критерий Вильсона и то, что p = 4×n + 1.

Имеем

–1 º (p – 1) ! = 1×2× … ×(p – 1) =

= 1×2× … ×(2×n–1)×(2×n)×(2×n+1)× … ×(4×n–1)×(4×n) º

º 1×2× … ×(2×n–1)×(2×n)×(–2×n)×(–(2×n–1))× … ×(–2)×(–1) =

= (–1)²^×ⁿ×1²×2²× … ×(2×n–1)²×(2×n)² = ((2×n) !)² (mod 4×n + 1).

Таким образом, если K = (2×n) ! , то –1 º K² (mod p), т.е. 1 + K² º 0 (mod p). Это значит, что 1 + K² = p×t для некоторого целого t.

Рассмотрим теперь множество всех упорядоченных пар целых чисел

M = {(u ; v) Î Z² | 0 £ £ k},

где k = [ ] – целая часть , т.е. наибольшее целое число, не превосходящее .

Примеры: [2,1] = 2, [ ] = 1, [3,99] = 3, [–0,5] = –1, [–2,1] = –3.

Во множестве M содержится (k + 1)² элементов, причём

(k + 1)² = k² + 2×k + 1 > ( – 1)² + 2×( – 1) + 1 = p.

Для каждой пары (u ; v) Î M рассмотрим число u + K×v Î N₀ и заметим, что все эти числа различны. Действительно, если u₁ + K×v₁ = u₂ + K×v₂ , то (u₁ – u₂) = K×(v₂ – v₁), причём |u₁ – u₂| £ k < = < K = (2×n) ! (докажите последнее неравенство !). Поэтому u₁ – u₂ может делиться на K только при u₁ = u₂ и v₁ = v₂ .

Итак, получили различные между собой числа вида u + K×v , количество которых больше p – числа остатков от деления на p. Значит, два каких-то различных числа u₁ + K×v₁ и u₂ + K×v₂ из рассматриваемого множества чисел дают одинаковые остатки при делении на p. Из u₁ + K×v₁ º u₂ + K×v₂ (mod p) следует, что (mod p), причём, как и ранее, |u| = |u₁ – u₂| < , |v| = |v₁ – v₂| < . Тогда u² – K²×v² = (u + K×v)×(u – K×v) кратно p. Учитывая, что K² º –1 (mod p), получим 0 º (u + K×v)×(u – K×v) = = u² – K²×v² º u² + v² (mod p). Значит, на p делится число u² + v² , где 0 < u² + v² < 2×p, т.е. u² + v² = p.

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

Пифагоровы тройки

Рассмотрим уравнение x² + y² = z² , представляющее собой соотношение Пифагора для прямоугольного треугольника. Вначале найдём все его рациональные решения, а затем – все целые решения диофантова уравнения.

1. Рациональные решения. Во-первых, уравнение переписывается в виде , где отношения , рациональны, если рациональными были x, y. Эти отношения являются рациональными координатами точе