数论 | 迎风飘

整除的相关性质
最大公因数的相关性质
同余的相关性质
线性同余方程
欧几里得算法与拓展
逆元
中国剩余定理
威尔逊定理
费马小定理
欧拉定理
不定方程相关定理
相关证明

整除的相关性质

整除的定义
设a,b $\in$ Z,a $\neq$ 0,若存在q $\in$ Z
使得b=aq,则称b能被a整除（或称a能整除b）记作a|b
否则，称b不能被a整除，记作a $\nmid$ b
1.传递性：若 $a|b$ 且 $b|c$ ,则 $a|c$
2.线性：a|b且a|c等价于对任意的整数x和y,有 $a|(b\times x+c\times y)$

最大公因数的相关性质

最大公因子的定义
所有能同时整除a和b的整数中的最大者，记为(a,b)或者gcd(a,b)
1.若(a,b)=d,则有(a/d,b/d)=1
2.d=(a,b),当且仅当d|a,d|b且如果c|a,c|b,则c|d
3.若(a,b)=1且a|bc,则a|c
4. $ax+by=c$ ,c的最小正整数解为gcd(a,b）
5. $\{k(a,b)|k\in Z\}=\{ax+by|x,y\in Z\}$
6. $(a+cb,b)=(a,b)$
证明：
(4) $ax+by=c$ ,c的最小正整数解为gcd(a,b）
命题即要证 $min｛ax+by｝=d,d|a,d|c$ ,且d最大为gcd(a,b)
反证，若d不能整除a,即存在有整数q,r,使得 $a=d\times q+r$ ,此时 $r<d$
$\qquad r=a-d\times q=a-(ax+by)\times q$
$\qquad r=a\times (1-q\times x)+b\times (-y\times q)$
此时发现一个数r满足ax+by的形式，这个数 $r<d$ ,与d的最小性质相违背
此时对于任意一个a,b的因子c, $c\leq d$ ,所以最大的d为gcd(a,b),由此得证
(5) $\{k(a,b)|k\in Z\}=\{ax+by|x,y\in Z\}$
设左边为集合A,右边为集合B
对于集合A来说，k=1,存在正整数ax+by=gcd(a,b)使之成立（贝祖定理），则有 $k\times gcd(a,b)$ 存在正整数 $k\times x,k\times y$ 使得等式成立，即 $A\subseteq B$
对于集合B来说，即证对于任意 $c=a\times x+b\times y$ 可以表示为 $k\times gcd(a,b)$ 的形式
此时方程有正整数解，满足 $gcd(a,b)|c,gcd(a,b)|a,gcd(a,b)|b$
则根据线性性质
$gcd(a,b)|(a\times x+b\times y)$
则对于任意的c一定可将正整数解x，y化为 $k\times x_0,k\times y_0$ 使得 $c=k\times gcd(a,b)$ 满足
(6) $(a+cb,b)=(a,b)$
即证更相减损法的正确性

同余的相关性质

若a,b为两个整数
他们的差a-b能被某个自然数整除
则称a就模m来说同余于b，或者说a和b关于模m同余
记为： $a\equiv b\pmod{m}$
1.自反性： $a\equiv a\pmod{m}$
2.对称性：若 $a\equiv b\pmod{m}$ ，则 $b\equiv a\pmod{m}$
3.传递性：若 $a\equiv b\pmod{m}$ , $b\equiv c\pmod{m}$ ，则 $a\equiv c\pmod{m}$
3.同加性：若 $a\equiv b\pmod{m}$ ，则 $a+c\equiv b+c\pmod{m}$
4.同乘性：若 $a\equiv b\pmod{m}$ ，则 $a\times c\equiv b\times c\pmod{m}$
$\qquad \qquad$ 若 $a\equiv b\pmod{m}$ , $c\equiv d\pmod{m}$ ,则 $a\times c\equiv b\times d\pmod{m}$
5.同幂性： $a\equiv b\pmod{m}$ ，则 $a^n\equiv b^n\pmod{m}$
6. $a\times b\ mod\ k=((a\ mod\ k\ )\ \times \ (b\ mod\ k\ ))\ mod\ k$
7.若 $a\equiv b\pmod{m}$ , $c\equiv d\pmod{m}$ ,则

$a+c\equiv b+c\pmod{m}$
$a-c\equiv b-d\pmod{m}$
$ac\equiv bd\pmod{m}$

8.若 $ac\equiv bc\pmod{m}$ , $a\equiv b\pmod{m/(c,m)}$
证明：
(8)若 $ac\equiv bc\pmod{m}$ , $a\equiv b\pmod{m/(c,m)}$
设 $a>b$
可知 $ac-bc=k\times m$
$\qquad a-b=(k\times m)/c$
a-b为整数，则 $(k\times m)/c$ 为整数
令gcd(c,m)=d
则有 $m=d\times m_1$ , $c=d\times c_1$
$(k\times m)/c=(k\times m_1)/c_1$
此时 $m_1,c_1$ 互质， $k/c_1$ 为整数
所以
$a-b=(k/c_1)\times m_1$
$a\equiv b\pmod{m_1}$
$a\equiv b\pmod{m/(c,m)}$
得证

线性同余方程

$a\times x\equiv b\pmod{m}$
若 $(a,m)\nmid b$ ，无解；若 $(a,m)|b$ ,则恰有(a,m)个模m不同余的解
特别的，若(a,m)互质，线性同余方程必有唯一解
证明
拓展欧几里得可以求得方程的一解 $x_0$
则根据不定方程的相关定理可得，方程的所有解为 $x=x_0+t\times \frac {m}{gcd(a,m)}$
则易知其模m不同余的所有解恰有(a,m)个