上个月的UyHiP谜题涉及到一些抽象代数的东西:考虑一个有f个元素的有限域,其中c是有限域中的一个元素。试求x^2+y^2=c有多少个解。你的答案应该是一个关于f和c的函数。
有趣的是,对所有c≠0的情况,x^2+y^2=c的解的个数与c都是无关的。事实上,方程解的个数只与f模4的余数和c是否为零元有关。具体地说:
c = 0 | c ≠ 0 | |
f mod 4 = 0 或 2 | f | f |
f mod 4 = 1 | 2f – 1 | f – 1 |
f mod 4 = 3 | 1 | f + 1 |
结论的证明并不复杂(并且很诡异),最关键的一点就是:有限域的乘法群是一个f-1阶循环群。在任一有限域F中必然存在一个“生成元”g,使得1、g、g^2、……、g^(f-2)正好就是F中的所有非零元素,反过来所有非零元也都能表示成g的某次幂。这样的话,要想知道c是否是一个二次剩余(是否存在x使得x^2=c),只需要把c写成g^i,然后看是否存在某个元素x=g^(i/2),换句话说有没有哪个数的两倍模f-1正好就是i。当f是奇数时,i/2存在当且仅当i为偶数;当f为偶数时,每个元素都是一个二次剩余。
定义函数Χ(a)为x^2=a的解的个数减一(嗯,我知道,这个函数来得很诡异)。由于x^2=a是一个二次方程,因此它最多只有两个解,也即Χ(a)的取值只可能是-1、0和1。容易看出:
1. 对所有非零元a,Χ(a) = Χ(a^(-1)),其中a^(-1)表示a的乘法逆元。注意,g^i的乘法逆元就是g^(f-i-1),它们相乘正好就是g^(f-1)=1。
2. 对任意a和b,Χ(a)Χ(b)=X(ab)。
3. Χ(0)=0,因为x^2=0明显只有x=0一个解。
4. 当f=4k+3时,Χ(-1)=-1;当f=2k时,Χ(-1)=0;当f=4k+1时,Χ(-1)=1。注意,-1是指乘法单位元的加法逆元,就是平方之后等于1的那个元素。当f=4k+3时,-1就是g^(2k+1),它没有平方根;当f=4k+1时,-1就是g^(2k),g^k和g^(3k)都是它的平方根;当f=2k时,1的加法逆元就是它本身,它的平方根也只有它本身。
5. ΣΧ(a)=0,其中a取遍有限域F中的所有元素。
现在我们来求x^2+y^2=c的解的个数,它应该等于:
Σa+b=c(Χ(a)+1)(Χ(b)+1)
= Σa+b=cΧ(ab) + ΣaΧ(a) + ΣbΧ(b) + f
= Σa+b=cΧ(ab) + f
= ΣbΧ((c-b)b) + f
= Σb≠0Χ((c-b)b) + f
= Σb≠0Χ((c-b)/b) + f
= Σb≠0Χ(c/b – 1) + f
当c=0时,式子就直接变成了Σb≠0Χ(-1) + f = f + (f-1)Χ(-1);
当c≠0时,函数m(b)=c/b正好就是一个F内所有非零元一一对应的函数,因此式子直接变为Σd≠0Χ(d-1) + f = Σd≠-1Χ(d) + f = f – Χ(-1)。而我们已经知道了Χ(-1)的值,问题迎刃而解。