数论-同余

定义

同余,就是两个整数$a,b$对同一个整数$p$进行模运算,所得的余数相同,那么说这两个整数$a,b$关于$p$同余。
我们能够发现,

一旦两个整数$a,b$关于$p$同余,那么他俩的差就能够被$p$整除。也就是$$a-b=m\times k(k∈Z)$$

相关概念

同余类

如果在模$n$意义下,$a,b$同余,那么$a,b$就属于同一个剩余类。
例如,奇数就是一个同余类。

完全剩余系

我们可以发现,一个模数$n$有$n$个不同的同余类,从每一个同余类中各取一个代表,组成的一个集合就是一个完全剩余系。简称完系。
如果这几个代表都$>0而且<n$,也就是$0,1,2,…,n-1$,这个完全剩余系我们称为最小非负完系。

缩同余类

如果$i$和$n$互质,则同余类$M_i$中所有数都和$n$互质(证明可以自己给出,这里先显然吧),那么这个同余类称为缩同余类。

欧拉函数

整数$n$的缩同余类个数记作$\varphi(n)$,我们称之为欧拉函数。

缩剩余系

就是所有的缩同余类中各取一个代表组成的集合。

性质

同余定理

若有$a_1\mod n=b_1$而且$a_2\mod n=b_2$
加法:
$(a_1+a_2)\mod n=(b_1+b_2)\mod n$
同样的,减法和乘法都满足上述性质。但是除法并没有简单的同余定理。
但是我们有这个性质:若$ac\equiv bc\pmod n$,则$a\equiv b\pmod{\frac{n}{(n,c)}}$。由此可以推出:若c和n互质,则有除法的同余定理成立。

性质

若$a\equiv b\pmod n$而且$d!=0$则有$ad\equiv bd\pmod dn$。

幂的同余

  1. 完全平方数模9同余0或者1;
  2. 完全平方数模8同余0,1,4;
  3. 完全平方数模3同余0,1;
  4. 完全平方数模5同余0,$\pm1$;
  5. 完全立方数模9同余0、$\pm1$;
  6. 整数的四次幂模16同余0、1;
  7. 四次幂满足所有平方幂性质,以此类推。

同余思维训练

设$a、b、c、d$都是正整数,证明$a^{4b+d}-a^{4c+d}$能被240整除。
证明
我们先对240进行分解质因数:$$240=2^4\times 3 \times 5$$
我们就可以分别证明原式被$3、5、16$整除。
因为$a^2\equiv 0,1\pmod 3$,所以$a^{4b}\equiv a^{4c}\equiv 0,1\pmod 3$,从而我们可以分类讨论得出:
$$a^{4b+d}-a^{4c+d}\equiv 0\pmod 3$$
……类似地证明其他几个数的整除关系。

文章目录
  1. 1. 定义
  2. 2. 相关概念
    1. 2.1. 同余类
    2. 2.2. 完全剩余系
    3. 2.3. 缩同余类
    4. 2.4. 欧拉函数
    5. 2.5. 缩剩余系
  3. 3. 性质
    1. 3.1. 同余定理
    2. 3.2. 性质
    3. 3.3. 幂的同余
  4. 4. 同余思维训练