Суммы квадратов - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Информация о финансово экономическом состоянии эмитента 1 134.64kb.
Вычисление суммы членов бесконечного ряда 1 32.06kb.
Вычисление суммы с конечным числом слагаемых и произведенияс конечным... 1 38.23kb.
Приложение 1 Расчет суммы упущенной выгоды при выплате комиссии за... 1 94.04kb.
На классной доске нарисуйте таблицу из 20 квадратов и пронумеруйте их. 1 39.06kb.
Голощапова Наталья 1 50.42kb.
Вопрос Жукова Ирина Юрьевна: Суммы в прогнозу продукции должны пересчитываться? 1 63.54kb.
Метод наименьших квадратов 1 248.31kb.
Методические рекомендации по выполнению заданий. Примеры выполнения... 1 35.51kb.
Задачи из справочника по математике Конечные суммы 1 37.66kb.
Уравнение множественной регрессии. Оценка уравнения регрессии 1 122.82kb.
Предположения и опровержения Рост научного знания 49 7151.38kb.
Направления изучения представлений о справедливости 1 202.17kb.

Суммы квадратов - страница №1/4

Введение


«Зачем складывать простые числа? — недоумевал великий физик Ландау. —
Простые числа созданы для того, чтобы их умножать, а не складывать!»

ЗАЧЕМ СКЛАДЫВАТЬ КВАДРАТЫ ЦЕЛЫХ ЧИСЕЛ? Почему бы не складывать их кубы или 666-е степени? Вопросы эти весьма серьезны и встают перед каждым, кто начинает изучать математику. Из огромного разнообразия задач не все достойны пристального внимания. Задача о сумме квадратов — в высшей степени достойна. К сожалению для философа, это невозможно объяснить, не рассказав ее решение и не углубившись тем самым в детали.

«Детали» — это критерий того, какие натуральные числа представимы в виде суммы квадратов двух целых чисел. В доказательстве этого критерия будут использованы не только «обычные» целые числа, но и числа комплексные — прекрасный пример применения абстрактной теории к конкретной арифметической задаче! Хотя эта статья содержит лишь малую часть богатейшей теории делимости алгебраических чисел, надеемся, ее очарование никого не оставит равнодушным.

Суммы квадратов


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

Г.Эдварде


Таблица сумм квадратов


Рассмотрим таблицу, в верхней строке и левом столбце которой — квадраты целых чисел, а в других клетках — суммы квадратов:

0

1

4

9

16

25

36

49

64

81

100

1

2

5

10

17

26

37

50

65

82

101

4

5

8

13

20

29

40

53

68

85

104

9

10

13

18

25

34

45

58

73

90

109

16

17

20

25

32

41

52

65

80

97

116

25

26

29

34

41

50

61

74

89

106

125

36

37

40

45

52

61

72

85

100

117

136

49

50

53

58

65

74

85

98

113

130

149

64

65

68

73

80

89

100

113

128

145

164

81

82

85

90

97

106

117

130

145

162

181

100

101

104

109

116

125

136

149

164

181

200

Эта таблица позволяет выписать представления: 1 = 12 + 02, 2 = 12 + 12, 4 =22 + 02, 5 = 22 + 12, 8 = 22 + 22, 9 = 32 + 02, 10 = 32 + 12, 13 = 32 + 22, ...Не вошедшие в таблицу числа первой сотни (3, 6, 7, 11, 12, 14, 15,...) в виде суммы двух квадратов не представимы.

Упражнение 1. Найдите наименьшее число, которое двумя существенно разными (т. е. не получающимися один из другого перестановкой слагаемых) способами представимо в виде суммы двух квадратов а) целых; 6) натуральных чисел.

Остатки от деления на 3


Наименьшее натуральное число, не представимое в виде суммы двух квадратов целых чисел, — это 3. Кратные 3 числа 6, 12, 15, 21 тоже не представимы, а вот числа 9 = 32 + 02 и 18 =32 + 32 — представимы. Возникает гипотеза: числа, которые кратны 3, но не кратны 9, не представимы в виде суммы двух квадратов. Эта гипотеза верна. Верно даже более сильное утверждение:

Теорема 1. Если сумма квадратов х2 + у2 целых чисел х, у кратна 3, то числа х, у тоже кратны 3.

Доказательство. Выпишем остатки от деления квадратов целых чисел на 3:

Квадрат

0

1

4

9

16

25

36

49

64

81

100

Остаток

0

1

1

0

1

1

0

1

1

0

1

Закономерность очевидна: остатки периодически повторяются, и никаких остатков кроме 0 и 1 не бывает.
(Точнее говоря, остаток от деления квадрата целого числа х на 3 равен 0, если х кратно 3, т. е. представимо в виде х = 3k, где k — целое число, и остаток равен 1, если x не кратно 3, т. е. представимо в виде х= В самом деле, в первом случае х = 9k2 делится на 3 без остатка, а во втором случае х2 = дает при делении на 3 остаток 1.)

Суммы остатков 0 + 1 и 1 + 1 не кратны 3. Значит, сумма квадратов х2 + у2 кратна 3 в том и только том случае, когда х и у кратны 3.



Упражнение 2. Докажите, что если сумма квадратов двух целых чисел кратна 31999, то эта сумма кратна 32000.

Остатки от деления на 7


Следующее после 3 и 6 не представимое в виде суммы двух квадратов число — это 7. Кратные 7 числа 14, 21, 28, 35, 42, 56, 63 не представимы в виде суммы квадратов. Опять возникает гипотеза: если сумма квадратов х2 + у2 кратна 7, то и сами целые числа х, у кратны 7.

Для доказательства составим таблицу остатков от деления квадратов на 7:



Квадрат

0

1

4

9

16

25

36

49

64

81

100

121

144

169

196

Остаток

0

1

4

2

2

4

1

0

1

4

2

2

4

1

0

Остатки, как видите, периодически повторяются. Поскольку сумма никаких двух из остатков 1, 2, 4 не кратна 7, мы доказали нашу гипотезу.

Упражнения
3. Остаток от деления квадрата целого числа х на 7 равен 0, если х = 7k, где k — целое число; равен 1, если равен 2, если х = равен 4, если Докажите это.
4. Докажите, что если сумма квадратов двух целых чисел кратна 21, то она кратна и 441.
5. а) Какие остатки дают квадраты целых чисел при делении на 11? б) Докажите, что если сумма квадратов двух целых чисел кратна 11, то она кратна 121. в) Докажите, что если сумма квадратов двух целых чисел кратна 1331, то она кратна и 14641.

Остатки от деления на 19


Если простое число р представлено в виде суммы квадратов, р = х2 + у2, то, очевидно, числа х, у меньше р и потому не могут быть кратны р. Значит, на роль тех чисел р, для которых из делимости суммы квадратов на р следует делимость на р обоих слагаемых, претендуют только числа, не представимые в виде суммы двух квадратов. Любое такое число можно исследовать аналогично числам 3 и 7.

Например, пусть р = 19. Составим таблицу остатков от деления квадратов на 19:



Квадрат

0

1

4

9

16

25

36

Остаток

0

1

4

9

16

6

17

Квадрат

49

64

81

100

121

144

169

Остаток

11

7

5

5

7

11

17

Квадрат

196

225

256

289

324







Остаток

6

16

9

4

1







В верхней строке — квадраты чисел 0, 1,..., 18. (Другие квадраты можно не рассматривать, поскольку любое, целое число х можно представить в виде х = 19q + r, где q — целое, и при этом число х2 = 192q2 + 38qr + r2 дает при делении на 19 такой же остаток, как и r2.)

В нижней строке таблицы один раз присутствует число О и по два раза - числа 1,4,5,6,7,9, 11, 16 и 17. Ненулевые остатки от деления квадратов целых чисел на простое число р > 2 называют квадратичными вычетами по модулю p. Все другие ненулевые остатки — квадратичные невычеты (при р = 19 это 2, 3, 8, 10, 12, 13, 14, 15 и 18).

Поскольку сумма никаких двух из чисел 1,4,5,6,7,9, 11, 16 и 17 не кратна 19, приходим к выводу: сумма квадратов двух целых чисел кратна 19 в том и только том случае, когда слагаемые кратны 19.

Упражнение 6. Если р — простое число, р > 2, то существует (р - 1)/2 квадратичных вычетов и ровно столько же квадратичных невычетов по модулю р. Докажите это.

Свойство простых чисел, не являющихся суммами двух квадратов


Как относиться к трудностям? В области неведомого надо рассматривать трудности как скрытый клад! Обычно: чем труднее, тем полезнее. Не так ценно, если трудности возникают от твоей борьбы с самим собой. Но когда трудности исходят от увеличившегося сопротивления предмета — это прекрасно!!

А.И.Солженицын

Чем больше по величине простое число р, тем больше квадратичных вычетов по модулю р. Поэтому пора менять метод исследования: если мы не желаем погрязнуть в нескончаемых вычислениях, то должны каким-то одним общим рассуждением охватить числа 3, 7, 11, 19 и многие другие простые числа.

Пока не вполне ясно, что это за числа и чем они отличаются от чисел 2, 5, 13, 17,... Впрочем, одно отличие очевидно: числа 3,7,11,19 не представимы, а числа 2, 5, 13,17 представимы в виде суммы квадратов двух целых чисел. Кроме того, простые числа р = 3, 7, 11, 19 обладают, как мы уже доказали, тем свойством, что если сумма квадратов целых чисел кратна р, то каждое из слагаемых кратно р. Продолжив (довольно утомительные, если не использовать компьютер) вычисления, можно доказать это свойство для р = 23, 31, 43, 47, 59, 67, 71, 79, 83, 87. Осечки ни разу не будет:



Теорема 2. Если простое число р не представимо в виде суммы двух квадратов и если сумма квадратов х2 + у2 кратна р, то каждое из целых чисел х, у кратно р.

Мы получим эту теорему как одно из следствий теории целых гауссовых чисел. Поскольку это не так уж просто, давайте отвлечемся на некоторое время от теоремы 2 и обратим внимание на другое свойство рассматриваемых простых чисел 3, 7, 11,..., 83, 87: при делении на 4 они дают остаток 3.


Числа вида 4n + 3


В виде суммы двух квадратов не представимы не только простые числа, которые при делении на 4 дают остаток 3, но и вообще все числа 3,7, 11, 15, 19,23,27,...:

Теорема 3. Всякое представимое в виде суммы квадратов двух целых чисел нечетное число при делении на 4 дает остаток 1, а не 3.

Доказательство. Из двух квадратов, сумма которых нечетна, обязательно один четен, а другой нечетен. Квадрат четного числа нацело делится на 4, а квадрат нечетного числа при делении на 4 дает остаток 1 (проверьте!).

Упражнение 7. а) Квадрат нечетного числа дает остаток 1 не только при делении на 4, но даже при делении на 8. Докажите это. б) Решите в целых числах уравнение x2 + y2 + z2 = 8n - 1. в) Никакое число вида 4m(8n + 7), где m, n — целые неотрицательные числа, не представимо в виде суммы квадратов трех целых чисел. Докажите это.

Произведение сумм квадратов


Мы уже нашли несколько признаков непредставимости числа в виде суммы двух квадратов. Не менее важны признаки представимости. Начнем с того, что если n = x2 + y2, то

(х + у)2 + (х - у)2 = x2 + 2ху + у2 + х2 - 2ху + у2 = = 2(x2 + y2) = 2n.

Значит, вместе с каждым представимым числом n представимо и число 2n. Далее,

(2х + у)2 + (х - 2у)2 = 4x2 + 4ху + у2 + х2 - 4ху + 4у2 = 5(x2 + у2)=5n.

Легко проверить и формулы

(2x +3у)2 + ( - 2у)2 = 13n,

(4x + y)2 + (x - 4y)2 = 17n.

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

(a2 + b2)(x2 + y2) = a2x2 + b2x2 + a2y2 + b2y2,

прибавим и отнимем 2аbху и изменим порядок слагаемых:

(a2 + b2)(x2 + y2) = a2x2 + 2ахbу + b2y2 + b2x2 - 2bхау + a2y2 =


= (ах + bу)2 + (bх - ау)2. (1)

Упражнение 8. Докажите, что
а) если четное число n есть сумма квадратов двух целых чисел, то и число n/2 представимо в виде суммы квадратов двух целых чисел;
б)* если кратное 5 число n есть сумма квадратов двух целых чисел, то число n/5 тоже представимо в таком виде;
в)* если 13k = х2 + у2, где k, х, у — целые числа, то хотя бы одна из формул представляет k в виде суммы квадратов целых чисел.

Теорема Ферма — Эйлера


Поскольку мы научились представлять произведение сумм двух квадратов в виде суммы двух квадратов, очень важно выяснить, какие простые числа представимы в виде суммы двух квадратов целых чисел, а какие не представимы. Числа вида 4n + 3, как утверждает теорема 3, не представимы. Поэтому рассмотрим простые числа, которые при делении на 4 дают остаток 1. Это: 5 = 22 + 12, 13 = 32 + 22, 17 = 42 + 12, 29 = 52 + 22, 37 = 62 + 12, 41 = 52 + 42, 53 = 72 + 22.

Теорема 4. Любое простое число р, которое при делении на 4 дает остаток 1, представимо в виде суммы квадратов двух натуральных чисел.

Мы приведем доказательство, состоящее из следующих двух лемм.



Лемма 1. Для любого простого числа р == 4n + 1, где существует такое целое число m, что m2 + 1 кратно р.

Лемма 2. Любой простой делитель р числа m2 + 1, где m — целое, представим в виде суммы квадратов двух натуральных чисел.

Упражнение 9. Пользуясь формулой (1), объясните, почему в лемме 2 слова «любой простой» можно заменить на «любой натуральный».

Лемму 1 мы выведем из теоремы Вильсона (1741- 1793), лемму 2 — из теории делимости целых гауссовых чисел. Но сначала сформулируем ответ на один важный вопрос.


Какие натуральные числа — суммы двух квадратов?


По теоремам 3 и 4, простое число р > 2 не представимо в виде суммы двух квадратов, если оно имеет вид р = 4k + 3, и представимо — если р = 4k + 1, где k — целое. Вспомнив формулу (1) и применив (еще не доказанную нами) теорему 2, получаем следующий элегантный критерий: натуральное число представимо в виде суммы квадратов двух целых чисел тогда и только тогда, когда в его разложение на простые множители любой простой множитель вида 4k + 3 входит в четной степени.

Этот критерий впервые был сформулирован голландцем Альбером Жираром (1595-1632) в следующем виде: натуральное число представимо в виде суммы двух квадратов тогда и только тогда, когда оно является или квадратом, или числом 2, или простым числом, которое на 1 больше, чем некоторое кратное 4, или произведением нескольких вышеперечисленных чисел. Скорее всего, Жирар опирался лишь на изучение таблиц и не претендовал на то, что может доказать необходимость и достаточность своих условий.



Упражнения
10. Докажите, что 15 не представимо в виде суммы квадратов двух рациональных чисел. (Этот факт упомянут в «Арифметике» древнегреческого математика Диофанта.)
11. Выведите из критерия представимости числа в виде суммы двух квадратов, что если сумма квадратов х2 + y2 целых чисел кратна р2s-1, где s - натуральное число, р — простое число, которое при делении на 4 дает остаток 3, то числа х и у кратны ps.
12. Докажите, что существует бесконечно много натуральных чисел, которые дают остаток 1 при делении на 4, но не представимы в виде суммы квадратов двух целых чисел.
13. а) Для любого делителя d числа n2 + 1, где существует бесконечно много таких что m2 + 1 кратно d. Докажите это. 6) Сколько существует натуральных чисел n < 1000, для которых n2 + 1 кратно 65?
14. Из леммы 2 и теоремы 3 выведите, что число вида n2 + 1, где не имеет ни одного делителя вида 4k - 1, где
15. Докажите, что если х, у, z — целые числа и 4ху - х - у = z2, то (Это упражнение придумал Л. Эйлер.)
16. а) Никакое число вида m2 + 1 не кратно никакому числу вида n2 - 1, где m, n — целые числа, n > 1. Докажите это. 6) Решите в целых числах уравнение х2у2 = х2 + y2 + z2.

Доказательство леммы 1


В качестве числа m в лемме 1 годится m = (2n)!, т. е. произведение первых 2n натуральных чисел. Чтобы это увидеть, рассмотрим число

(р - 1)! = 1 . 2 . ... . (2n - 1) . (2n) х (2n + 1) . (2n + 2) . ... . (4n - 1) . (4n) =


= 1 . 2 .... . (2n - 1) . (2n) . (р - 2n) х (р - (2n -1)) . ... . (р - 2) . (p - 1).

Оно дает при делении на р такой же остаток, как и число

1 . 2 . ... . (2n-1) . (2n) . (-1)2n . (2n) . (2n- 1) . ... . 2 .1 = m2.

Значит, m2 + 1 при делении на р дает такой же остаток, как и число (р - 1)! + 1. Последнее число кратно р по теореме Вильсона, которая впервые была сформулирована англичанином Эдуардом Варингом (1734 — 1798), а доказана французом Жозефом Луи Лагранжем (1736 — 1813).



Теорема Вильсона. Для любого простого числа р сумма (р - 1)! + 1 кратна р. (Другими словами, произведение 1 . 2 . ... . (р - 1 ) дает остаток (р - 1) при делении на р.)

Доказательство этой теоремы можно узнать, например, из статьи А. Егорова и А. Котовой «Необыкновенные арифметики» (Приложение к журналу «Квант» N 2 за 1994 год).

Итак, мы вывели лемму 1 из теоремы Вильсона. Идея доказательства леммы 2 — разложение на множители m2 + 1 = (m + i)(m - i). Что такое i и что делать дальше, вы узнаете, когда познакомитесь с комплексными числами.

Упражнения
17. Докажите, что числа а) 97! . 1901! - 1; б) 98! . 1900!+1 кратны 1999. Указание. 1999 — простое число.
18. Если р — простое число, р > 2, m = ((р - 1)/2)!, то m2 = (-1)(p+1)/2(modр), т.е. остаток от деления на р числа m2 равен 1, если р = 4n + 3, и равен р - 1, если р = 4n + 1. Докажите это.
19. Докажите, что а) если составное число n > 4, то (n- 1)! кратно n; б) если (n- 1)! + 1 кратно n, где n > 1- натуральное число, то n — простое.


следующая страница >>



Не Шекспир главное, а примечания к нему. Антон Чехов
ещё >>