Problem 153

Investigating Gaussian Integers

As we all know the equation x²=-1 has no solutions for real x.
If we however introduce the imaginary number i this equation has two solutions: x=i and x=-i.
If we go a step further the equation (x-3)²=-4 has two complex solutions: x=3+2i and x=3-2i.
x=3+2i and x=3-2i are called each others’ complex conjugate.
Numbers of the form a+bi are called complex numbers.
In general a+bi and a−bi are each other’s complex conjugate.

A Gaussian Integer is a complex number a+bi such that both a and b are integers.
The regular integers are also Gaussian integers (with b=0).
To distinguish them from Gaussian integers with b ≠ 0 we call such integers “rational integers.”
A Gaussian integer is called a divisor of a rational integer n if the result is also a Gaussian integer.
If for example we divide 5 by 1+2i we can simplify $\frac{5}{1 + 2 i}$ in the following manner:
Multiply numerator and denominator by the complex conjugate of 1+2i: 1−2i.
The result is $\frac{5}{1 + 2 i} = \frac{5}{1 + 2 i} \frac{1 - 2 i}{1 - 2 i} = \frac{5 (1 - 2 i)}{1 - (2 i)^{2}} = \frac{5 (1 - 2 i)}{1 - (- 4)} = \frac{5 (1 - 2 i)}{5} = 1 - 2 i$ .
So 1+2i is a divisor of 5.
Note that 1+i is not a divisor of 5 because $\frac{5}{1 + i} = \frac{5}{2} - \frac{5}{2} i$ .
Note also that if the Gaussian Integer (a+bi) is a divisor of a rational integer n, then its complex conjugate (a−bi) is also a divisor of n.

In fact, 5 has six divisors such that the real part is positive: {1, 1 + 2i, 1 − 2i, 2 + i, 2 − i, 5}.
The following is a table of all of the divisors for the first five positive rational integers:

n	Gaussian integer divisors with positive real part	Sum s(n) of these divisors
1	1	1
2	1, 1+i, 1-i, 2	5
3	1, 3	4
4	1, 1+i, 1-i, 2, 2+2i, 2-2i,4	13
5	1, 1+2i, 1-2i, 2+i, 2-i, 5	12

For divisors with positive real parts, then, we have: $\sum_{n = 1}^{5} s (n) = 35$ .

For 1 ≤ n ≤ 10⁵, ∑ s(n)=17924657155.

What is ∑ s(n) for 1 ≤ n ≤ 10⁸?

高斯整数的研究

我们都知道方程x²=-1在实数范围内无解。
但如果我们引入虚数i，这个方程将会有两个解x=i和x=-i。
进一步地，方程(x-3)²=-4有两个复数解：x=3+2i和x=3-2i。
x=3+2i和x=3-2i互称为共轭复数。
形如a+bi的数被称为复数。
概括地说，a+bi和a−bi互称为共轭复数。

高斯整数是形如a+bi且a和b均为整数的复数。
一般意义上的整数也是高斯整数（取b=0）。
为了把它们和b ≠ 0的高斯整数区分开来，称它们为“有理整数”。
如果一个高斯整数除有理整数n的结果仍然是高斯整数，则称它为该有理整数的约数。
例如，我们用1+2i除5，按如下方式简化 $\frac{5}{1 + 2 i}$ ：
分子和分母同时乘以1+2i的共轭：1−2i。
结果是： $\frac{5}{1 + 2 i} = \frac{5}{1 + 2 i} \frac{1 - 2 i}{1 - 2 i} = \frac{5 (1 - 2 i)}{1 - (2 i)^{2}} = \frac{5 (1 - 2 i)}{1 - (- 4)} = \frac{5 (1 - 2 i)}{5} = 1 - 2 i$ 。
所以1+2i是5的约数。
注意1+i不是5的约数，因为 $\frac{5}{1 + i} = \frac{5}{2} - \frac{5}{2} i$ 。
同时注意如果高斯整数(a+bi)是有理整数n的约数，那么它的共轭复数(a−bi)也是n的约数。

事实上，5一共有六个实数部分是正数的约数：{1, 1 + 2i, 1 − 2i, 2 + i, 2 − i, 5}。
如下表格列出了前五个正有理整数的所有约数：

n	实数部分是正数的高斯整数约数	约数的和s(n)
1	1	1
2	1, 1+i, 1-i, 2	5
3	1, 3	4
4	1, 1+i, 1-i, 2, 2+2i, 2-2i,4	13
5	1, 1+2i, 1-2i, 2+i, 2-i, 5	12

对于实数部分为正数的约数，我们有： $\sum_{n = 1}^{5} s (n) = 35$ 。

对于1 ≤ n ≤ 10⁵，∑ s(n)=17924657155。

对于1 ≤ n ≤ 10⁸，求∑ s(n)。