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

Теорема Ферма — Эйлера или теорема о представлении простых чисел в виде суммы двух квадратов гласит [1] :

Любое простое число p = 4 n + 1 <displaystyle p=4n+1> , где n <displaystyle n> — натуральное число, представимо в виде суммы квадратов двух натуральных чисел.

p = 4 n + 1 , n ∈ N ⇒ p = x 2 + y 2 , <displaystyle p=4n+1,nin mathbb Rightarrow p=x^<2>+y^<2>,>

где p <displaystyle p> — простое число.

В иностранной литературе это утверждение часто называют рождественской теоремой Ферма, так как она стала известна из письма Пьера Ферма, посланного 25 декабря 1640 года.

5 = 1 2 + 2 2 <displaystyle 5=1^<2>+2^<2>> , 13 = 2 2 + 3 2 <displaystyle 13=2^<2>+3^<2>> , 17 = 1 2 + 4 2 <displaystyle 17=1^<2>+4^<2>> , 29 = 2 2 + 5 2 <displaystyle 29=2^<2>+5^<2>> , 37 = 1 2 + 6 2 <displaystyle 37=1^<2>+6^<2>> , 41 = 4 2 + 5 2 <displaystyle 41=4^<2>+5^<2>> .

Из этого утверждения при помощи тождества Брахмагупты выводится общее утверждение:

Натуральное число представимо в виде суммы двух квадратов (целых чисел) тогда и только тогда, когда любое простое число вида 4 k + 3 <displaystyle 4k+3> входит в его разложение на простые множители в чётной степени.

Иногда именно этот факт подразумевается под теоремой Ферма — Эйлера.

Содержание

История [ править | править код ]

Впервые это утверждение обнаружено у Альбера Жирара в 1632 году. Пьер Ферма объявил в своём письме к Мерсенну (1640), что он доказал данную теорему, однако доказательство не привёл. Через 20 лет в письме к Каркави (от августа 1659 года) Ферма намекает, что доказательство основывается на методе бесконечного спуска.

Первое опубликованное доказательство методом бесконечного спуска было найдено Леонардом Эйлером между 1742 и 1747 годами. Позднее доказательства, основанные на иных идеях, дали Жозеф Лагранж, Карл Гаусс, Герман Минковский, Якобшталь и Дон Цагир. Последним приведено доказательство, состоящее из одного предложения [2] .

Доказательства [ править | править код ]

Одно из самых коротких доказательств придумано немецким математиком Доном Цагиром [3] :

Инволюция конечного множества S = < ( x , y , z ) ∈ N 3 : x 2 + 4 y z = p > <displaystyle S=<(x,y,z)in mathbb ^<3>:x^<2>+4yz=p>> , определённая как

2yend>>"> ( x , y , z ) → < ( x + 2 z , z , y − x − z ) , x y − z ( 2 y − x , y , x − y + z ) , y − z x 2 y ( x − 2 y , x − y + z , y ) , x >2 y <displaystyle (x,y,z)
ightarrow <egin(x+2z,z,y-x-z),&x 2yend>> 2yend>>"/>

имеет ровно одну неподвижную точку (а именно ( 1 , 1 , k ) <displaystyle (1,1,k)> , так как p = 4 k + 1 <displaystyle p=4k+1> — простое), так что | S | <displaystyle |S|> нечётно и инволюция ( x , y , z ) → ( x , z , y ) <displaystyle (x,y,z)
ightarrow (x,z,y)> также имеет неподвижную точку.

Также есть доказательство через теорему Вильсона, придуманное Акселем Туэ [4] .

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

1. Исследование (неполная индукция). При n=1, очевидно, рассматривать задачу не имеет смысла (так как квадрат натурального числа равен самому себе).

При n=2 чисел m, удовлетворяющих условию задачи найдется достаточно, это так называемые пифагорейские числа, наименьшая по величине составляющих ее чисел тройка – длины сторон египетского треугольника: 3, 4, 5 (5 2 = 3 2 + 4 2 ). Умножая каждое из этих чисел на одно и то же натуральное число, получим тройку натуральных чисел, квадрат одного из которых равен сумме квадратов двух других. Значит, при n=2, в роли числа m может быть любое натуральное число кратное 5.

Еще одна известная любому школьнику тройка пифагорейских чисел: 5, 12, 13 (13 2 = 12 2 + 5 2 ), содержит число 5, квадрат которого сам представляется в виде суммы квадратов двух различных натуральных чисел. Т.е., в этом случае можно записать 13 2 = 12 2 + 5 2 = 12 2 + 4 2 + 3 2 и при n=3 в роли числа m можно взять 13, квадрат которого представляется в виде суммы квадратов как двух, так и трех различных натуральных чисел (или любое натуральное число, кратное 13).

Для n=4 попробуем определить такие натуральные числа x и y, для которых x 2 = y 2 + 13 2 , тогда квадрат числа x можно будет представить в виде суммы квадратов двух, трех и четырех различных натуральных чисел:x 2 = y 2 + 13 2 = y 2 + 12 2 + 5 2 = y 2 + 12 2 + 4 2 + 3 2 .

Запишем равенство x 2 = y 2 + 13 2 в виде x 2 — y 2 = 13 2 и применив формулу разности квадратов получим (x — y)(x + y)= 13 2 = 169. В виду того, что число 169 имеет только три натуральных делителя: 1, 13 и 169, выбрать удовлетворяющие нашему требованию x и y можно единственным способом – если считать, что x — y =1, а x + y = 169 (в виду нечетности 169 это возможно). Итак, разделив 168, на 2 получим y = 84, а соответственно, x = 85. То есть, для n=4 имеем число m=85, квадрат которого можно представить в виде суммы квадратов 2-х, 3-х или 4-х различных натуральных чисел.

Этот процесс, очевидно, можно продолжить для любого натурального n. Например, на следующем его шаге из равенств x-y = 1 и x + y = 85 2 = 7225 найдем число 3613, квадрат которого можно представить в виде суммы квадратов 2-х, 3-х, 4-х или 5-и различных натуральных чисел. И т. д.

Итак, описанный выше процесс построения последовательности натуральных чисел, удовлетворяющих условию задачи, дает нам возможность утверждать, что для любого натурального числа n мы сможем "построить” нужное m (но в строго математическом смысле он еще не является доказательством). Заметим, что "успешность” нашего процесса базируется на том, что на каждом его шаге мы получаем нечетное число m (квадрат которого тоже нечетное число). Вследствие этого система уравнений x-y = 1 и x + y = m 2 имеет решение в натуральных числах, и при этом наше следующее m (т. е. число x) тоже оказывается нечетным числом.

2. Доказательство (полная индукция). Выше установлено, что при n=2 мы имеем нечетное число m=5, квадрат которого можно представить в виде суммы квадратов 2 натуральных чисел: 5 2 = 3 2 + 4 2 .

Допустим, что для некоторого натурального n=k существует такое нечетное число m_k = 2p + 1 (p — натуральное число), квадрат которого можно представить в виде суммы квадратов двух, трех,…, k различных натуральных чисел. Тогда из системы уравнений

найдем натуральные числа и , для которых . То есть, квадрат числа m_k+1 можно представить в виде суммы квадратов двух различных натуральны чисел m_k и y. Так как квадрат m_k можно представить в виде суммы квадратов двух, трех, …, k, то, соответственно, получим запись квадрата m_k+1 еще и в виде суммы квадратов трех, четырех,…, k+1, различных натуральных чисел. При этом число m_k+1 тоже нечетно.

Мы доказали, что из предположения о том что утверждение задачи справедливо при некотором натуральном n=k следует, что это же утверждение справедливо при следующем значении n=k+1. Следовательно, по принцип математической индукции мы ожжем утверждать справедливость этого утверждения для любого натурального n.

Задача

Еще в древнем Египте была известна формула для суммы последовательных натуральных чисел:

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

Найдите формулу для суммы а) квадратов (1^2+2^2+ldots+n^2); б) кубов (1^3+2^3+ldots+n^3); в) четвертых степеней (1^4+2^4+ldots+n^4).

Подсказка 1

Начните c эксперимента: вычислите первые несколько сумм ((1^2+2^2), (1^2+2^2+3^2) и т. д. хотя бы до (n=5)). После этого попробуйте найти закономерность.

Подсказка 2

Экспериментальные данные полезно записать в виде таблицы:

(n)	(1)	(2)	(3)	(4)	(5)	(6)	(7)
(1^<phantom1>+ldots+n^<phantom1>)	(1)	(3)	(6)	(10)	(15)	(28)	(35)
(1^2+ldots+n^2)	(1)	(5)	(14)	(30)	(55)	(91)	(140)
(1^3+ldots+n^3)	(1)	(9)	(36)	(100)	(225)	(784)	(1225)
(1^4+ldots+n^4)	(1)	(17)	(98)	(354)	(979)	(2275)	(4676)

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

Подсказка 3

Если у чисел в двух строках постоянно появляются общие делители (например, 10 и 30 делятся на 10, 15 и 55 — на 5, 28 и 91 — на 7 и т. д.), то полезно изучить отношение этих чисел. Что за последовательности получаются? (Удобно добавить в таблицу из второй подсказки соответствующие строки.)

Решение

Как и предлагалось в последней подсказке, изучим отношение первых двух строк.

(n)	(1)	(2)	(3)	(4)	(5)	(6)	(7)
(S_1)	(1)	(3)	(6)	(10)	(15)	(21)	(28)
(S_2)	(1)	(5)	(14)	(30)	(55)	(91)	(140)
(S_2/S_1)	(1)	(5/3)	(7/3)	(3)	(11/3)	(13/3)	(5)

Теперь нетрудно заметить закономерность: с увеличением (n) на 1 частное увеличивается на (2/3), то есть это частное равно ((2n+1)/3). Вместе с формулой для суммы (1+2+ldots+n) это дает (гипотетический) ответ

С суммами кубов дело обстоит даже проще, чем с квадратами — глядя на таблицу естественно предположить, что (S_3=S_1^2), то есть

Заметно сложнее угадать формулу для суммы четвертых степеней. В отличие от предыдущих случаев, у (S_4(n)) практически не видно общих делителей с (S_1(n)) (кроме двойки). Зато можно заметить, что 14 и 98 делятся на 7, 55 и 979 — на 14. Посмотрим на отношение (S_4/S_2):

(n)	(1)	(2)	(3)	(4)	(5)	(6)
(S_2)	(1)	(5)	(14)	(30)	(55)	(91)
(S_4)	(1)	(17)	(98)	(354)	(979)	(2275)
(S_4/S_2)	(1)	(17/5)	(7)	(59/5)	(89/5)	(25)

Видно, что после домножения этого отношения на 5 получится последовательность целых чисел: 5, 17, 35, 59, 89, 125. Тут уже нельзя сказать, что разность соседних чисел неизменна. Но если выписать эти разности: 12, 18, 24, 30. то закономерность сразу становится видной!

Таким образом, гипотеза состоит в том, что

Итак, стало понятно, какие должны быть ответы, но как их доказать?

И что вообще значит, что какое-то выражение (P(n)) дает формулу для суммы (1^2+ldots+n^2)?

Это значит, что (P(1)=1), (P(2)=P(1)+2^2), . (P(n)=P(n-1)+n^2). То есть все сводится к быть может утомительному, но прямолинейному вычислению:

Аналогичным образом (говоря формально — по индукции) можно доказать найденные выше формулы для (S_3(n)) и (S_4(n)).

Послесловие

Геометрическое доказательство формулы для суммы (1+2+ldots+n)

Видимо наиболее наглядный способ вычислить сумму (1+2+ldots+n) — геометрический: об этой сумме можно думать как о треугольном числе, то есть площади «пиксельного» (составленного из единичных квадратиков) равнобедренного прямоугольного «треугольника» со стороной (n). Из двух таких треугольников легко составить прямоугольник размера (n imes(n+1)), откуда и получается ответ (n(n+1)/2) (половина площади прямоугольника).

Пирамидка, составленная из квадратов со стороной (1), (2), …, (n)

Подобным образом можно вычислить и сумму (1^2+2^2+ldots+n^2): ее можно проинтерпретировать как объем пирамиды из кубиков (нижний слой которой состоит из (n^2) кубиков, следующий — из ((n-1)^2) кубиков и т. д.), после чего сложить из шести таких пирамид параллелепипед (n imes(n+1) imes(2n+1)). Как это сделать, можно посмотреть на сайте «Математические этюды».

Есть геометрические доказательства и у позволяющего вычислить сумму кубов замечательного равенства (1^3+2^3+ldots+n^3=(1+2+ldots+n)^2). Одно из них можно посмотреть на youtube-канале Think Twice, см. также подборку «доказательств без слов» в «Кванте» №11 за 2017 год.

Заметим, однако, что формула для суммы четвертых степеней не раскладывается (в отличие от предыдущих) на простые линейные множители. Видимо из-за этого ее не получается найти методами геометрического суммирования и открыта она была примерно на 1000 лет позже, чем формула для суммы кубов (известная уже в античности).

Чтобы продвинуться дальше, полезно задуматься, что мы вообще надеемся увидеть в качестве ответа. Не любое алгебраическое выражение можно разложить на достаточно простые множители, но всегда можно, наоборот, раскрыть все скобки и привести подобные. В изученных нами случаях получаются следующие многочлены от (n):

Практически сразу возникает гипотеза, что вообще для любого (k) сумма (1^k+2^k+ldots+n^k) равна многочлену от (n), который начинается с (frac1n^) (в этом выражении изучавшие математический анализ сразу узнают первообразную того, что мы суммируем), дальше идет (frac12n^k) и члены еще меньших степеней.

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

В первой половине XVII века Иоганн Фаульхабер смог найти формулы для сумм (1^k+2^k+ldots+n^k) до (k=17) (интересную попытку реконструкции рассуждений Фаульхабера опубликовал Дональд Кнут). Вот несколько из таких формул:

Коэффициенты при (n^) и при (n^) обсуждались выше. Подумав некоторое время вы наверняка угадаете формулу для коэффициентов при (n^) и (n^), а быть может, — и для коэффициента при (n^).

Возникает надежда на общую (работающую для произвольного (k)) формулу для (S_k(n)). И такую формулу нашел в конце XVII века Якоб Бернулли. В нее входит последовательность так называемых чисел Бернулли ((B^0=1), (B^1=1/2), (B^2=1/6), . ), а саму формулу можно записать символически очень коротко:

Понимать эту запись следует следующим образом. Нужно раскрыть формально в выражении ((n+B)^) скобки, после чего начать воспринимать (B^m) не как степень переменной (B), а как (m)-е число Бернулли. Например:

Если поверить в эту (крайне странную, на первый взгляд) процедуру, то будет ясно и как вычислять числа Бернулли: при подстановке (n=1) получается равенство (1=frac<(1+B)^-B^>), позволяющее найти (B^k), если числа Бернулли с меньшими номерами уже известны. В таблице ниже приведены несколько первых чисел Бернулли.

(m)	(0)	(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)	(9)	(10)	(11)	(12)	(13)	(14)
(B^m)	(1)	(frac12)	(frac16)	(0)	(-frac1<30>)	(0)	(frac1<42>)	(0)	(-frac1<30>)	(0)	(frac5<66>)	(0)	(-frac<691><2730>)	(0)	(frac76)

Замечательным образом те же самые числа Бернулли возникают и в квадратурных формулах для вычисления приближенных значений интегралов, и при вычислении бесконечных сумм типа (1+frac14+frac19+frac1<16>+ldots=frac<pi^2>6) (то есть значений знаменитой дзета-функции), и в комбинаторике, и в теории чисел, и в топологии.

Литература по теме:
1) Д. Пойа. Математика и правдоподобные рассуждения (М.: Наука, 1975). — Мало где можно прочитать не о конкретной области математики, а о том, как вообще решать новую для себя математическую задачу. Подсказки и решение выше по существу следуют главе 7 этой замечательной книги.
2) Интервью с академиком И. М. Гельфандом // Квант, 1989, № 1, стр. 3–12. — В приведенном выше решении сделана попытка объяснить, как некоторые формулы для сумм степеней мог бы искать любой человек. Интересующимся математикой может быть интересно прочитать, как такую задачу решал в школьные годы один из выдающихся математиков XX века (собственно про это — небольшой фрагмент на стр. 8–9, но все интервью интересное).
3) В. С. Абрамович. Суммы одинаковых степеней натуральных чисел // Квант, 1973, № 5, стр. 22–25. — Можно прочитать доказательство формулы для суммы степеней (из конца послесловия), использующее, по сути, только бином Ньютона.
4) Г. А. Мерзон. Алгебра, геометрия и анализ сумм степеней последовательных чисел // Математическое просвещение, сер. 3, вып. 21 (2017), стр. 104–118. — Подробная статья о разных взглядах на задачу о суммировании степеней.
5) Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика (М.: Мир, 1998). — В учебнике, написанном по лекциям знаменитого Дональда Кнута, обсуждается и задача о суммировании степеней, и числа Бернулли.