Какие натуральные числа представимы в виде суммы квадратов целых чисел:
n=x*x+y*y (1)
Мне приходилось объяснять решение этой задачи для простых чисел вида p=4m+1 семикласснику. Несмотря на простоту и многочисленные применения, ее не найдешь ни в школьных курсах, ни в курсах математики для вузов.
Решение лучше изложить вводя Гауссовые числа. Я не знаю, ввели в школьную математику комплексные числа или нет. Поэтому обойдусь без них. Вначале докажем мультипликативность множества натуральных чисел, представимых в виде суммы двух квадратов. Пусть
n1=x1*x1+y1*y1, n2=x2*x2+y2*y2. (2)
Мультипликативность множества означает, что если два числа n1,n2 принадлежат этому множеству, то их произведение так же принадлежит этому множеству, т.е. из (1) следует
n3=n1*n2= (x1*x1+y1*y1)(x2*x2+y2*y2)=(x1*x2-y1*y2)^2+(x1*y2+x2*y1)^2. (3)
Соотношение (3) легко проверяется, так как при возведении в квадрат два члена, не являющиеся квадратами, уничтожаются. Обозначим величины в правой части (3) через
x3=x1*x2-y1*y2, y3=x1*y2+x2*y1. (4)
Для тех, кто знаком с комплексными числами отметим, что
x3+iy3=(x1+iy1)(x2+iy2), n1=(x1+iy1)*(x1-iy1), n2=(x2+iy2)(x2-iy2).
Через представление комплексных чисел в виде векторов на плоскости легче и нагляднее выводятся многие теоремы из школьной геометрии.
Отметим, что квадрат нечетного числа дает остаток 1 при делении на 8, а квадрат четного числа делится на 4. Поэтому, если нечетное число n представимо в виде суммы двух квадратов n=x*x+y*y, то одно из них нечетное, другое четное, а само число n дает остаток 1 при делении на 4. Если четное число n=2m=x*x+y*y, не делящееся на 4 представляется в виде суммы двух квадратов, то x,y нечетные числа, m при делении на 4 дает остаток и представляется в виде суммы двух квадратов:
m=x1*x1+y1*y1, x1=(x+y)/2, y1=(x-y)/2.
Если число n=4m=x*x+y*y, делящееся на 4 представляется в виде суммы двух квадратов, то x,y четные числа, и m=(x/2)*(x/2)+(y/2)*(y/2).
Таким образом представление четных чисел в виде суммы двух квадратов сводится к представлению нечетных чисел в виде суммы двух квадратов.
Сейчас решим задачу для простых чисел р. Для деления представления, аналогичного делению на 2 выше, требуется свойство: Если a не делится на простое число р, то существует единственное натуральное число b<p, что ab=1 по модулю р. Можем считать, что а так же натуральным числом меньше р. Если а=1, то b=1. Если a>1, возводя в разные степени и вычисляя остатки, получим равенство a^n=a^m, n>m+1. Тогда ab=1, где b=a^{n-m-1} mod p.
Выше отметили, что нечетное число, дающее остаток 3 при делении на 4 не представимо в виде суммы двух квадратов. Рассмотрим простое число р с остатком 1 при делении на 4. Пусть r=(p-1)/2, s=r! mod p. Вычислим остаток при делении числа (р-1)! на р двумя способами. Первый способ - объединяя в пары, для которых ab=1 mod p. Для чисел 1 и p-1 парами служат сами 1 и р-1, т.е. они остаются без пары в произведении. Поэтому (р-1)! равно 1*(p-1)*...(ab)...=p-1 mod p. Таким образом доказали теорему Вильсона
(p-1)!+1 делится на р. (5)
Второй способ - объединим в пары а, р-а. Количество таких пар r=(p-1)/2 четное число, поэтому
(p-1)!=r!*r! mod p =s*s mod p.
Если s>p/2, можем заменить на p-s и считать, что s<=(p-1)/2. Из (5) следует, что
s*s+1 делится на р и s*s+1<p*p/4 (6).
Если р=5 находим s=2 и s*s+1=5=x*x+y*y.
Для единственности представления в дальнейшим посчитаем, что х нечетное натуральное число, y четное натуральное число.
Если р=13 находим s=5 и s*s+1=26=2*13. Делением на 2 получим x=(5+1)/2=3, y=(5-1)/2=2 и 13=3*3+2*2. Решение единственное с учетом нашего соглашения.
Если р=17 находим s=4 и 1+s*s=17 и решение единственное.
Если р=29 находим s=12 и 1+s*s=145=5*29. Нам надо делит на 5=1*1+2*2.
Общий метод деления n=x1*x1+y1*y1=mp на p=x*x+y*y. Так как решение для простого р единственное с точностью нашего соглашения выполняется одно из условий x1=+-x=x2 mod p, y1=+-y=-y2 mod p или x1=+-y=-y2 mod p, y1=+-x=-x2 mod p.
В первом случае x3=(x1*x2-y1*y2)=x4*p, y3=x1*y2+y1*x2=y4*p целые и делятся на р, во втором x3 и y3 меняются ролями. При этом x3*x3+y3*y3=np=mp*p. Отсюда получаем
m=x4*x4+y4*y4 (7).
Так доказывается теорема Лагранжа о том, что натуральное число n представляется в виде суммы двух квадратов тогда и только тогда, когда в качестве делителей нечетные числа вида p=4k+3 имеет только в четной степени. Общее количество решений x^2+y^2=n=2^kp_1^{k_1}...p_l^{k_l} в целых числах равно 4N(n), где N(n) мультипликативная функция, определенная на степенях по формуле
N(2^k)=1, N(p1^k)=k+1, N(p3)^k=(1+(-1)^k)/2. (8)
Здесь p1=1 mod 4, p3=3 mod 4.
Эта теорема имеет отношение к вычислению целых точек в круге большого радиуса и дзета функции с характером 1 на простых числах первого вида р1 и -1 на простых числах второго вида р3.