Skip to content

《简明数论》的简明笔记(下)

  • x²≡d (mod p)的问题。
    • ax²+bx+c≡0 (mod p)可通过配方转化。
      • (2ax+b)²≡b²-4ac(mod p)
    • d是p的二次剩余当且仅当方程有解,否则为二次非剩余。
      • 既约剩余系中恰有(p-1)/2个二次剩余和(p-1)/2二次非剩余。
    • d是二次剩余当且仅当d(p-1)/2≡1 (mod p),否则模为-1。
      • 于是两二次剩余或两二次非剩余的积为二次剩余,二次剩余与非剩余的积为二次非剩余。
  • Legendre符号\left(\frac{d}{p}\right)当d是p的二次剩余、非剩余及p|d时分别取值1、-1、0。
    • Gauss二次互反律\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}的主要应用似乎是用来简化及计算Legendre符号的值,以求解二次同余方程。
      • 但在编程中可直接利用\left(\frac{d}{p}\right)=(-1)^{\frac{p-1}{2}}来计算,复杂度是相同的。
    • Jacobi符号具有与Legendre符号相同的互反律,但似乎就与二次同余方程没什么关系了,目前还没看到应用。
  • 关于同余方程的Lagrange定理的内容是同余方程的解数不超过它的次数。
    • 可用归纳法证明,很优雅。
    • n次同余方程f(x)=x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \equiv 0 \pmod{p}有n个解,当且仅当f(x)的次数小于等于p,且f(x)除xp-x所得的余式模p恒等于0。
    • 对于次数大于p的高次同余方程,总存在一个次数不大于p、首项系数为1的等价同余方程,即是xp-x除f(x)所得的余式(再将首项系数化为1)。
      • 例外是余式模p恒等于0,不妨认为此时的等价同余方程就是xp-x。
    • 事实上,简化高次同余方程也可避免做多项式除法,可用Fermat小定理xp≡x (mod p)直接降低次数。
  • 模为素数幂的同余方程的解法看上去很强大,但是前提是需要先解出模为素数的同余方程啊!难道除了直接验证没什么通用的解法?26节先放下。

One Comment

  1. beyes wrote:

    有些数学符号,在您的blog上显示不出来了

    Saturday, August 11, 2012 at 13:36 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*