2009-07-11 4:48| 
12 Comments | 本文内容遵从上个月的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)的值，问题迎刃而解。
沙发
对抽象代数没研究啊，才高一啊，不过这个证明很神啊，膜拜下
嗯假期日志更新的速度变慢了
对 ‘2. 对任意a和b，Χ(a)Χ(b)=X(ab)。’似乎解释一下比较好，呵呵。我想了一会才注意到要用到前面二次剩余的结论。
我彻底看晕了……
囧,我想死胡同里了......
先占位,后阅读....
神奇
完全看不明白……
那5个性质...都怎么证阿....
看不明白
终于感觉到了，看《Proofs from the Book》和对这类题感兴趣，真的是正相关的
Euler定理贝，必然是模4余1形式的同余类，从这个定理可以推出x+yi是高斯整环Z[i]的逆元当且仅当y≠0时x+yi的范数“x的平方+y的平方”是模4余1的素数，y=0时x是模4余3的素数 欢迎来我主页http://xiaonei.com/profile.do?id=31134449&_vip_flag=72交流数学