胡说Eisenstein整环之方程解计数

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

公式推导

看到这个信息,hujunhua快速给出了如下结论:
a、b互质时,N有且只能有1(mod3)的质因数。这是数论中关于Z(ω)Z(\omega)的一个基本定理。
当N有k个1(mod3)的质因子时,a2ab+b2=N2a^2-ab+b^2=N^2的互质解(a,b)对数为2k12^{k-1}
并且他认为:
在算法上,这个问题与求本原勾股数完全相同。关于本原勾股数的两个公式:
1、通解公式:a=u2v2,b=2uv,c=u2+v2a=|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)对有2k12^{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(u,v)=1,
{b=4uva=3u2v2+2uvN=3u2+v2\begin{cases}b=4uv\\a=3u^2-v^2+2uv\\N=3u^2+v^2\end{cases}
ii)(u,v)=1(u,v)=1,
{b=4uva=u23v2+2uvN=u2+3v2\begin{cases}b=4uv\\a=u^2-3v^2+2uv\\N=u^2+3v^2\end{cases}
当然我们还需要限定条件1a<b1\le a\lt b,还有可能有公共的因子2需要消去

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

Eisenstein整环简介

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

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

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

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

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

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

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

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

© 2021 Blog Boost Starter