首页 > Math > 素数的平方和表示

素数的平方和表示

2011年4月11日 发表评论 阅读评论

问题：

找到这样的正整数A和B，使得A^2 + B^2 = p

 

当然，只有模4余1的素数（大于2）的才有平方和表示^^

假设p(>2)是两个数a和b平方的和，因为p是奇数，所以a和b有一个是奇数另一个是偶数。假设a=2m, b=2n+1, 则a^2 + b ^2 = 4m^2+ 4n^2 + 4n + 1， 显然，它模4余1

现在证明以下定理，证明本身就是一个算法（费马降阶Fermat's method of descent）

For \; p \; is \; prime \; more \; than \; 2: \; p \equiv 1 \mod 4 \Leftrightarrow \exists a, b \in N^*, p = a^2 + b^2

 

  • 首先，由二次互反律，存在整数A, B使得A^2 + B^2 = Mp, 其中M是小于p的正整数

若A=1，则B^2 \equiv -1 \mod p，所以只要我们能找到这样的B，就OK了

二次互反律说明，-1是二次剩余，所以这样的B是可以被找到的（稍后说怎么找，算法）


  • 然后就是用费马降阶对这个初始的式子进行变换了
    1. 取u, v，使得u \equiv A (\mod M), v \equiv B (\mod M), -\frac{M}{2} \leqslant u, v \leqslant \frac{M}{2}
    2. 注意到u^2 + v^2 \equiv A^2 + B^2 \equiv 0 \; (\mod M)，所以我们有u^2 + v^2 = Mr\;(1 \leqslant r < M)
    3. 所以(uA+vB)^2+(vA-uB)^2=(u^2+v^2)(A^2+B^2)=M^2 rp
    4. 把M^2除到左边，得到(\frac{uA+vB}{M})^2+(\frac{vA-uB}{M})^2=rp
    5. 这个式子和初始的A^2 + B^2 = Mp一个格式，并且有r \leqslant \frac{M}{2}
    6. 不断重复以上步骤，M的规模每次至少减半，直到成为1，于是算法结束。此时我们也得到了p的平方和表示，并且完成了证明。
    7. 费马降阶算法的时间复杂度为O(log(M))，因为每次M的规模至少减半

PS:很漂亮的恒等式：(uA+vB)^2+(vA-uB)^2=(u^2+v^2)(A^2+B^2)，值得好好研究下

  • 这样，这个定理是证明了，但是，算法却没有结束。因为初始的B还没有找到（虽然它必然存在），以下给出一个随机算法
    1. 注意到欧拉准则a^{\frac{p-1}{2}} \equiv (\frac{a}{p})( \mod p)
    2. 所以二次非剩余的(p-1)/2次同余-1模p
    3. 因为二次非剩余有一半（在1~p-1之间），所以每次随即的选取a，我们有一半的机会获得二次非剩余
    4. k次全部失败的概率是0.5^k，数学期望在两次左右就可找到二次非剩余
    5. 每次计算a^{\frac{p-1}{2}} \mod p的代价是O(log(p))的
    6. 所以算法在期望O(log(p))的时间结束

 

PS：一些猜想：如果素数模4余1，则平方剩余成对出现，即a是平方剩余，则-a也是平方剩余。如果素数模4余3，a是平方剩余，导致-a必然不是平方剩余，即他们总是落单（这其实是显然的，否则就可以用费马降阶，构造出模4余3的素数的平方和表示了，而这是不可能的。但猜想的前半句却不是那么显然的）

上面的算法主要来自《数论概论》这本书，26章是直接对于这个问题的。

分类: Math 标签: ,
  1. Earthson
    2011年4月12日15:22 | #1
    回复 | 引用

    由欧拉准则，其实我那个猜想是显然的。
    p模4余1的情况：若a是二次剩余，则由欧拉准则-a也是二次剩余。若a不是，则-a也不是。因为a和-a是一致的
    p模4余3的情况：正好和上面相反
    所以猜想得证^^

  2. xz
    2011年5月19日11:10 | #2
    回复 | 引用

    此题能否用高斯整数做？
    b^2+1=0(mod p)
    即b^2+1=k*p
    若k求得是x^2+y^2,上式可变成(b+i)=(x+y*i)*(u+v*i)
    求得u、v即分解了p。

  3. Earthson
    2011年5月20日07:26 | #3
    回复 | 引用

    @xz
    若k求得是x^2+y^2

    这貌似不是显然的。。而且，把k表示成x^2+y^2貌似不比原来的把p表示成两数平方简单。

    对高斯整数一直不是太了解。不过它分解的性质应该不是偶然的，找时间我再研究下^^

  1. 本文目前尚无任何 trackbacks 和 pingbacks.