Skip to content

同余

2021-07-12

INFO

若无特殊说明,本章涉及的变量皆为正整数。

定义

amodm=bmodm,则 abm 同余,记作 ab(modm)

aba=b+kmm(ab)(modm)

性质

  • 自反性:aa(modm)
  • 对称性:abba(modm)
  • 传递性:abbcac(modm)
  • 同加性:aba+cb+c(modm)
  • 同乘性:abacbc(modm)
  • 同幂性:abanbn(modm)

同余不满足同除性。当 ab(modm) 时不一定有 anbn(modm)

同余类

集合 A 是模 m 的同余类,当且仅当:

  • A 中的所有元素模 m 都等于同一个值 a
A={xxmodm=a}

a 称为该同余类的代表元。

m 的同余类有 m 个,其代表元分别为 0,1,2,,m1

剩余系

集合 A 是模 m 的剩余系,当且仅当:

  • A 中的元素模 m 互不相同。
ij,AiAj(modm)

完全剩余系

m 的完全剩余系有 m 个元素,是元素最多的剩余系。

简化剩余系

m 的简化剩余系有 φ(m) 个元素,每个元素模 m 后都与 m 互质。

乘法封闭

从模 m 的简化剩余系中任取两个数 a,b,则 abmodm 也在模 m 的简化剩余系中。

a,b 属于模 m 的简化剩余系,则 amodm,bmodmm 互质,(amodm)(bmodm) 也与 m 互质。根据 欧几里得算法 有:

gcd((amodm)(bmodm),m)=gcd(m,(amodm)(bmodm)modm)=gcd(m,abmodm)=1

因此 abmodmm 互质,也属于模 m 的简化剩余系。