数论在\(\text{OI}\)中十分重要。
什么是数论？
\[ 研究整数的理论 ——zzq \]
下面直奔主题。
若\(a\)是\(b\)的因数，或\(b\)是\(a\)的倍数，则\(a\)整除\(b\)，记作\(a|b\)。
关于整除，有以下几点：
1、若\(a|b\)，\(b|c\)，则\(a|c\)。
2、若\(a|b\)，\(a|c\)，则\(a|b+c\)。
3、若\(a|b\)，对于任意的\(k \in Z\)，都有\(a|kb\)。
（小学生都懂）
给定整数\(a\)，\(b\)和模数\(p\)，若\(a \bmod p = b \bmod p\)，则称\(a\)和\(b\)在模\(p\)意义下同余，简写成\(a\equiv b \pmod p\)。
同余有以下性质：
1、\((a \bmod p) \plusmn (b \bmod p) = (a \plusmn b) \bmod p\)
2、\((a \bmod p) \times (b \bmod p) = (a \times b) \bmod p\)
3、\(\frac{a \bmod p}{b \bmod p} = \frac{a}{b} \bmod p\)（如果你直接算的话，数学老师会揍你，正确姿势放后面）
3、\(ax \equiv bx \pmod p \Leftrightarrow a \equiv b \pmod { \frac{ p }{ \gcd(p,x) } }\)
\(Proof\)：
\[\because ax \equiv bx \pmod p\]
\[\therefore (a-b)x \equiv 0 \pmod p\]
\[\therefore p|(a-b)x\]
\[\therefore \frac{p}{\gcd(x,p)}|\frac{x}{\gcd(x,p)}(a-b)\]
\[\because \gcd(\frac{p}{\gcd(x,p)},\frac{x}{\gcd(x,p)})=1，也就是互质\]
\[\therefore \frac{p}{\gcd(x,p)} | (a-b)\]
\[\therefore a-b \equiv 0 \pmod p\]
\[于是a\equiv b \pmod p得证\]
原文：https://www.cnblogs.com/ac-evil/p/11705829.html