2010年4月wayne提问 :
如果,正整数a,b,N,满足,a^2-ab+b^2=N^2
试问,1\le a\lt b\lt 10^{100}以内的互质的解有多少组?
最终hujunhua通过利用Eisenstein整环给出了一个对于给定的N上面方程正整数解数目的公式, 并且给出了原理分析。

公式推导

看到这个信息,hujunhua快速给出了如下结论:
a、b互质时,N有且只能有1(mod3)的质因数。这是数论中关于Z(\omega)的一个基本定理。
当N有k个1(mod3)的质因子时,a^2-ab+b^2=N^2的互质解(a,b)对数为2^{k-1}
并且他认为:
在算法上,这个问题与求本原勾股数完全相同。关于本原勾股数的两个公式:
1、通解公式:a=|u^2-v^2|, b=2uv, c=u^2+v^2, 式中GCD(u, v)=1, u, v一奇一偶。
2、计数公式:c只含有1(mod4)的质约数,当c有k个1(mod4)的质约数时,本原(a,b)对有2^{k-1}个。
wayne的问题中也有对应的通解公式和计数公式,它们对优化算法的作用应该是完全一样的。

wayne选择特殊的N对hujunhua的结论进行验证:

比如当N=7\times 13\times 19\times 31\times 37\times 43
其解有2^5=32组,如下:
{a,b}:

{5, 9237},      {157, 9312},         {368, 9413},       {873, 9640},
{880, 9643},        {960, 9677},        {1063, 9720},       {1383, 9848},
{1565, 9917},       {1592,   9927}, {1752, 9985},       {1933, 10048},
{2277, 10160},  {2435,   10208},    {2640, 10267},  {2687, 10280},
{2787, 10307},  {3127, 10392},  {3272, 10425},  {3355, 10443},
{3625, 10497},  {3707,   10512},    {3953, 10553},  {4103, 10575},
{4177, 10585},  {4272, 10597},  {4297, 10600},  {4755, 10643},
{4833, 10648},  {4925, 10653},  {4968, 10655},  {5295, 10663}

mathe认为可以有通解:
i)(u,v)=1,
\begin{cases}b=4uv\\a=3u^2-v^2+2uv\\N=3u^2+v^2\end{cases}
ii)(u,v)=1,
\begin{cases}b=4uv\\a=u^2-3v^2+2uv\\N=u^2+3v^2\end{cases}
当然我们还需要限定条件1\le a\lt b,还有可能有公共的因子2需要消去

然后hujunhua给出了改进的公式:
{a, b}={u^2-v^2, 2uv-v^2}
N=u^2-uv+v^2
u\gt v\gt 0, Gcd(u,v)=1, u\ne -v(\mod3)

Eisenstein整环简介

hujunhua给出:
Z(\omega)及丢番图方程a^2-ab+b^2= N^2简介

一、Eisenstein整数环Z(\omega)简介。

【定义1】(Eisenstein整数环)Z(\omega):={a+b\omega|a, b\in Z}\omega是3次单位根,满足\omega^3=1,\omega^2+\omega+1=0.
注1: \omega的共扼根\omega^{\prime}=\omega^{-1}=\omega^2, 这对共轭复根具有平等对称的性质,随便取哪个当作\omega定义Z(\omega)都是一样的,因为有\omega+\omega^{\prime}=-1使得Z(\omega^{\prime})=Z(\omega)。故Z(\omega)中的数也并行采用a+b\omega^{\prime}的形式,有互易转换a+b\omega=(a-b)-b\omega^{\prime}.
在下文中,如用一个字符来表示Z(\omega)中的数,不作声明时都用z(可带下标)。
【定义2】(范数)对于z= a+b\omega,N(z):=|z|^2=(a+b\omega)(a+b\omega^{\prime})=a^2-ab+b^=:a\otimes b ,称为z的范数。
注:\otimes是为了简化书写而引入的一个二元运算符号。
【定义3】(单位元)范数等于1的Eisenstein整数称为Z(\omega)的(乘法)单位元。
注1:Z(\omega)中有6个单位元: \pm 1, \pm\omega, \pm\omega^{\prime},以下用 \epsilon不定代指单位元。
注2:如果z_1=\epsilon z_2,就称z_1z_2相伴。
【基本性质1】作为环,Z(\omega)对加、减、乘法封闭。值得一提的是对乘法封闭的意义,即对任意的a+b\omega与c+d\omega, 存在e+f\omega=(a+b\omega)(c+d\omega)。由于降次公式\omega[sup]2[/sup]=-1-\omega,这是显然的。取范数可得代数恒等式
(a\otimes b)(c\otimes d)=(ac-bd)\otimes (da+bc+bd)
胡子评曰:恒等式“两平方和乘积=两平方和”与此具有相似的背景和意义,它们在初等代数中都不是显然的,仿佛灵光一闪间妙手偶得之,但在Z(i)和Z(\omega)中一点也不惊奇,就跟1+1=2差不多。从高端看初等的优势于此可见一斑。
【基本性质2】Z(\omega)中成立算术基本定理,并且是唯一分解的整环。
注:Z(\omega)中的素数有3类:
1) \omega-\omega^{\prime} =:\rho, 具有性质\rho=\omega-\omega^{\prime}=-(\omega^{\prime}-\omega)=-\rho^{\prime}, 所以\rho^2=-N(\rho)=-3。可见3=-\rho^2不是Z(\omega)中的素数。
2) a+b\omega, a\otimes b=1(mod6)的素数。即6m+1形的自然素数都不是Z(\omega)中的素数,都可以唯一地分解为Z(\omega)中一对共扼素数a+b\omegaa+b\omega^{\prime}的积。
3) 2(mod3)的自然素数, 即2和6m-1形自然素数在Z(\omega)仍然是素数。

二、几个对本帖有用的引理。

【引理1】 \omega\equiv\omega^{\prime}\equiv1(\mod\rho)
证:\omega\equiv\omega^{\prime}(mod\rho)显然,两边乘以\omega^2\omega\equiv\omega^{\prime}\equiv1(\mod\rho).
推论1:a+b\omega\equiv a+b\omega^{\prime}\equiv a+b(mod\rho)
推论2:a+b\omega\equiv 0(mod \rho) 当且仅当a+b\equiv 0(mod 3).(证略)
注:事实上, \rho1-\omega,1-\omega^{\prime}相伴,而且大多数书上选择的是\rho=1-\omega.
【引理2】 Gcd(a+b\omega, a+b\omega^{\prime})|\rho Gcd(a, b)
证:Gcd(a+b\omega, a+b\omega^{\prime})=Gcd(a+b\omega, a+b\omega-(a+b\omega^{\prime}))=Gcd(a+b\omega, \rho b)|Gcd(\rho(a+b\omega)-\omega\rho b, \rho b)
=Gcd(\rho a, \rho b)=\rho Gcd(a, b).
推论1:当 \rho 不整除a+b\omega时,Gcd(a+b\omega, a+b\omega^{\prime})=Gcd(a, b).
推论2:当 \rho 不整除a+b\omega时,Gcd(a+b\omega, a+b\omega^{\prime})=1↔Gcd(a, b)=1.即“共扼互质↔分量互质”。
【引理3】 d|(a+b\omega), 当且仅当d|Gcd(a,b).
证:d总是同时整除a+b\omegaa+b\omega^{\prime},即d|Gcd(a+b\omega, a+b\omega^{\prime})|\rho Gcd(a, b). 当d不含因子3时,显然d|Gcd(a,b). 当3|d时,因dGcd(a, b)均含有偶数个\rho,仍有d|Gcd(a,b).

三、丢番图方程a^2+ab+b^2= n^2的通解公式和解数

    除了那些基本性质,关于Z(\omega)最容易想到的一个问题就是哪些a+b\omega(ab\ne 0)的模为自然整数,即范数N(a+b\omega)为自然平方数。这就导致方程:  

a\otimes b=n^2. 在Z(\omega)中写为(a+b\omega)(a+b\omega^{\prime})=n^2.
只要求出本原解,比例解乘以倍数可得,所以限定Gcd(a,b)=1是有道理的。这个限制使得
1)n不含任何第3)类素数因子p^3. 否则p^3|(a+b\omega),由引理3得p^3|Gcd(a, b)=1,矛盾.
2)n不含因子3. 否则n^2\rho^4. 由于引理1的推论1知a+b\omegaa+b\omega^{\prime}平分n^2中的\rho,那么至少各分得\rho^2,即3|Gcd(a, b)=1,矛盾. 于是按引理2推论2可得
3) Gcd(a+b\omega, a+b\omega^{\prime})=Gcd(a,b)=1,因此总可得到a+b\omega=(u+v\omega)^2a+b\omega^{\prime}=(u+v\omega^{\prime})^2n=u\otimes v.
展开后比较分量系数可得 a=u^2-v^2,b=2uv-v^2.
要保持Gcd(a,b)=1,须有Gcd(u, v)=1,u+v\ne 0(mod 3).(引理1推论2)
显然,总可以得到u \gt v \gt0。如果所得u^2-v^2\gt 2uv-v^2,那就取 a=2uv-v^2,b=u^2-v^2. 总可使得结果满足0\lt a\lt b.
4)假定n=p_1^{s_1}\cdot p_2^{s_2}\cdot \cdot \cdot p_i^{s_i}\cdot \cdot \cdot p_k^{s_k}p_i=(a_i+b_i\omega )(a_i+b_i\omega^{\prime}),为了构造a+b\omegaa+b\omega^{\prime},我们需要将(a_i+b_i\omega)^{2s_i}(a_i+b_i\omega^{\prime})^{2s_i}的所有质因子(按重数计)平分成两堆,划拨给a+b\omegaa+b\omega^{\prime}。由于引理3的原因,a+b\omega不能同时要一对共扼因子,a+b\omega^{\prime}也一样。否则短路打火,烧焦成实因子,就破坏了a与b的互质性。所以要么将(a_i+b_i\omega )^{2s_i}全部给a+b\omega(a_i+b_i\omega^{\prime})^{2s_i}全部给a+b\omega^{\prime},要么将(a_i+b_i\omega^{\prime})^{2s_i}全部给a+b\omega(a_i+b_i\omega)^{2s_i}全部给a+b\omega^{\prime},只有这2种分配方案。于是全部分配方案就是\frac{2^k}2=2^{k-1}种。除以2是因为共扼对称和乘法交换律。

并且hujunhua给出了对应的图解
Ze