задача про сумму квадратов
Попалась задачка: решить в целых числах уравнение
x^2 + y^2 = 19451945 (восемь цифр: 1945, повторенное дважды).
Уже после того, как я ее решил (далеко не сразу), погуглил и обнаружил, что есть видео на канале Бориса Трушина, где он находит решение. Сначала перебором, начиная с x, очень близкого к корню из 19451945, и уменьшая, пока не найдется полный квадрат для y^2. Потом более интересным способом, используя разбиение 19451945 на 1945*10001, и удачно подобранные представления этих чисел, в свою очередь, как сумм двух квадратов.
Но если добавить немного базисных знаний про комплексные числа, то можно заодно найти все решения и доказать, что других нет, "за те же деньги". Попробую это вкратце рассказать (так я решил).
Идея в том, чтобы решать это уравнение не в целых числах, а в целых гауссовых числах. Это числа вида x+y*i, где i - мнимая единица. Эта идея оказывается полезной по двум причинам. Во-первых, x^2 + y^2 = (x+yi)(x-yi). Таким образом мы перевели *сумму* двух чисел в *произведение* двух (гауссовых) чисел. Во-вторых, как обычные целые числа раскладываются на простые множители единственным способом, так и гауссовы целые числа раскладываются на множители (простые гауссовые) единственным образом. Доказательство этого опускаю. Это значит, что раз в гауссовых целых числах
(x+yi)(x-yi) = 19451945, то когда мы разложим 19451945 на (гауссовы) простые множители, то оба числа x+yi и x-yi обязаны будут быть какими-то комбинациями этих множителей. И так мы сможем как найти решения, так и доказать, что других не бывает.
19451945 = 1945*10001. Далее делим 1945 на 5, очевидно, и находим 1945=5*389; то, что 389 простое, можно проверить перебором. Чтобы разложить 10001 на множители, не пользуясь компьютером/калькулятором/интернетом, можно пробовать деление на все простые числа, меньшие 100 (если можно как-то легче, я не знаю, как), и так находим: 10001 = 73*137. Всего есть четыре простых множителя: 19451945 = 5*73*137*389.
Однако хотя это простые числа, они необязательно простые *гауссовы* числа. Например, 5 = (2+i)(2-i), и это разложение на простые (гауссовы) множители. Вообще говоря, любое простое число вида 4k+3 является также простым гауссовым, а любое вида 4k+1 раскладывается на произведение простых гауссовых типа (a+bi)(a-bi), где a^2+b^2 равно этому простому числу. У нас есть четыре простых множителя, довольно маленьких, поэтому легко найти полное разложение:
19451945 = 5*73*137*389 = (2-i)(2+i) * (8-3i)(8+3i) * (11-4i)(11+4i) * (17-10i)(17+10i)
После всей этой работы мы знаем, что любое представление 945145 в виде (x+yi)(x-yi) обязано как-то поделить между x+yi и x-yi эти восемь простых гауссовых множителей. Но очевидно, что если взять в одну группу, например x+yi оба числа одной пары, скажем (8-3i) и (8+3i), то оба коэффициента x,y будут делиться на 8^2+3^2=73, а произведение чисел другой группы на 73 делиться никак не сможет, поэтому там не выйдет ровно x-yi. То есть для того, чтобы получились сопряженные произведения x+yi и x-yi, мы обязаны поделить наши восемь множителей на две группы, взяв в каждую группу одного представителя каждой пары: один из 2-i, 2+i, один из 8-3i, 8+3i итд. И тогда автоматически получаются произведения вида x+yi, x-yi, каждое из которых дает решение уравнения вида x^2+y^2 = 19451945.
Всего способов выбрать множители для x+yi есть 16 - четыре выбора из двух в каждой паре, 2 в четвертой степени. Но для каждого из них есть двойник, когда мы меняем все 4 знака, и вместо x+yi получаем x-yi, это те же самые x,y. Поэтому всего есть 8 разных решений, и их легко можно вычислить. Например, если в одну группу возьмем все со знаком -: (2-i)(8-3i)(11-4i)(17-10i), то это выйдет -581-4372i, соответственно 581^2+4372^2 = 19451945.
(для полной точности надо добавить, что мы можем также заменить например 8+/- 3i на 3+/- 8i, и так в других множителях. Но поскольку это эквивалентно умножению на i, которое меняет местами коэффициенты, это не даст никаких новых решений, просто x и y в x^2+y^2 поменяются местами).
x^2 + y^2 = 19451945 (восемь цифр: 1945, повторенное дважды).
Уже после того, как я ее решил (далеко не сразу), погуглил и обнаружил, что есть видео на канале Бориса Трушина, где он находит решение. Сначала перебором, начиная с x, очень близкого к корню из 19451945, и уменьшая, пока не найдется полный квадрат для y^2. Потом более интересным способом, используя разбиение 19451945 на 1945*10001, и удачно подобранные представления этих чисел, в свою очередь, как сумм двух квадратов.
Но если добавить немного базисных знаний про комплексные числа, то можно заодно найти все решения и доказать, что других нет, "за те же деньги". Попробую это вкратце рассказать (так я решил).
Идея в том, чтобы решать это уравнение не в целых числах, а в целых гауссовых числах. Это числа вида x+y*i, где i - мнимая единица. Эта идея оказывается полезной по двум причинам. Во-первых, x^2 + y^2 = (x+yi)(x-yi). Таким образом мы перевели *сумму* двух чисел в *произведение* двух (гауссовых) чисел. Во-вторых, как обычные целые числа раскладываются на простые множители единственным способом, так и гауссовы целые числа раскладываются на множители (простые гауссовые) единственным образом. Доказательство этого опускаю. Это значит, что раз в гауссовых целых числах
(x+yi)(x-yi) = 19451945, то когда мы разложим 19451945 на (гауссовы) простые множители, то оба числа x+yi и x-yi обязаны будут быть какими-то комбинациями этих множителей. И так мы сможем как найти решения, так и доказать, что других не бывает.
19451945 = 1945*10001. Далее делим 1945 на 5, очевидно, и находим 1945=5*389; то, что 389 простое, можно проверить перебором. Чтобы разложить 10001 на множители, не пользуясь компьютером/калькулятором/интернетом, можно пробовать деление на все простые числа, меньшие 100 (если можно как-то легче, я не знаю, как), и так находим: 10001 = 73*137. Всего есть четыре простых множителя: 19451945 = 5*73*137*389.
Однако хотя это простые числа, они необязательно простые *гауссовы* числа. Например, 5 = (2+i)(2-i), и это разложение на простые (гауссовы) множители. Вообще говоря, любое простое число вида 4k+3 является также простым гауссовым, а любое вида 4k+1 раскладывается на произведение простых гауссовых типа (a+bi)(a-bi), где a^2+b^2 равно этому простому числу. У нас есть четыре простых множителя, довольно маленьких, поэтому легко найти полное разложение:
19451945 = 5*73*137*389 = (2-i)(2+i) * (8-3i)(8+3i) * (11-4i)(11+4i) * (17-10i)(17+10i)
После всей этой работы мы знаем, что любое представление 945145 в виде (x+yi)(x-yi) обязано как-то поделить между x+yi и x-yi эти восемь простых гауссовых множителей. Но очевидно, что если взять в одну группу, например x+yi оба числа одной пары, скажем (8-3i) и (8+3i), то оба коэффициента x,y будут делиться на 8^2+3^2=73, а произведение чисел другой группы на 73 делиться никак не сможет, поэтому там не выйдет ровно x-yi. То есть для того, чтобы получились сопряженные произведения x+yi и x-yi, мы обязаны поделить наши восемь множителей на две группы, взяв в каждую группу одного представителя каждой пары: один из 2-i, 2+i, один из 8-3i, 8+3i итд. И тогда автоматически получаются произведения вида x+yi, x-yi, каждое из которых дает решение уравнения вида x^2+y^2 = 19451945.
Всего способов выбрать множители для x+yi есть 16 - четыре выбора из двух в каждой паре, 2 в четвертой степени. Но для каждого из них есть двойник, когда мы меняем все 4 знака, и вместо x+yi получаем x-yi, это те же самые x,y. Поэтому всего есть 8 разных решений, и их легко можно вычислить. Например, если в одну группу возьмем все со знаком -: (2-i)(8-3i)(11-4i)(17-10i), то это выйдет -581-4372i, соответственно 581^2+4372^2 = 19451945.
(для полной точности надо добавить, что мы можем также заменить например 8+/- 3i на 3+/- 8i, и так в других множителях. Но поскольку это эквивалентно умножению на i, которое меняет местами коэффициенты, это не даст никаких новых решений, просто x и y в x^2+y^2 поменяются местами).