「学习笔记」数论基础（一）：一些基础定义和定理

笔者能力有限，如有误，请在评论区指正~ 注：以下定理证明较为简单，证明过程可以略过

定义

整除

\[a,b\in\mathbb{Z},a\mathbb{N}eq0\] \[若\exists c\in\mathbb{Z}:a \times c=b\] \[则称a整除b,记为a\mid b\]

最大公约数

\[a,b\in\mathbb{Z}且a,b不同时为0\] \[将a,b的公约数中最大的称为最大公约数,记作(a,b)或\gcd(a,b)\] \[以下是最大公约数的基本性质\] \[\begin{aligned} (a,b) &=(b,a)\\ (a,b) &=(-a,b)\\ (a,b) &=(|a|,|b|)\\ (a,0) &=|a|\\ (a,ka) &=|a|(k\in \mathbb{Z}) \end{aligned}\]

线性组合

\[a,b,m,n\in\mathbb{Z}\] \[称形如ma+nb的整数为a,b的线性组合\]

带余除法

\[a\in\mathbb{Z},n\in\mathbb{N^+}\] \[\exists!q,r\in\mathbb{Z}:0\le r<n且a=qn+r\] \[称q=\lfloor \frac{a}{n}\rfloor为除法的商,r=a\mod{n}为除法的余数\]

同余

\[m\in\mathbb{N^+},a,b\in\mathbb{Z}且m\mid a-b\] \[则称a和b模m同余,记为a\equiv b\pmod{m}\]

完全剩余系

\[若一个整数集合A使得\forall a\in\mathbb{Z},\exists! b\in A:b\equiv a\pmod{m}\space(m\in\mathbb{N^+})\] \[则称A是一个模m的完全剩余系\]

定理

定理1

内容

\[若a,b,m,n\in\mathbb{Z}, 且c\mid a, c\mid b\] \[则c\mid ma+nb\]

证明

\[令cp=a, cq=b\] \[ma+nb=cmp+cnq=c(mp+nq)\] \[\therefore c\mid ma+nb\]

定理2

内容

\[若a,b,c\in \\mathbb{Z}\] \[则(a,b)=(a+cb,b)\] ### 证明 \[令集合A为a与b的所有公因子,集合B为a+cb与b的所有公因子\] \[\forall m\in A\] \[\because m\mid a,m\mid b\] \[\therefore m|1\times a+c\times b(定理1)\] \[\therefore m\in B\] \[\therefore A\subseteq B\] \[\forall n\in B\] \[\because n\mid a+cb,m\mid b\] \[\therefore n|1\times(a+cb)+(-c)\times b(定理1)\] \[\therefore n\in A\] \[\therefore B\subseteq A\] \[\therefore A=B\] \[\therefore (a,b)=(a+cb,b)\]

定理3

内容

\[a,b\in \mathbb{Z}且a\mathbb{Z}不全为0\] \[(a,b)是a,b的线性组合中最小的正整数\] ### 证明 \[令d=ma+nb为a,b的线性组合中最小的正整数(m,n\in \mathbb{Z})\] \[将a表示为带余除法的形式a=dq+r(q,r\in \mathbb{Z},0\le r<d)\] \[r=a-dq=a-(ma+nb)q=(a-mq)a-nqb\] \[\therefore r是a,b的线性组合\] \[又\because 0\le r<d且d是a,b的线性组合中最小的正整数\] \[\therefore r=0\] \[\therefore a=dq\] \[\therefore d\mid a\] \[同理可得d\mid b\] \[\forall c\in\mathbb{N^+}:c\mid a,c\mid b\] \[c\mid d(定理1)\] \[若d\mathbb{N}eq(a,b),则存在e=(a,b)>d\] \[\because e\mid a,e\mid b\] \[\therefore e\mid d\] \[而e>d且e,d\in\mathbb{N^+}\] \[\therefore e\mathbb{N}mid d,自相矛盾\] \[\therefore d=(a,b)\]

推论

\[a,b\in \mathbb{Z}且a,b不全为0\] \[\forall c\in\mathbb{N^+}:c\mid a, c\mid b有c\mid (a,b)\]

定理4

内容

\[a,b,e\in \mathbb{Z}且(a,b)=d\] \[那么(ae,be)=de\] ### 证明 \[\begin{aligned} (ae,be)&=\min\{mae+nbe:m,n\in \mathbb{Z}\}(定理3)\\ &=\min\{e(ma+nb):m,n\in \mathbb{Z}\}\\ &=e\cdot \min\{ma+nb:m,n\in \mathbb{Z}\}\\ &=e\cdot (a,b)(定理3) \end{aligned}\]

定理5

内容

\[a,b\in \mathbb{Z}且(a,b)=d\] \[那么(\frac{a}{d},\frac{b}{d})=1\]

证明

\[令(\frac{a}{d},\frac{b}{d})=e\] \[(a,b)=de(定理4)\] \[\because (a,b)=d\] \[\therefore e=1\] \[\therefore (\frac{a}{d},\frac{b}{d})=1\]

定理6

内容

\[a,b,c\in\mathbb{N^+}\] \[(a,b)=1,a\mid bc\] \[则a\mid c\]

证明

\[\because (a,b)=1\] \[\therefore \exists d,e\in \mathbb{Z}:da+eb=1\] \[\therefore dac+eac=c\] \[\because a\mid a,a\mid bc\] \[\therefore a\mid ec\times a+f\times bc\] \[\therefore a\mid c\]

定理7(裴蜀定理)

内容

\[a,b,c\in \mathbb{Z},(a,b)=d\] \[\begin{cases} 若d\mathbb{N}mid c,那么方程ax+by=c无整数解\\ 若d\mid c,那么方程ax+by=c有无穷个整数解\\ 若方程有解,所有的解可以表示为 \begin{cases} x=x_0+\frac{b}{d}\cdot n\\ y=y_0-\frac{a}{d}\cdot n \end{cases} (n\in \mathbb{Z},x_0,y_0是方程的一组特解) \end{cases}\] ### 证明 1. \(d\mathbb{N}mid c\)的情况

\[\because d\mid a,d\mid b\] \[\therefore d\mid ax+by\] \[而d\mathbb{N}mid c\] \[\therefore 原方程无解\] 2. \(d\mid c的情况\)

\[由定理3得\exists s,t\in \mathbb{Z}:as+bt=d\] \[\frac{asc}{d}+\frac{btc}{d}=c\] \[\because d|c\] \[\therefore \frac{c}{d}\in \mathbb{Z}\] \[可得特解\begin{cases}x_0=\frac{sc}{d}\\y_0=\frac{tc}{d}\end{cases}\] \[设x',y'是任意一组整数解\] \[\begin{cases} ax'+by'&=&c\\ ax_0+by_0&=&c \end{cases}\] \[两式相减得a(x'-x_0)+b(y'-y_0)=0\] \[a(x'-x_0)=b(y_0-y')\] \[\frac{a}{d}(x'-x_0)=\frac{b}{d}(y_0-y')\] \[\therefore \frac{b}{d}\mid\frac{a}{d}(x'-x_0)\] \[又\because (\frac{a}{d},\frac{b}{d})=1(定理5)\] \[\therefore \frac{b}{d}\mid(x'-x_0)(定理6)\] \[\therefore\exists n\in \mathbb{Z}:\frac{b}{d}\cdot n=x'-x_0\] \[\begin{aligned} \therefore x'&=x_0+\frac{b}{d}\cdot n\\ 同理y'&=y_0-\frac{a}{d}\cdot n \end{aligned}\] \[\therefore原方程的解满足 \begin{cases} x=x_0+\frac{b}{d}\cdot n\\ y=y_0-\frac{a}{d}\cdot n \end{cases}\] ### 说明 原方程(即形如\(ax+by=c(a,b,c\in \mathbb{Z})\))叫做二元线性丢番图方程

定理8

内容

\[a,b\in \mathbb{Z}\] \[a\equiv b\pmod{m}当且仅当\exists m\in \mathbb{Z}:a=b+km\] ### 证明 1. 充分性

\[\because a\equiv b\pmod{m}\] \[\therefore m\mid a-b\] \[\therefore\exists k\in \mathbb{Z}:a-b=km\] \[\therefore a=b+km\] 2. 必要性

\[\because a=b+km(k\in \mathbb{Z})\] \[\therefore a-b=km\] \[\therefore m\mid a-b\] \[\therefore a\equiv b\pmod{m}\]

定理9

内容

\[m\in\mathbb{N^+},模m的同余满足以下性质:\] \[1.自反性:若a\in \mathbb{Z},则a\equiv a\pmod{m}\] \[2.对称性:若a,b\in \mathbb{Z}且a\equiv b\pmod{m},则b\equiv a\pmod{m}\] \[3.传递性:若a,b,c\in \mathbb{Z}且a\equiv b\pmod{m}, b\equiv c\pmod{m},则a\equiv c\pmod{m}\]

证明

1. 自反性

\[\because m\mid0\] \[\therefore m\mid a-a\] \[\therefore a\equiv a\pmod{m}\] 2. 对称性

\[\because a\equiv b\pmod{m}\] \[\therefore \exists k\in \mathbb{Z}:a=b+km\] \[\therefore a-b=km\] \[\therefore b-a=-km\] \[\therefore m\mid b-a\] \[b\equiv a\pmod{m}\] 3. 传递性

\[\because a\equiv b\pmod{m}\] \[\therefore m\mid a-b\] \[\therefore \exists p\in \mathbb{Z}:a-b=pm\] \[同理\exists q\in \mathbb{Z}:b-c=qm\] \[两式相加得a-c=(p+q)m\] \[\therefore m|a-c\] \[\therefore a\equiv c\pmod{m}\]

定理10

内容

\[若a,b,c\in \mathbb{Z},m>0,a\equiv b\pmod{m}\] \[则\begin{cases} a+c\equiv b+c\pmod{m}\\ a-c\equiv b-c\pmod{m}\\ ac\equiv bc\pmod{m} \end{cases}\] ### 证明 1. \(a+c\equiv b+c\pmod{m}\)

\[\because a\equiv b\pmod{m}\] \[\therefore m\mid a-b\] \[\therefore m\mid (a+c)-(b+c)\] \[\therefore a+c\equiv b+c\pmod{m}\] 2. \(a-c\equiv b-c\pmod{m}\)

\[\because a\equiv b\pmod{m}\] \[\therefore m\mid a-b\] \[\therefore m\mid (a-c)-(b-c)\] \[\therefore a-c\equiv b-c\pmod{m}\] 3. \(ac\equiv bc\pmod{m}\)

\[\because a\equiv b\pmod{m}\] \[\therefore m\mid a-b\] \[\therefore m\mid c(a-b)\] \[\therefore m\mid ac-bc\] \[\therefore ac\equiv bc\pmod{m}\]

定理11

内容

\[a,b,c,d,m\in \mathbb{Z},m>0\] \[若a\equiv b\pmod{m},c\equiv d\pmod{m}\] \[则\begin{cases} a+c\equiv b+d\pmod{m}\\ a-c\equiv b-d\pmod{m}\\ ac\equiv bd\pmod{m} \end{cases}\] ### 证明 1. \(a+c\equiv b+d\pmod{m}\)

\[\because a\equiv b\pmod{m}\] \[\therefore\exists p\in \mathbb{Z}:a-b=pm\] \[同理\exists q\in \mathbb{Z}:c-d=qm\] \[两式相加得(a+c)-(b+d)=(p+q)m\] \[\therefore a+c\equiv b+d\pmod{m}\] 2. \(a-c\equiv b-d\pmod{m}\)

\[\because a\equiv b\pmod{m}\] \[\therefore\exists p\in \mathbb{Z}:a-b=pm\] \[同理\exists q\in \mathbb{Z}:c-d=qm\] \[两式相减得(a-c)-(b-d)=(p-q)m\] \[\therefore a-c\equiv b-d\pmod{m}\] 3. \(ac\equiv bd\pmod{m}\)

\[\because a\equiv b\pmod{m}\] \[\therefore\exists p\in \mathbb{Z}:a-b=pm\] \[同理\exists q\in \mathbb{Z}:c-d=qm\] \[\begin{aligned} ac-bd&=ac-bc-bd+bc\\ &=(a-b)c-(b-d)c\\ &=pmc-qmc\\ &=(pc-qc)m \end{aligned}\] \[\therefore m\mid ac-bd\] \[\therefore ac\equiv bd\pmod{m}\]

定理12

内容

\[a,b,c,d\in \mathbb{Z},m>0,d=(c,m)\] \[若ac\equiv bc\pmod{m}\] \[则a\equiv b\pmod{\frac{m}{d}}\]

证明

\[\because ac\equiv bc\pmod{m}\] \[\therefore m\mid(a-b)c\] \[\therefore\exists k\in \mathbb{Z}:c(a-b)=km\] \[\therefore\frac{c}{d}(a-b)=k\frac{m}{d}\] \[\therefore(\frac{c}{d},\frac{m}{d})=1(定理5),\frac{m}{d}\mid\frac{c}{d}(a-b)\] \[\therefore\frac{m}{d}\mid(a-b)(定理6)\] \[\therefore a\equiv b\pmod{\frac{m}{d}}\]

推论

\[a,b,c,m\in \mathbb{Z},(c,m)=1\] \[若ac\equiv bc\pmod{m}\] \[则a\equiv b\pmod{m}\]

定理13

内容

\[若\{r_1,r_2,\dots,r_m\}是一个模m的完全剩余系,且正整数a使得(a,m)=1\] \[则\forall b\in \mathbb{Z}有\{a\cdot r_1+b,a\cdot r_2+b\dots,a\cdot r_m+b\}是一个模m完全剩余系\]

证明

\[设i,j\in([1,m]\cup\mathbb{N})且a\cdot r_i+b\equiv a\cdot r_j+b\pmod{m}\] \[\therefore a\cdot r_i\equiv a\cdot r_j\pmod{m}\space(定理10.2)\] \[\because (a,m)=1\] \[\therefore r_i\equiv r_j\pmod{m}\space(定理12.推论)\] \[又\because一个完全剩余系中的数两两不同余(完全剩余系的定义)\] \[\therefore i=j\] \[\therefore\{a\cdot r_1+b,a\cdot r_2+b\dots,a\cdot r_m+b\}中的数模m两两不同余\] \[\therefore\{a\cdot r_1+b,a\cdot r_2+b\dots,a\cdot r_m+b\}是一个模m完全剩余系\]