数论剩余系学习

2019-04-13 13:21发布

剩余系定理三: 若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(mod m)时,有a≡b(mod m); 证明:ac≡bc(mod m) <=> (ac - bc)≡0(mod m) <=> (a - b) * c ≡ 0 (mod m),如果(c, m) = 0,那么一定有 m | (a - b),也就是(a - b) ≡ 0 (mod m)  <=> a ≡ b (mod m); 形象理解:如果把m看成一个环形跑道,一匹马每一步走c米,起点都是0,那么走a步和走b步最终停在了同一个位置,那么一定有m | (a - b)。因为(c, m) = 1,那么在1~m这m步内这匹马一定停在了跑道上不同的m个位置,同时也遍历了跑道的m个位置,所以说a和b一定相差m的整数倍。 如果把a和b看成跨步不同的马,同时走c步,那就很难理解了。 剩余系定理七: 设m是一个整数,且m>1,b是一个整数且(m,b)=1。如果a1,a2,a3,……,am是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…,ba[m]也构成模m的一个完全剩余系。 形象理解:因为序列a是一个完全剩余系,所以都是mk + c的形式,因为m | mk*c,所以剩下的依然是因为互质所产生的剩余系的遍历。 同余定理六: 如果a,b,c,d是四个整数,且a≡b(mod m),c≡d(mod m),那么ac≡bd(mod m); 理解:a可以分解成mk1 + h的形式,同样c可以分解成mk2 + h的形式,然后(mk1 + h)(mk3 + L)≡(mk2 + h)(mk4 + L)  ( mod m) 费马小定理的证明: 如果p为质数,那么一定有剩余系(1,2,3,4,5,……,p-1),因为互质,所以需要p-1步遍历所有的点,就是在p-1步的时候回到原位置,所以a^(p-1)≡1(mod p)。
素性测定: 如果对于任意满足1 b^(p-1)≡1(mod p) 那么p必定是一个素数。 证明:因为如果p是一个合数,那么一定存在一个b满足(b,p) != 1,那么这时候b^(p-1)!≡1(mod p),因为b最小只能遍历到lcm(b,p)/b这个程度。 所以p必定是一个素数。
信息安全数学基础上的数论定理: 第二章——同余 完全剩余系: 定理3:设m是正整数,a是满足(a,m) = 1的整数,b是任意整数,若x遍历模m的一个完全剩余系,则ax+b也遍历模m的一个完全剩余系。 证明:因为(a,m)=1那么我们知道了需要a*m才能回到原点,也就是说ax能够遍历模m的一个完全剩余系,那么+b也可以遍历完全剩余系,只是位置有些错位罢了。 定理4:设m1,m2是两个互素的正整数,若x1,x2分别遍历m1,m2的完全剩余系,则m2*x1 + m1*x2遍历模m1*m2的剩余系。 证明:因为x1遍历了m1的剩余系,而x1又在x1*m2当中乘了一个m2,所以可以直接假设x1为最小非负完全剩余系,x2同理。 x1和x2有m1*m2种组合方式,要证明着几种组合方式两两不同即可。因为m1和m2互素,所以会在x1 = m1且x2 = m2的时候回到原点。 理解:一个可以一步跨5米或者8米的马,可以走到环形5 * 8 = 40米跑道的任何地方。 定理5:设p,q是两个不同的素数,n是他们的乘积,则对于任意的整数c,存在唯一的一对整数x,y(0 ≤ x < p, 0 ≤ y < q)满足 qx + py ≡ c (mod n),因为一共有p*q种选择,不同的选择构成了一个p*q的矩阵。 简化剩余系: 定理2:设m是一个正整数,若r1,……,rk是k = eular(m)个与m互素的整数,并且两两不同余,则r1,……rk两两不同余,那么构成一个简化剩余系。 定理3:设m是一个正整数,a是满足(a, m) = 1的整数,如果x遍历模m的一个简化剩余系,那么ax也遍历m的一个简化剩余系。 因为(a,m) = 1,那么ax遍历结果两两不同余,因为a和x中都没有m的公共因子,所以说ax也遍历了m的一个简化剩余系。“乘互素,仍剩余”。 定理4:设m是一个正整数,a是满足(a,m)=1的整数,则存在整数a‘,1≤a’≤m-1,使得a*a‘≡1(mod m)。 证明:1一定属于m的一个剩余类,那么ax(1 < x < m)在遍历m的剩余系的时候一定遍历了1这个点。 构造:广义欧几里得算法。 定理5:设m1,m2是互素的两个整数,如果x1,x2分别遍历模m1和模m2的简化剩余系,则m2x1 +m1x2遍历m1m2的简化剩余系。 证明: