同余式.md

含有整数变量的合同式，称为合同方程或同余式。

$ax\equiv b(mod\ m)$这种形式的合同式称为一次同余式，类似地，$a_2x^2+a_1x\equiv b(mod\ m)$称为二次同余式

定理

1. 若$a$与$m$互质，$b$任意，则模$m$恰有一个数$x$使$ax\equiv b(mod\ m)$

   证明：

   • 存在性：因为$a$和$m$互质，故有$s,t$使$as+mt=1$，于是$asb+mtb=b$，于是取$x=sb$，$x$所在剩余类中的数均是解
   • 唯一性：所谓模$m$只有一个这样的$x$，意思是说在模$m$合同的意义下，解是唯一的。即若$ax\equiv b(mod\ m)$，$ay\equiv b(mod\ m)$，则$x\equiv y(mod\ m)$。因为，由$ax\equiv b(mod\ m)$，$ay\equiv b(mod\ m)$得$ax\equiv ay(mod\ m)$，消去和$m$互质的$a$就能得到$x\equiv y(mod\ m)$

2. 若$gcd(a,m)=d\gt1$，且$d\not\mid b$，则同余式$ax\equiv b(mod\ m)$无解

   证明：反证法，如果上式可解，则存在$\alpha$，使得$a\alpha\equiv b(mod\ m)$，从而存在$q$，使得$b=a\alpha-mq$，因为$gcd(a,m)=d\gt1$，故$d\mid(a\alpha-mq)$，从而$d\mid b$，矛盾

3. 若$gcd(a,m)=d\gt1$，且$d\mid b$，则同余式

   $$ ax\equiv b(mod\ m) $$

   有$d$个解，分别为

   $$ \alpha,\alpha+m/d,\alpha+2m/d,\cdots,\alpha+(d-1)m/d $$

   其中$\alpha$为同余式

   $$ (a/d)x\equiv b/d(mod\ m/d) $$ 的解