Задача 153
Исследование целых чисел Гаусса

Как известно, уравнение x2)=-1 не имеет решений в области действительных значений x.
Однако, если ввести мнимое число i, то у такого уравнения будет два решения: x=i и x=-i.
Если продолжить, то уравнение (x-3)2=-4 имеет два комплексных решения: x=3+2i и x=3-2i.
x=3+2i и x=3-2i, которые называют сопряженными друг другу.
Числа вида a+bi принято называть комплексными числами.
В общем случае, числа a+bi и abi являются комплексно-сопряженными.

Целое Гаусса - это такое комплексное число a+bi, для которого a и b являются целыми числами.
Обычные целые числа также являются целыми Гаусса (при b=0).
Для того чтобы отличить такие числа от целых Гаусса, у которых b ≠ 0, будем называть их "рациональными целыми числами."
Целое Гаусса называют делителем рационального целого числа, если результат деления также является целым Гаусса.
К примеру, если мы разделим 5 на 1+2i, то полученное выражение можно упростить следующим способом:
Домножим числитель и знаменатель дроби на комплексно сопряженное значение числа 1+2i: 1−2i.
Получим .
Таким образом, 1+2i является делителем числа 5.
Обратите внимание, что 1+i не является делителем числа 5, поскольку .
Также заметьте, что если целое Гаусса (a+bi) является делителем рационального целого числа n, то комплексно сопряженное ему число (abi) также будет являться делителем n.

Между прочим, для числа 5 существует 6 делителей с положительной вещественной частью: {1, 1 + 2i, 1 − 2i, 2 + i, 2 − i, 5}.
Ниже приведена таблица всех делителей для первых пяти положительных рациональных целых чисел:

n Делители целых Гаусса
с положительной веществ. частью
Сумма s(n)
этих делителей
111
21, 1+i, 1-i, 25
31, 34
41, 1+i, 1-i, 2, 2+2i, 2-2i,413
51, 1+2i, 1-2i, 2+i, 2-i, 512

В таком случае, для делителей с положительными вещественными частями, мы можем найти следующую сумму: .

При 1 ≤ n ≤ 105, s(n)=17924657155.

Чему равна сумма s(n), если 1 ≤ n ≤ 108?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net