На Южном математическом турнире (пользуясь случаем, поздравляю с победой команду солнечного Саранска) выдали следующую лемму. Выходит, не все её знают, так что напомню свой старый пост в книге лиц, в котором из неё выводится Рождественская теорема Ферма.

Лемма (обратное неравенство Коши-Буняковского-Шварца, шорт-лист IMO 1995 A2). Если a,b,c — неотрицательные целые числа и ab-c² неотрицательно, то существуют два вектора x,y с целыми координатами (одной и той же, может быть большой, размерности) такие, что a,b — квадраты их норм, а c — их скалярное произведение. Иначе говоря: если квадратный трёхчлен f(t)=at²+2ct+b неотрицателен на вещественной оси, то его можно представить как сумму квадратов линейных [аффинных, если вам так нравится - ФП] функций с целыми коэффициентами:

f(t) =sum (x_i t+y_i)²

Доказательство леммы. Предположим противное и возьмём контрпример с минимальным c. Если min(a,b,c)=c, то

f(t)=c(t+1)²+(a-c)t²+(b-c) 1² —

искомое представление. Если, скажем, c>a, то возьмем трёхчлен f(t-1), то есть тройку (a, b-2c+a, c-a), по минимальности c она уже не является контрпримером, а из представления в нужном виде трёхчлена f(t-1) получается представление f(t) сдвигом буквы t на 1.

Теперь

Рождественская теорема Ферма. Если p=4k+1 простое, то p есть сумма двух квадратов целых чисел.

Доказательство. При некоторм целом c число p делит c²+1 (простое доказательство: иначе остатки от 2 до 4k-1 по модулю p разбиваются на четвёрки вида (y, - y, 1/y,-1/y)):

ap=c²+1.

Используя лемму, находим векторы x,y с x²=a, y²=p, c=xy=sum(x_i y_i). Возьмем любой индекс i, для которого y_i≠0. Обозначим x_i=X, y_i=Y. Имеем

1-(pX²+aY²-2cXY)=(a-X²)(p-Y²)-(c-XY)²⩾0

(это КБШ для векторов x, y без i-ой координаты).

Умножая на p и подставляя ap=c²+1 в левую часть, получаем
p-(pX-cY)²-Y²⩾0, но левая часть кратна p (и меньше p, так как Y≠0), поэтому она равна 0.