模意义下的数和运算

取模的运算

定义，对于整数$a$和$b$,满足$b > 0$,则存在唯一的整数$q$和$r$,满足$a = bq + r$,其中$0\le r < b$

其中称$q$为商：$r$为余数。余数可以记作$a\ mod\ b$或者$a%b$表示

模的运算基本上与普通运算规律一样，见下？

给出简单证明：
令$a = n_1 p + r_1,b = n_2 p + r_2$

$(a+b)\ mod\ p = (r_1 + r_2)\ mod\ p = (a\ mod\ p + b\ mod\ p)\ mod\ p$

对于为什么和的模等于模的和再模$p$,对于加法：$r_1,r_2$的和可能大于$p$,对于减法，二者差可能出负数，所以需要再次取模

比如$(5+3)\ mod\ 2$应该为$0$,但是仅计算$(a\ mod\ p + b\ mod\ p)$会得到$2$,需要再一次取模。

再比如$(6-3)\ mod\ 5$应该是$3$,但是$(a\ mod\ p - b\ mod\ p)$得到$-2$,需要再一次取模。

乘法同样可以用上面方法证明出来

特别地,除法不满足以上运算律

比如$(12\div 3)\ mod\ 6 = 4$,但是$(12\ mod\ 6\div 3\mod 6)\mod 6 = 0$,二者不相等

不难发现，任意数$a$对$p$取模得结果只有$p$种，分别是$0,1,2,3,…,p-1(0\le r < p)$

根据这个结果，可以把$mod\ p$意义下所有整数分成$p$种类型，如果两个数$mod\ p$结果相同，那么就把它们视为同一类。

将这种$mod\ p$意义下得相同，称作同余。

我们规定:若两数$a,b$除以$p$得余数相等，则称$a,b$模$p$同余，记作$a \equiv b \pmod{p}$

加法：若$a \equiv b \pmod{M}$且$c \equiv d \pmod{M}$,则$a+c \equiv b+d \pmod{M}$
减法：若$a \equiv b \pmod{M}$且$c \equiv d \pmod{M}$,则$a-c \equiv b-d \pmod{M}$
乘法：若$a \equiv b \pmod{M}$且$c \equiv d \pmod{M}$,则$a\times c \equiv b\times d \pmod{M}$
幂运算：若$a \equiv b \pmod{M}$,则$a^k \equiv b^k \pmod{M},k为正整数$
除法性质：若$a \equiv b \pmod{M}$且$d\mid a,d\mid b,d\mid M$,则$\frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{M}{d}}$

除法性质了解即可

容易得到：$a \equiv b \pmod{M}$等价于$b\mid (x-y)$

裴蜀定理:对于整数$a,b$,一定存在一组整数$x,y$使得$ax+by=gcd(a,b)$

内容待定，请待更新