信息安全数学基础（11）同余的概念及基本性质

一、同余的概念

同余是一个数学概念，用于描述两个数在除以某个数时所得的余数相同的情况。具体地，设m是一个正整数，a和b是两个整数，如果a和b除以m的余数相同，则称a和b模m同余，记作a≡b(mod m)。反之，如果a和b除以m的余数不同，则称a和b模m不同余。

二、同余的基本性质

自反性：对任一整数a，有a≡a(mod m)。这是显然的，因为任何数除以自身都余0。

对称性：若a≡b(mod m)，则b≡a(mod m)。即如果a和b模m同余，那么b和a也模m同余。

传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)。即如果a和b模m同余，且b和c模m同余，那么a和c也模m同余。

加法性质：若a≡b(mod m)，c≡d(mod m)，则a+c≡b+d(mod m)。即模m同余的数在加法运算下保持同余。

乘法性质：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)。即模m同余的数在乘法运算下也保持同余。

幂的性质：若a≡b(mod m)，k为正整数，则ak≡bk(mod m)。即模m同余的数的幂也模m同余。

线性组合：若a≡b(mod m)，c≡d(mod m)，则对于任意整数x,y，有ax+cy≡bx+dy(mod m)。这是加法性质和乘法性质的推广。

整除性质：若a≡b(mod m)，且d|m（d是m的因数），则a≡b(mod d)。即模m同余的数也模m的因数同余。

模的乘积：若a≡b(mod m1)且a≡b(mod m2)，且m1,m2互素，则a≡b(mod m1m2)。这是中国剩余定理的基础。

三、剩余类与剩余系

剩余类：设m是一个正整数，对任意整数a，令Ca={c|c∈Z, c≡a(mod m)}。Ca叫做模m的a的剩余类，它包含了所有模m余数为a的整数。
完全剩余系：若r0,r1,...,rm-1是m个整数，并且其中任何两个数都不在同一个剩余类里（即它们模m两两不同余），则称r0,r1,...,rm-1为模m的一个完全剩余系。完全剩余系中的每个数都代表了一个不同的剩余类。
简化剩余系：如果一个模m的剩余类中存在一个与m互素的剩余，则这个类被称为模m的一个简化剩余类。在模m的所有不同简化剩余类中，从每个类中任取一个数组成的整数的集合，叫做模m的一个简化剩余系。简化剩余系中的元素个数等于欧拉函数φ(m)的值，即小于或等于m且与m互素的整数的个数。