余数的和等于和的余数:a%p+b%p=(a+b)%p
余数的差等于差的余数:a%p-b%p=(a-b)%p
余数的积等于积的余数: a%p * b%p=(a*b)%p
意义在于当一个数A过大时,可以利用和差积把A拆分为几个数字分别求余,再组合到一起。
乘法逆元:
看到上面的几个推理,是否想商是否也用同样的事情呢?遗憾的是,没有。因为:12/3 % 7 = 4
但12%7=5,3%7=3,(5/3)%7
遇到5/3
不能得整数的尴尬局面。
为了搞定这个问题,想办法找到等式成立的x,3x % 7 = 1
,这样等式(5/3 * 3x)%7 = (5/3)%7
,因为乘1值不变。
乘3再除以3可以消去,得到5x%7 = (5/3)%7
,ok,除法变乘法,x就是5在模7意义下的乘法逆元。
肉眼观察x=5时,3*5%7=1
成立,故(5/3)%7=(5*5)%7=4
,看到没,再回到最初的问题上,12/3=4,4%7=4
等价于12/3%7=>12%7,3%7,5/3%7,5*5%7=4