0509.1917天：除法模余运算的意义是什么？

#每日三件事，第1917天#

现在是11点，6小时以后是几点？你一定会说是下午5点，或者说是17点。11+6-12=5。

今天是周四，5天以后是周几？你会说是周二。因为4+5-7=2。

今天是9号，25天以后是几号？你会说是6月4日，因为6+25-31=4，五月有31天。

你有4个苹果，再给你5个，你有9个苹果，4+5=9。

发现了吗？有些计算是在一定范围内循环的，有些则没有。

比如时间，就是在0-23之间循环，星期的天数在1-7之间循环，日期则在1-31之间循环。

这种计算就是模运算，记作mod。比如10 mod 7 = 3。

(a+b) mod n = a mod n + b mod n
(a-b) mod n = a mod n - b mod n
(a*b) mod n = a mod n * b mod n，如果结果大于n的话，就继续modn

a/b mod n 的计算就比较麻烦了，需要用到逆元。

当gcd(a,p)=1时， $a^{p-1} \equiv 1 \ mod \ p$ ，变换一下就是： $a * a^{p-2} \equiv 1 \ mod \ p$

也就是说 $a 和 a^{p-2}$ 互为逆元， $a/b \ mod \ p= a* inv(b) mod \ p = a* b^{p-2} mod \ p$

加法、减法以及乘法的的模运算还可以理解，这个除法的模运算就是乘以这数的逆元，到底是个什么意思呢？暂时还不能理解。