Книги по разным темам Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 76 |

Теорема Виноградова была доказана им лишь для всех достаточно больших чисел; точнее говоря, Виноградов установил существование такого числа N, что всякое целое число n > N может быть представлено в виде суммы четырех простых чисел. Метод Виноградова не позволяет никак судить о величине N; в противоположность методу Шнирельмана, он Ч существенно косвенный и неконструктивный. По существу, Виноградов доказал следующее: допуская, что существует бесконечное множество чисел, не представимых в виде суммы четырех (или менее того) простых чисел, можно получить противоречие. Здесь перед нами прекрасный пример, показывающий глубокое различие между двумя типами доказательств Ч прямым и косвенным (см. общее обсуждение этого вопроса на стр. 40)1.

Основной результат И. М. Виноградова (1937) устанавливает существование такого натурального N, что всякое нечетное n > N представимо в виде суммы трех простых чисел:

n = p1 + p2 + p3, () из чего, разумеется, вытекает уже представимость любого натурального n > N + 2 в виде суммы четырех простых чисел. Результат Виноградова о нечетных числах окончателен Ч число слагаемых (три) в его формулировке уменьшить нельзя. Что же касается четных чисел, то из представимости их в виде () з 2 СРАВНЕНИЯ Следующая проблема, еще более любопытная, чем проблема Гольдбаха, нисколько не приблизилась к своему разрешению. Было подмечено, что простые числа нередко встречаются парами в виде p и p + 2.

Таковы 3 и 5, 11 и 13, 29 и 31 и т. д. Предположение о существовании бесконечного множества таких близнецов кажется весьма правдоподобным, но до сих пор не удалось даже приблизиться к его доказательству.

з 2. Сравнения 1. Общие понятия. Всякий раз, когда приходится говорить о делимости целых чисел на некоторое определенное целое число d, все рассуждения становятся яснее и проще, если пользоваться отношением сравнения, введенным Гауссом, и соответствующими обозначениями.

Чтобы ввести понятие сравнения, рассмотрим остатки, получающиеся при делении различных чисел, например, на 5. Мы получаем:

0 = 0 5 + 0 7 = 1 5 + 2 -1 = -1 5 + 1 = 0 5 + 1 8 = 1 5 + 3 -2 = -1 5 + 2 = 0 5 + 2 9 = 1 5 + 4 -3 = -1 5 + 3 = 0 5 + 3 10 = 2 5 + 0 -4 = -1 5 + 4 = 0 5 + 4 11 = 2 5 + 1 -5 = -1 5 + 5 = 1 5 + 0 12 = 2 5 + 2 -6 = -2 5 + 6 = 1 5 + 1 и т. д. и т. д.

Заметим, что остатком при делении на 5 может быть только одно из чисел 0, 1, 2, 3, 4. Говорят, что два числа a и b сравнимы по модулю 5, если при делении на 5 они дают один и тот же остаток. Так, все числа 2, 7, 12, 17, 22,..., -3, -8, -13, -18,... сравнимы по модулю 5, так как при делении на 5 все они дают остаток 2. Вообще, говорят, что два числа a и b сравнимы по модулю d (где d Ч некоторое целое число), если при делении на d они дают один и тот же остаток; другими словами, если существует такое целое число n (положительное, отрицательное или вытекала бы сразу и представимость любого четного n в виде суммы двух простых слагаемых (т. к. в этом случае одно из слагаемых равно 2). Однако при всей правдоподобности гипотезы о представимости в таком виде любого четного n > 3, проблема ее доказательства чрезвычайно трудна и превышает, по-видимому, еще возможности математиков.

Неэффективный характер теоремы Виноградова устранен в 1939 г. К. Г. Борозe41,диным, показавшим, что в виде () представимо любое нечетное n > C = ee ;

в 1956 г. ему же удалось снизить эту оценку до C = ee. Конечно, уменьшение константы C до разумных пределов позволило бы решить гипотезу о представимости в виде () нечетных n, 6 < n < C, Ч и тем самым любого нечетного n > 6 Ч посредством прямой вычислительной проверки. Ч Прим. А. Н. Колмогорова.

58 ТЕОРИЯ ЧИСЕЛ гл. I нуль), что a - b = nd. Например, 27 и 15 сравнимы по модулю 4, так как 27 = 6 4 + 3, 15 = 3 4 + 3.

Для отношения сравнения введено специальное обозначение Ч если a и b сравнимы по модулю d, то пишут: a b (mod d). [Если же a не сравнимо с b по модулю d, то пишут a b (mod d).] Если ясно, какой модуль имеется в виду, то приписку mod d опускают.

Сравнения часто встречаются в повседневной жизни. Например, часовая стрелка указывает время по модулю 12; автомобильный счетчик отмечает пройденные расстояния по модулю 100000 (миль или километров).

Прежде чем перейти к более детальному рассмотрению сравнений и их свойств, пусть читатель проверит, что следующие утверждения в точности эквивалентны:

1) a сравнимо с b по модулю d.

2) a = b + nd, где n Ч целое.

3) a - b делится на d.

Введенные Гауссом обозначения для сравнений подчеркивают то обстоятельство, что сравнения обладают многими свойствами обычных равенств. Напомним эти свойства:

1) Всегда a = a.

2) Если a = b, то b = a.

3) Если a = b и b = c, то a = c.

Кроме того, если a = a и b = b, то 4) a + b = a + b.

5) a - b = a - b.

6) ab = a b.

Эти же свойства сохраняются, если соотношение равенства a = b заменяется соотношением сравнения a b (mod d). Именно:

1 ) Всегда a a (mod d).

2 ) Если a b (mod d), то b a (mod d).

3 ) Если a b (mod d) и b c (mod d), то a c (mod d).

(Проверьте! Ч это нетрудно.) Точно так же, если a a (mod d) и b b (mod d), то 4 ) a + b a + b (mod d).

5 ) a - b a - b (mod d).

6 ) ab a b (mod d).

Таким образом, сравнения по одному и тому же модулю можно складывать, вычитать и умножать. В самом деле, из a = a + rd, b = b + sd з 2 СРАВНЕНИЯ вытекает a + b = a + b + (r + s)d, a - b = a - b + (r - s)d, ab = a b + (a s + b r + rsd)d, что и приводит к нужным заключениям.

Сравнения допускают великолепное геометрическое представление. Если хотят дать геометрическое представление целым числам, то обыкновенно выбирают прямолинейный отрезок единичной длины и затем откладывают кратные отрезки в обе стороны. Таким образом, для каждого целого числа получается соответствующая ему точка на прямой Ч числовой оси (рис. 6). Но если приходится иметь 3 2 1 0 1 2 Рис. 6. Геометрическое представление целых чисел дело с числами по данному модулю d, два сравнимых числа Ч поскольку речь идет о делимости на d Ч рассматриваются как нечто неразличимое, так как дают одни и те же остатки. Чтобы изобразить все это геометрически, возьмем окружность, разделенную на d равных частей. Всякое целое число при делении на d дает в качестве остатка одно из чисел 0, 1, 2,..., d - 1; эти числа мы и расставим по окружности на равных расстояниях. Каждое число сравнимо с одним из этих чисел по модулю d и, следовательно, представляется соответствую щей точкой; два числа сравнимы, если изоб2 8 ражаются одной и той же точкой. Рис. сделан для случая d = 6. Циферблат часов может также служить моделью.

В качестве примера применения мульти 3 пликативного свойства сравнений 6 ) опре3 делим остатки, получающиеся при делении 9 на одно и то же число последовательных степеней числа 10. Так как 10 = -1 + 11, то 10 -1 (mod 11).

4 Умножая многократно это сравнение само 10 на себя, получаем дальше 102 (-1)(-1) = 1 (mod 11), Рис. 7. Геометрическое 103 (-1) (mod 11), представление целых чисел по модулю 104 1 (mod 11) и т. д.

Отсюда можно заключить, что всякое целое число, запись по десятичной 60 ТЕОРИЯ ЧИСЕЛ гл. I системе которого имеет вид z = a0 + a1 10 + a2 102 +... + an 10n, дает тот же остаток при делении на 11, что и сумма его цифр, взятая с чередующимися знаками:

t = a0 - a1 + a2 -...

В самом деле, мы имеем z - t = a1 11 + a2(102 - 1) + a3(103 + 1) + a4(104 - 1) +...

Так как все выражения 102 - 1, 103 + 1,... сравнимы с нулем по модулю 11, то z - t также сравнимо с нулем, и потому z при делении на дает тот же остаток, что и t. В частности, число делится на 11, т. е. дает остаток 0 при делении, в том и только том случае, если знакочередующаяся сумма его цифр делится на 11. Например, число z = 3162819 делится на 11, так как 3 - 1 + 6 - 2 + 8 - 1 + 9 = 22 делится на 11. Найти таким же образом правило делимости на 3 или на 9 еще проще, так как 10 (mod 3 и 9), и потому 10n 1 (mod 3 и 9) при любом n. Отсюда следует, что число z делится на 3 и на 9 в том и только том случае, если сумма его цифр s = a0 + a1 + a2 +... + an делится соответственно на 3 и на 9.

Если в качестве модуля возьмем 7, то получим 10 3, 102 2, 103 -1, 104 -3, 105 -2, 106 1.

Далее остатки повторяются. Таким образом, z делится на 7 в том и только том случае, если выражение r = a0 + 3a1 + 2a2 - a3 - 3a4 - 2a5 + a6 + 3a7 +...

делится на 7.

Упражнение. Найдите подобный же признак делимости на 13.

Складывая и умножая сравнения по определенному модулю, скажем d = 5, можно всегда обеспечить то, чтобы входящие числа не становились слишком большими, заменяя всякий раз встречающееся число одним из чисел 0, 1, 2, 3, 4, а именно тем, с которым оно сравнимо. Так, вычисляя суммы и произведения различных чисел по модулю 5, нужно только пользоваться следующими таблицами сложения и умножения:

з 2 СРАВНЕНИЯ a + b ab b 0 1 2 3 4 b 0 1 2 3 a 0 0 1 2 3 4 a 0 0 0 0 0 1 1 2 3 4 0 1 0 1 2 3 2 2 3 4 0 1 2 0 2 4 1 3 3 4 0 1 2 3 0 3 1 4 4 4 0 1 2 3 4 0 4 3 2 Из второй таблицы видно, что произведение ab сравнимо с нулем по модулю 5 только в том случае, если a или b 0 (mod 5). Это наводит на мысль о существовании следующего общего закона:

7) ab 0 (mod d) только в том случае, если a 0 или b 0 (mod d), что является распространением хорошо известного свойства обыкновенного умножения:

ab = 0 только в том случае, если a = 0 или b = 0.

Но закон 7) действителен только при том условии, что модуль d есть простое число. Действительно, сравнение ab 0 (mod d) означает, что ab делится на d, а мы уже видели, что произведение ab делится на простое d в том и только том случае, если один из множителей a или b делится на d, т. е. если a 0 (mod d) или b 0 (mod d).

С другой стороны, закон теряет силу при d составном: можно тогда написать d = r s, где оба множителя r и s меньше чем d, так что r 0 (mod d), s 0 (mod d) и, однако, rs = d 0 (mod d).

Например, 2 0 (mod 6) и 3 0 (mod 6), но 2 3 = 6 0 (mod 6).

Упражнения. 1) Покажите, что для сравнений по простому модулю имеет место следующее правило сокращения: если ab ac и a 0, то b c.

2) С каким числом в пределах от 0 до 6 включительно сравнимо число 11 18 2322 13 19 по модулю 7 3) С каким числом в пределах от 0 до 12 включительно сравнимо число 3 7 11 17 19 23 29 113 по модулю 13 4) С каким числом в пределах от 0 до 4 включительно сравнима сумма 1 + 2 + 22 +... + 219 по модулю 5 2. Теорема Ферма. В XVII столетии Ферма, основатель современной теории чисел, открыл чрезвычайно важную теорему. Если p Ч простое число, не делящее целого числа a, то ap-1 1 (mod p).

62 ТЕОРИЯ ЧИСЕЛ гл. I Другими словами, (p - 1)-я степень a при делении на p дает остаток 1.

Некоторые из ранее произведенных нами вычислений подтверждают эту теорему: так, мы видим, что 106 1 (mod 7), 102 1 (mod 3) и 1010 1 (mod 11). Таким же образом легко проверить, что 212 (mod 13) и 510 1 (mod 11). Для этой цели нет необходимости на самом деле вычислять столь высокие степени данных чисел; достаточно использовать мультипликативное свойство сравнений:

24 = 16 3 (mod 13), 52 3 (mod 11), 28 9 -4 (mod 13), 54 9 -2 (mod 11), 212 -4 3 = -12 1 (mod 13), 58 4 (mod 11), 510 3 4 = 12 = 1 (mod 11).

Обращаясь к доказательству теоремы Ферма, рассмотрим числа, кратные a:

m1 = a, m2 = 2a, m3 = 3a,..., mp-1 = (p - 1)a.

Никакие два из этих чисел не могут быть между собой сравнимы по модулю p. В противном случае p должно было бы делить разность mr ms = (r - s)a, где r, s была бы пара целых чисел, подчиненных ограничению 1 r < s (p - 1). Но из закона 7) следует, что этого не может случиться: так как s - r меньше чем p, то p не делит s - r; с другой стороны, по предположению, p не делит и a. Таким же образом мы убеждаемся, что ни одно из чисел m не сравнимо с нулем. Отсюда следует, что числа m1, m2,..., mp-1 соответственно сравнимы с числами 1, 2,..., p - 1, взятыми в некоторой их перестановке. Дальше заключаем:

m1m2... mp-1 = 1 2 3... (p - 1)ap-1 1 2 3... (p - 1) (mod p), или же, полагая ради краткости K = 1 2 3... (p - 1), K(ap-1 - 1) 0 (mod p).

Число K не делится на p, так как ни один из входящих в него множителей не делится на p; значит, согласно закону 7) (ap-1 - 1) должно делиться на p, т. е.

ap-1 - 1 0 (mod p).

Это и есть теорема Ферма.

Проверим эту теорему еще раз. Возьмем p = 23 и a = 5; тогда получаем по модулю 52 2, 54 4, 58 16 = -7, 516 49 3, 520 12, 522 24 1.

Если возьмем a = 4 вместо 5, то будем иметь, опять-таки по модулю 23, 42 -7, 43 -28 -5, 44 -20 = 3, 48 9, 411 -45 1, 422 1.

В примере, где было взято a = 4, p = 23 (как и во многих иных), можно заметить, что не только (p - 1)-я степень, но и более низкая степень a з 2 СРАВНЕНИЯ уже оказывается сравнимой с единицей. Наименьшая такая степень Ч в нашем примере степень 11 Ч непременно есть делитель числа p - (см. ниже, упражнение 3).

Упражнения. 1) С помощью подобных же вычислений проверьте, что 28 1 (mod 17), 38 -1 (mod 17), 314 -1 (mod 29), 214 -1 (mod 29), 414 1 (mod 29), 514 1 (mod 29).

2) Проверьте теорему Ферма, взяв p = 5, 7, 11, 17 и 23 и придавая числу a различные значения.

3) Докажите общую теорему: наименьшее число e, для которого ae (mod p), должно быть делителем p - 1. [Указание: произведите деление p - на e, получая p - 1 = ke + r, где 0 r < e, и дальше воспользуйтесь тем обстоятельством, что ap-1 ae (mod p).] 3. Квадратические вычеты. Обращаясь снова к примерам, иллюстрирующим теорему Ферма, мы можем подметить, что не только всегда справедливо сравнение ap-1 1 (mod p), но (предположим, что p есть простое число, отличное от 2, значит, Ч нечетное, p = 2p + 1) при p- некоторых значениях a справедливо также сравнение ap = a (mod p). Это обстоятельство вызывает ряд заслуживающих внимания соображений. Теорему Ферма можно записать в следующем виде:

ap-1 - 1 = a2p - 1 = (ap - 1)(ap + 1) 0 (mod p).

Так как произведение делится на p только в том случае, если один из множителей делится на p, то, значит, одно из чисел ap - 1 или ap + должно делиться на p; поэтому, каково бы ни было простое число p > и каково бы ни было число a, не делящееся на p, непременно должно иметь место одно из двух сравнений p-1 p-2 a 1 или a -1 (mod p).

Начиная с самого возникновения современной теории чисел, математики были заинтересованы выяснением вопроса: для каких чисел a оправдывается первое сравнение, а для каких Ч второе Предположим, что a сравнимо по модулю p с квадратом некоторого числа x, a x2 (mod p).

Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 76 |    Книги по разным темам