Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/03/21.pdf Дата изменения: Fri Dec 23 19:25:12 2005 Дата индексирования: Tue Oct 2 00:18:05 2012 Кодировка: Windows-1251 Поисковые слова: элементы орбиты

СУММЫ

КВАДРАТОВ

И

ЦЕЛЫЕ

ГАУССОВЫ

ЧИСЛА

21

Теорема 9. Никакое простое число не может быть представлено в виде суммы квадратов двух целых чисел существенно разными (т. е. не получающимися один из другого перестановкой слагаемых) способами. Доказательство. Если бы простое число p имело два 2 2 2 2 существенно разных представления, p = a + b = c + d , то разложения p = (a + bi)(a bi) = (c + di)(c di) противоречили бы теореме 8.
Упражнение 34 (М1288*). Докажите, что число 1000009 = 235 2 + 9722 составное.

следующим образом: 65 = (2 + i)(3 + 2i) (2 i)(3 2i)= (4 + 7i) (4 7i)= = 4 2 + 72 = (2 + i)(3 2i) (2 i)(3 + 2i) =
2 2 = (8 i) (8 + i) = 8 + 1 .

Можно обойтись в доказательстве теоремы 9 и без комплексных чисел. Предположим, что простое число p двумя существенно разными (т. е. отличающимися не только порядком слагаемых) способами разложено в сумму квадратов натуральных чисел: p=a +b =c +d. Тогда a2 -b2 и c - d mod p . Следовательно, a c -b 2 - d2 mod p , т. е. число a2 c2 b 2 d2 кратно p. (Если рассуждения со сравнениями по модулю p непривычны и потому подозрительны, вы можете получить то 22 22 же самое, рассматривая тождество a c b d =
2 2 2 2 2 2

Понимаете? По-разному группируя множители, получили два разных разложения! Следующий пример число 25. Тот, кто решил упражнение 1, знает, что 25 наименьшее число, двумя способами представимое в виде суммы квадратов двух целых чисел. Оба эти разложения легко получить, поразному группируя множители:

25 = 2 + i

b g b2 - ig = b3 + 4ig b3 - 4ig = 3 = b2 + i gb2 - i g b2 + i gb2 - i g
2 2

2

+4 =
2 2

2

=55 = 5 + 0 .

e je jb
2

g

b

g

22

Последний пример число 5746. Как мы хорошо знаем, 2 всякому представлению 5746 = a + b2 соответствует разложение 5746 = (a + bi)(a bi) на сопряженные множители. Поэтому разложим рассматриваемое число сначала на простые натуральные, а затем и на простые гауссовы множители:
5746 = 2 13 17 = = 1 + i 1 - i 3 + 2i
2

= a c + d a + b d .) Поскольку число p простое, из делимости произведения (ac + bd)(ac bd) на p следует, что один из множителей кратен p. Если число ac + bd кратно p, то воспользуемся формулой (1):

e

2

2

je

2

2

j

2

b gb gb

gb
2

3 - 2i

gb
2

4+i 4-i .

gb

g

Теперь мы должны из нескольких этих множителей составить a + bi, да так, чтобы произведение остальных множителей равнялось a bi. Это нетрудно сделать:
a + bi = 1 + i 3 + 2i a - bi = 3 - 2i

p2 = ac + bd

b

g +b
2

2 ad - bc .

g

Если ad bc 0, то противоречие очевидно, ибо первое 2 слагаемое ac + bd кратно p2 и потому не меньше p2 . Если же ad bc = 0, то ad = bc. Поскольку как числа a и b, так и числа c и d взаимно просты, имеем a = c и d = = b. Случай, когда ac bd кратно p, можно рассмотреть 2 аналогично, воспользовавшись формулой p2 = ac - bd + 2 + ad + bc .

b

g

b gb b1 - igb

gb gb
2 2

4 + i = -45 + 61i ,
4 - i = -45 - 61i .
2

g g

При этом, разумеется, 452 + 61 = 2025 + 3721 = 5746. Легко найти и еще два варианта:

a + bi = 1 + i 3 + 2 i 3 - 2 i 4 + i = 39 + 65i
или
a+
2

b

g

b

g

b gb gb gb g bi = b1 + igb3 - 2ig b4 + ig = 75
2 2

- 11i .

Упражнение 35. Представьте число 1000009 = 2352 + 9722 в виде произведения двух отличных от 1 натуральных чисел.

Итак, простое число нельзя двумя существенно разными способами представить в виде суммы квадратов двух натуральных чисел. Число, единственным образом представимое в виде суммы квадратов двух натуральных 2 2 чисел, не всегда является простым: 10 = 1 + 3 , 25 = 2 2 = 3 + 4 . Легко сформулировать условия, при которых число имеет единственное представление в виде суммы двух квадратов. Но давайте не будем тратить на это свои силы, а ответим на более общий вопрос.

Сколькими способами число можно представить в виде суммы двух квадратов?
В III веке нашей эры греческий математик Диофант не только знал, что число 65 представимо двумя способами, но и объяснял это тем, что 65 является произведением чисел 13 и 5, каждое из которых сумма двух квадратов. Комплексных чисел Диофант не знал, иначе он непременно выписал бы разложения 5 = (2 + i)(2 i), 13 = =(3 + 2i)(3 2i) и продолжил бы свои объяснения
6 Квант ? 3

Они приводят к представлениям 39 + 65 = 1521 + 4225 = = 5746 и 752 + 112 = 5625 + 121 = 5746. Никаких других представлений нет (попытайтесь их придумать и довольно скоро поймете причину этого). Аналогично можно найти число представлений в виде суммы двух квадратов любого натурального числа n = a a = 2 a p1 1 K pr r Q , где p1 ,..., pr попарно различные простые числа, каждое из которых дает остаток 1 при делении на 4, Q число, не имеющее простых делителей кроме тех, которые дают остаток 3 при делении на 4. А именно, если Q не является точным квадратом, то n не представимо в виде суммы двух квадратов; если же Q точный квадрат, то, применив необходимое число раз теорему 2, получаем: количество представлений числа n в виде суммы двух квадратов равно количеству представa a лений числа m = 2a p1 1 K pr r в виде суммы двух квадратов. Формулу для этого количества нашел немец Петер Густав Лежен Дирихле (18051859). Теорема 10. Количество представлений числа m в виде суммы квадратов двух целых чисел равно [(( a1 + 1) ... ... ( ar + 1)+1)/2]. (Если число сомножителей равно 0, то произведение считается равным 1. Представления, отличающиеся порядком слагаемых, не различаются.)