1.何为同余

数论啊，兜兜转转还是回到了这里

这里并不会像教材一样严格讨论定义，重点还是会用，会算就行

可能字面会错，但我能保证意思不会差

仅仅是记录我的学习过程

数论研究的是整数，所以以下的所有字母默认均为属于整数

什么是余数？

这还用想吗，被除数-商*除数就是余数

但如果被除数是负数呢？越减越小，减减更快乐？所以我们不应该只将其定义为“被除数减去除数直到其小于除数后的那个数”。

想一想 \[ (-3)÷2 \] 这玩意应该余啥？我们都把负数专门拿出来讨论了，那只输出本体或是固定的负无穷大那就没意思了

何必拘泥于减法呢？我们可以看看加法 \[ (-3)+2=-1 \]

啥？你跟我说-3除以2余1？确实，我就是想说这个

或者说实际上我们并不是想知道它严格上的余数到底是什么，我们只想要一个对人类而言最简单易懂的结果

例如一天有24小时，每天早上八点有课

我们会理解为

而不会说

在“我们每天八点有课”中，我们已经不关心是哪一天了，反正昨天有，今天有，明天也有。我们觉得每一天的八点都一样要上课，那就不必拘泥于到底是哪一天，八点和三十二点已经在暗中被画上了等号

我们可以称24为“模”，也就是模为24的情况下，-40，-16，8，32，56是等价的，也就是这些数在模24的情况下都可以写成8。虽说要写32，56什么的也没什么问题，但最简单的8多好看

所以，我们就不需要拘泥于余数的定义有没有被除数为负数的情况，而是直接认识到它们是等价的

那除数为负数呢？

无所谓的，对于一天的时间，减24和加24终究是回到原点，所以模-24和模24是一样的，那我们还不如直接把模数都写成正的，好看也好理解

至此，为了方便记录这些等式，我们就可以给出定义

\[ a≡b\quad(mod\space n) \] 这个式子可以理解为a%n==b%n的意思，a与b除以p所得余数相同

它也可以说成

其中n就称为“模”或者“模数”（一般来讲，n≠0，毕竟n=0求余也没什么意义）

或者说

它有一个等价形式 \[ n|(a-b) \] 等等，“|”又是什么东西？

在式子 \[ a|b \] 中，它一般叫做“a整除b”，可以理解说是b%a==0 ，但更准确的定义是 \[ b=ka\quad k∈Z \] 毕竟b有可能是负数

所以上面的式子也就是n整除a-b，或者说，存在一个整数k，使得kn=a-b

说实话一开始我还觉得左边是除数右边是被除数的形式看着难受，但永远不要小看人的适应能力。多看多用，总会习惯

但是，你有没有发现，明明两种形式都有各自的定义，我却在两者之间强行插上了“等价”二字

这个加粗不是为了强调，而只是想让你产生怀疑

说怀疑也怀疑不到哪里去吧应该。毕竟，从小学一年级就开始认识数字，加减乘除的我们会觉得这个“等价”会是个不证自明的东西

如果你觉得它不证自明，那我猜测你的想法是：a和b应该是能被拆成能整除的部分和不能整除的部分，相减一下，欸，不能整除的部分没了！

其实证明这个等价也就是这么回事

先来试试前推后

由 \[ a≡b\quad(mod\space n) \] 说明存在k₁和k₂，使得a=k₁n+p₁，b=k₂n+p₂（p₁,p₂∈[0,n-1]）

显然的，a对n求余是p₁，b对n求余是p₂，由上面，我们对同余式的定义可以得到p₁=p₂

那我们就将p₁，p₂都记为p，即令p=p₁=p₂

那么就有 \[ a-b=(k_1n+p-(k_2n+p))=n(k_1-k_2) \] 说明a-b是n的倍数，即n整除a-b

现在逆推，由 \[ n|(a-b) \] 也就是 \[ a-b=kn⇨a=b+kn \]

\[ a≡b\quad(mod\space n)⇨b+kn≡b\quad(mod\space n) \]

显然的，(b+kn)%n==b%n，因为就是相差整数倍的n，有上面等式成立

至此我们证明了两种表达是等价的

这最后一步的证明也隐含了同余的重要性质： \[ a≡a+kn\quad(mod\space n)\quad k∈Z \] 这个我觉得没什么必要证明了，从定义就能明白

2.同余的基本性质

同余式既然长得像个等式，肯定是因为人们发现它具有等式的一些性质才会这么做，因为这样理解和使用更加便捷

那就让我们一步步看

1.自反性

即 \[ a≡a\quad(mod\space n)\quad \] 任何数都与自身同余，这里不做证明

2.对称性

\[ a≡b\quad(mod\space n)⇦⇨b≡a\quad(mod\space n)\quad \]

这里不作证明

3.传递性

\[ a≡b\quad(mod\space n),b≡c\quad(mod\space n)⇨a≡c\quad(mod\space n)\quad \]

证明： \[ a≡b\quad(mod\space n)⇨n|(a-b)⇨k_1n=(a-b)\newline b≡c\quad(mod\space n)⇨n|(b-c)⇨k_2n=(b-c) \] 两式相加得 \[ (k_1+k_2)n=a-c⇨n|(a-c)⇨a≡c\quad(mod\space n) \]

4.加减模数为自身

第一条就是前面说的 \[ a≡a+kn\quad(mod\space n)\quad k∈Z \]

5.左右可同加减（同余式）

\[ a≡b\quad(mod\space n)⇦⇨a+x≡b+x\quad(mod\space n) \]

证明：可将其化为 \[ n|a-b⇦⇨n|(a+x)-(b+x) \]

所以两者均可相互转化。正着转换是加法，反过来就是减法，或者说减一个数就是加上其相反数，一样的方法就能证明，这里省略

那如果 \[ a≡b\quad(mod\space n)\newline c≡d\quad(mod\space n) \] 会有 \[ a+c≡b+d\quad(mod\space n) \] 吗？

答案是肯定的 \[ a≡b\quad(mod\space n)⇨n|(a-b)⇨jn=a-b\newline c≡d\quad(mod\space n)⇨n|(c-d)⇨kn=c-d\newline (j+k)n=(a+c)-(b+d)⇨n|(a+c)-(b+d)⇨\newline a+c≡b+d\quad(mod\space n) \] 两侧相减也是同理，此处不作证明

6.左右可同乘（同余式）

\[ a≡b\quad(mod\space n)⇨ka≡kb\quad(mod\space n)\quad k∈Z \]

证明： \[ a≡b\quad(mod\space n)⇨n|(a-b)⇨jn=a-b⇨jkn=k(a-b)⇨n|k(a-b)⇨n|ka-kb⇨ka≡kb\quad(mod\space n) \]

同样，也有 \[ a≡b\quad(mod\space n)\newline c≡d\quad(mod\space n)\newline ⇨ac≡bd\quad(mod\space n) \] 但证明方式得稍微拐个弯

尝试： \[ a≡b\quad(mod\space n)⇨n|(a-b)⇨jn=a-b\newline c≡d\quad(mod\space n)⇨n|(c-d)⇨kn=c-d\newline jkn^2=ac-ad-bc+bd \] 这样的等式与我们期望的结果不符

那我们就该重新想想

我们操作等式的重心一定要在n上吗

如果说这条性质是正确的，只要我们凑出ad-bc，它等号的对侧一定是能够写成n乘上什么什么的形式

至于n旁边的数是什么，我们并不关心

但ad-bc在哪？如果你的注意力比较涣散的话可能就难以发现(其实就是移项避免分配律乱配)，反正我就是这样我是笨蛋😢 我还是问GPT才意识到的

现在我们看不出ad-bc在哪，我也不想看。

那不然我们就试试找出ad或者bc，相对于我们想要的结果kn=ac-bd也就是移一个项的事

看看上面，感觉b和d比较好表示，那我们就算算bd

证明： \[ a≡b\quad(mod\space n)⇨n|(a-b)⇨jn=a-b⇨b=jn+a\newline c≡d\quad(mod\space n)⇨n|(c-d)⇨kn=c-d⇨d=kn+c\newline bd=jkn^2+jcn+kan+ac⇨(jkn+jc+ka)n=bd-ac⇨n|bd-ac\newline ⇨ac≡bd\quad(mod\space n) \] 你看，这样表示bd确实就是kn+ac的形式，由此就能得证了

7.除呢？我同除呢？

拔说了，直接上反例 \[ 4≡2\quad(mod\space 2) \] 这个同余式没什么问题，但两侧同除2后 \[ 2≡1\quad(mod\space 2) \] 你说这怎么可能嘛

但也不是所有情况都不能同除 \[ 20≡50\quad(mod\space 3)⇨(同除5)⇨4≡10\quad(mod\space 3) \] 20和50模3都余2没什么问题，4和10模3都余1也没问题，同余式仍然成立

并不是所有情况都可以同除，但也不是所有情况不能同除。

即使如此，我们一般也不认为同余具有除法性质

但我觉得同余两侧同除一个数会发生什么是一个很好玩的思维游戏 \[ a≡b\quad(mod\space n)⇨n|(a-b)⇨kn=a-b⇨\frac{kn}{m}=\frac{a-b}{m} \]

当然，这里m能够整除a和b，以后除法默认可整除

因为(a-b)/m是整数，所以kn/m也是整数

或者也可以如此说明kn/m是整数 \[ kn=a-b⇨a=kn+b\newline \frac{a}{m}=\frac{b+kn}{m}=\frac{b}{m}+\frac{kn}{m} \] 虽然kn/m是板上钉钉的事，但我总觉得这个表达形式让我心痒痒

m是a和b的公因数，也就是b和kn+b的公因数

m确实和k有这么一层关系，但总觉得，很不直观

要不然换种表达吧 \[ da≡db\quad(mod\space n)⇨n|da-db⇨kn=d(a-b)⇨\frac{kn}{d}=a-b \] 这次我们不控制差值了，而是控制公因数d

也就是 \[ k=\frac{d(a-b)}{n} \] 是不是直观多了

现在回到正题，什么时候能整除，什么时候不能整除？

如果要 \[ a≡b\quad(mod\space n)⇦⇨n|(a-b)⇦⇨\frac{k}{d}∈Z \] 说明当d能整除k的时候两侧可以同除

那如果我不听话，硬是同除呢？

kn/d是整数，但d不整除k，那我们可以将其看作 \[ \frac{kn}{d}=\frac{gcd(k,d)k_1n}{gcd(k,d)d_1}=k_1\frac{n}{d_1}\newline 其中gcd(a,b,...)表示括号内所有数的最大公因数\newline 令k=gcd(k,d)k_1\space,\space d=gcd(k,d)d_1 \] 因为kn/d是整数，k₁是整数，那必然有n/d₁是整数

这样就可以写成 \[ da≡db\quad(mod\space n)⇨a≡b\quad(mod\space \frac{n}{d_1})⇨a≡b\quad(mod\space \frac{gcd(k,d)n}{d})⇨a≡b\quad(mod\space \frac{gcd(\frac{d(a-b)}{n},d)n}{d}) \] 显然地有，当d整除k，有d₁=1，因为这时候gcd(k,d)=d

所以这个推理是对任意d成立的，因为d要么整除k，要么不整除k

但我觉得这个式子可能没什么实际价值，太抽象了，单纯推着玩。

同时我们也可以发现，表达法多种多样，毕竟你只要找到一个a-b能被一个数整除，你可以写出类似的式子

像gpt喜欢说 \[ da≡db\quad(mod\space n)⇨a≡b\quad(mod\space \frac{n}{gcd(d,n)}) \] 然后说，当d和n互质时，两侧就可以同除

证法是类似的，这个推理也是正确的 \[ \frac{kn}{d}=\frac{gcd(n,d)n_2k}{gcd(n,d)d_2}=\frac{k}{d_2}n_2 \] 也就是说，当n和d互质时，两侧同除d是能保证模数n不变的

因为n和d互质，那只能让d整除k才能保证kn/d是整数

那反过来想想，如果两侧除以d后，在模数不变的情况下同余式仍成立

可以说明d一定整除k吗？可以说明d和n一定互质吗？

前者是可以的，因为a-b=kn/d，由同余式的定义可知k/d一定是整数

对于后者，我们已经知道了k/d，那么一定会有gcd(n,d)=1？不见得

想证伪最简单的办法就是举反例

找k，n，d使得d整除k并且n和d有公因数

不妨令k=4，n=6，d=2，那么kn=24=da-db

也就是da=db+24，不妨令b=1，有 \[ 26≡2\quad(mod\space 6) \] 这个同余式没有问题

尝试左右两侧同除2 \[ 13≡2\quad(mod\space 6) \] 仍没有问题，但是gcd(n,d)≠1

也就是，同余式两侧有公因数d的情况下

d整除k是同余式两侧同除d但模数不变后同余式仍然成立的充要条件

d和n互质是同余式两侧同除d但模数不变后同余式仍然成立的充分不必要条件

其实我猜测同除这件事可能跟高中学的向量运算比较相似，既没有这个性质，平时应该遇不上这种问题。就像我们平时见不到向量除向量一样，我们应该也见不到同余除以同余，这时由其性质决定的，因为没有什么实际含义，所以没有对应的情况能表达出这种东西

8.左右可同求幂

像一般等式一样 \[ a=b⇨a^c=b^c \] 我们也希望有 \[ a≡b\quad(mod\space n)⇨a^c≡b^c\quad(mod\space n) \] 其实这个问题很简单，因为我们已经知道了 \[ a≡b\quad(mod\space n)\newline c≡d\quad(mod\space n)\newline ⇨ac≡bd\quad(mod\space n) \] 那剩下就是归纳法的事了

证明：

显然有 \[ a≡b\quad(mod\space n)⇨a^2≡b^2\quad(mod\space n) \] 并且有 \[ 若a^k≡b^k\quad(mod\space n)\newline 则a^{k+1}≡b^{k+1}\quad(mod\space n) \] 所以 \[ a≡b\quad(mod\space n)⇨a^c≡b^c\quad(mod\space n) \] 得证

结

同余式常用的基本性质大致就这些。

像同除，同开跟，同取对数之类的运算一般不会去深究，因为一般不会出现，而且这些运算容易产生分数和无理数