preparation

加法消去律：如果(a+b)≡(a+c) mod m, 则b ≡ c mod m

乘法消去律：对于(a×b)≡(a×c) mod m，若gcd(a,m)=1，则b ≡ c mod m

(a和m互素)

逆元

1.加法逆元 x-y=0

此时很清楚的看出来：

1). (0+4)mod4=0

2). (2+2)mod4=0

3). (1+3)mod4=0


此时0的加法逆元为4, 2的加法逆元为2, 1的加法逆元为3

2.乘法逆元 x*y^-1=1

1).取非素数4
|Z_{4|0|1|2|3|
|:–:|:–:|:–:|:–:|:–:|
|0|0|0|0|0|
|1|0|1|2|3|
|2|0|2|0|2|
|3|0|3|2|1|}

由于4不是素数，所以只有gcd(x,4)=1的有逆元：
此时0和2没有乘法逆元，而1的乘法逆元是1, 因为1×1=1. 3的乘法逆元是3, 因为3×3=1(行标和列标)

2).若取素数5：
|Z_{5|0|1|2|3|4|
|:–:|:–:|:–:|:–:|:–:|:–:|
|0|0|0|0|0|0|
|1|0|1|2|3|4|
|2|0|2|4|1|3|
|3|0|3|1|4|2|
|4|0|4|3|2|1|}

此时1,2,3,4均有乘法逆元

Q:乘法消去律,为什么一定要求要满足gcd(a,m)=1?

A:模m的乘法运算返回的结果是0~(m-1)之间的数，如果乘数a和模数m有除1以外的共同因子,那么不会产生完整的余数集合.

赏

请作者喝养乐多

支付宝

微信