logo
Th_Numb+Combi (2)

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

Общее диофантово уравнение от одного переменного имеет следующий вид: anxn + an–1xn–1 + … + a1x + a0 = 0, где f(x) = anxn + … + a1x + a0 – многочлен с заданными целыми коэффициентами. Вопрос о решениях этого диофантова уравнения – это вопрос о целых корнях многочлена с целыми коэффициентами.

Теорема (о рациональных корнях многочлена с целыми коэффициентами). Если несократимая дробь = Q является корнем многочлена f(x) = anxn+…+a1x+a0 Z[x] степени n с целыми коэффициентами, то p | a0 и q | an .

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

0 = f() = =

= (anpn + an–1pn–1q +…+ aipiqn–i +…+ a1pqn–1 + a0qn),

anpn + an–1pn–1q + … + aipiqn–i + … + a1pqn–1 + a0qn = 0,

a0qn = p( –anpn–1 – an–1pn–2q – … – a1qn–1).

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

anpn = q(–an–1pn–1 – … – a1pqn–2 – a0qn–1)

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

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

Следствие (о целых корнях многочлена с целыми коэффициентами). Если целое число Z является корнем многочлена f(x) = anxn+…+a1x+a0 степени n с целыми коэффициентами, то | a0 .

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

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

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

f(x) = 2х4 + 5х3 – х2 + 5х – 3.

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

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

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

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

fi

3

0

–2

1

38

Si(1)

3

3

1

2

40

Si(–1)

3

–3

1

0

38

Si(2)

3

6

10

21

80

Si(–2)

3

–6

10

–19

0

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

f(x) = (x + 2)(3x3 – 6x2 + 10x – 19).

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

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

§ 3. Диофантово уравнение x2 – y2 = a

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

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

3. Для a = 2 имеем x2 – y2 = 2 (x + y)(x – y) = 2. Действуя аналогично предыдущему, рассматриваем разложения 2 = 12 = 21 = (–1)(–2) = = (–2)(–1), составляем системы: , которые, в отличие от предыдущего примера, не имеют решений. Так что нет решений и у рассматриваемого диофантова уравненияx2 – y2 = 2.

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

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

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

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

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

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

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

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

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

Примеры: 1. Диофантово уравнение x2 – y2 = 2012 не имеет решений, т.к. 2010 = 4502 + 2 2 (mod 4).

2. Диофантово уравнение x2 – y2 = 2011 имеет решения, т.к. 2011 3 (mod 4). Имеем очевидные разложения

2011 = 12011 = 20111 = (–1)(–2011) = (–2011)(–1),

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

§ 4. Диофантово уравнение x2 + y2 = a

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

2. 2 = 12 + 12, 5 = 12 + 22, 8 = 22 + 22, 10 = 12 + 32, 13 = 22 + 32, 17 = 12 + 42, 18 = 32 + 32, 20 = 22 + 42, …

3. Решений нет для a = 3, 6 = 23, 7, 11, 12 = 223, 14 = 27, 15 = 35, 19, 21 = 37, 22 = 211, 23, 24 = 323, …

Анализ приведённых результатов способен навести на мысль, что отсутствие решений каким-то образом связано с простыми числами вида 4n + 3, присутствующими в разложении на множители чисел, не представимых в виде сумм двух квадратов.

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

Доказательство. Вначале докажем, что если натуральное число a представимо в виде суммы двух квадратов, то в его каноническом разложении все простые числа вида 4n + 3 должны иметь чётные показатели степеней. Предположим, вопреки доказываемому, что a = р2k+1b = x2+y2, где р – простое число вида 4n+3 и b p. Представим числа х и у в виде х = Dz, y = Dt, где D = НОД(x, y) = рsw, p w; z, t, s N0 . Тогда получаем равенство р2k+1b = D2(z2 + t2) = р2sw2(z2 + t2) , т.е. р2(k–s)+1b = w2(z2 + t2). В левой части равенства присутствует p (нечётная степень не равна нулю), значит, на простое число p делится один из множителей в правой части. Поскольку p w, то р | (z2 + t2), где числа z, t взаимно просты. Это противоречит следующей лемме (?!).

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

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

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

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

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

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

0 = 0u2 x2u2 + y2u2 = (xu)2 + (yu)2 1 + t2 (mod p).

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

1 t p–1 = t 4n+3–1 = t 2(2n+1) = (t 2)2n+1 (–1)2n+1 = –1 (mod p).

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

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

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

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

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

(а2 + b2)(c2 + d2) = (ac – bd)2 + (ad + bc)2 ,

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

|z||t| = |zt| |a + bi||c + di| = |(a + bi)(c + di)|

|a + bi|2|c + di|2 = |(ac – bd) + (ad + bc)i|2

(а2 + b2)(c2 + d2) = (ac – bd)2 + (ad + bc)2 .

Из этого тождества следует, что если два числа u, v представимы в виде суммы двух квадратов: u = x2 + y2, v = z2 + t2, то и их произведение uv представимо в виде суммы двух квадратов: uv = (xz – yt)2 + (xt + yz)2.

Любое натуральное число a > 1 можно записать в виде a = р1 … рkm2 , где рi – попарно различные простые числа, m N. Для этого достаточно найти каноническое разложение , записать каждую степень видаr в виде квадрата (r)2 при чётном = 2, или в виде r = r(r)2 при нечётном = 2 + 1, а затем сгруппировать отдельно квадраты и оставшиеся одиночные простые числа. Например,

29250 = 2325313 = 2513(35)2 , m = 15.

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

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

2 = 12 + 12, 5 = 12 + 22, 13 = 22 + 32,

25 = (11 – 12)2 + (12 + 11)2 = 12 + 32,

2513 = (12 – 33)2 + (13 + 32)2 = 72 + 92,

29250 = 2513(15)2 = (715)2 + (915)2 = 1052 + 1352.

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

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

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

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

Пользуясь леммой об обратимости по модулю p, замечаем, что у каждого множителя x из произведения 1…x…(p–1) существует элемент обратный 1 u < p по модулю p : xu 1 (mod p). При этом элемент u тоже участвует в рассматриваемом произведении (p – 1) ! = 1…x…u…(p–1) и разным x отвечают разные обратные: если xu 1 yu (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 ? В этом случае x2 1 (mod p), т.е. выполнено условие (x + 1)(x – 1) 0 (mod p) значит, p | (x + 1)(x – 1), т.е. либо x + 1 p, либо x – 1 p. Это возможно только при x = 1 или x = p – 1.

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

(p – 1) ! = 12…(p–2)(p–1) = 1(p–1)(x1u1)…(xkuk) 1(–1)1…1 = –1

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

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

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

4 ! = 1234 = 14(23) 1(–1)1 = –1 (mod 5).

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

12 ! = 123456789101112 =

= 112(27)(39)(410)(58)(611) 1(–1)11111 = –1 (mod 13).

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

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

Имеем

–1 (p – 1) ! = 12 … (p – 1) =

= 12 … (2n–1)(2n)(2n+1) … (4n–1)(4n)

12 … (2n–1)(2n)(–2n)(–(2n–1)) … (–2)(–1) =

= (–1)2n1222 … (2n–1)2(2n)2 = ((2n) !)2 (mod 4n + 1).

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

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

M = {(u ; v) Z2 | 0 k},

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

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

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

(k + 1)2 = k2 + 2k + 1 > ( – 1)2 + 2( – 1) + 1 = p.

Для каждой пары (u ; v) M рассмотрим число u + Kv N0 и заметим, что все эти числа различны. Действительно, если u1 + Kv1 = u2 + Kv2 , то (u1 – u2) = K(v2 – v1), причём |u1 – u2| k < = < K = (2n) ! (докажите последнее неравенство !). Поэтому u1 – u2 может делиться на K только при u1 = u2 и v1 = v2 .

Итак, получили различные между собой числа вида u + Kv , количество которых больше p – числа остатков от деления на p. Значит, два каких-то различных числа u1 + Kv1 и u2 + Kv2 из рассматриваемого множества чисел дают одинаковые остатки при делении на p. Из u1 + Kv1 u2 + Kv2 (mod p) следует, что (mod p), причём, как и ранее, |u| = |u1 – u2| < , |v| = |v1 – v2| < . Тогда u2 – K2v2 = (u + Kv)(u – Kv) кратно p. Учитывая, что K2 –1 (mod p), получим 0 (u + Kv)(u – Kv) = = u2 – K2v2 u2 + v2 (mod p). Значит, на p делится число u2 + v2 , где 0 < u2 + v2 < 2p, т.е. u2 + v2 = p.

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