跳转至

剩余

剩余

前置知识:离散对数

模运算下的剩余问题,是将开方运算引入模运算的尝试。

定义

令整数 k2,整数 am 满足 (a,m)=1,若存在整数 x 使得

(1)xka(modm)

则称 a 为模 mk 次剩余,否则称 a 为模 mk 次非剩余。

二次剩余 即是 k 次剩余的特例。

性质

当整数 k2,整数 am 满足 (a,m)=1,模 m 有原根 g 时,令 d=(k,φ(m)),则:

  1. a 为模 mk 次剩余当且仅当 dindga,即:

    aφ(m)d1(modm)
  2. 方程 (1) 若有解,则模 m 下恰有 d 个解

  3. mk 次剩余类的个数为 φ(m)d, 其有形式

    agdi(modm),(0i<φ(m)d)
证明
  1. x=gy,则方程 (1) 等价于

    gkygindga(modm)

    其等价于

    (2)kyindga(modφ(m))

    由同余的性质,我们知道 y 有整数解当且仅当 d=(k,φ(m))indga,进而

    aφ(m)d1(modm)gφ(m)dindga1(modm)φ(m)φ(m)dindgaφ(m)dφ(m)indgadindga
  2. dindga 时,由同余的性质可知方程 (2)φ(m) 下恰有 d 个解,进而方程 (1)m 下恰有 d 个解。

  3. 由 1 知 a 为模 mk 次剩余当且仅当 dindga,故

    indgadi(modφ(m)),(0i<φ(m)d)

    故模 mk 次剩余共有 φ(m)d 个同余类:

    agdi(modm),(0i<φ(m)d)

参考资料

  1. 冯克勤。初等数论及其应用。

本页评论