数论笔记【1】

整除与素数的定义

定义1.1 若对于 \(x,y\in\mathbb{Z}\) ，\(\exists z\in\mathbb{Z}\) ，使得 \(xz=y\) ，则称 \(y\) 可以被 \(x(x\ne 0)\) 整除，当它们都大于 \(0\) 时记作

\[x\ |\ y \]

此时，我们称 \(x\) 为 \(y\) 的一个因子。

若 \(x\) 不能整除 \(y\) ，则记作 \(x\nmid y\) 。我们可以得到一些整除的性质

性质1.1 若 \(x\ |\ y,y\ |\ z\) ，则 \(x\ |\ z\) .

性质1.2 若 \(x\ |\ y\) ，则 \(xz\ |\ yz(z\ne 0)\) ，反过来也一样。

性质1.3 若 \(c\ |\ a,c\ |\ b\) ，则 \(c\ |\ (ma+nb)\)

性质1.4 若 \(a\ |\ (x+y)\) ，且 \(a\nmid x\) ，则 \(a\nmid y\) .

下面我们定义素数

定义1.2 若 \(p>1\) 只有 1 和自己两个因子，则称 \(p\) 为素数，否则称为合数。

定理1.1 每个大于 \(1\) 的数都可以被表示成形如 \(p_1p_2p_3\cdots p_n\) 的素数相乘的形式。

证明：用归纳法。由定义，\(2\) 为素数，故 \(2=p_1=2\) ，符合。当 \(n=k>2\) 时，假设对于 \(2 \le k<n\) 时都成立。由定义， 存在 \(a,b\) 使得 \(n=ab\) ，且 \(\max\{a,b\}<n\) .故 \(a,b\) 可分别表示成 \(a=p_1p_2p_3\cdots p_s,b=q_1q_2q_3\cdots q_t\) ，得到 \(n=p_1p_2p_3\cdots p_sq_1q_2q_3\cdots q_t\) . \(\Box\)

有了这个定理，我们就可以证明存在无限个素数。

定理1.2(Euclid定理) 素数有无限个。

证明：假设存在有限个素数，设它们为 \(p_1p_2p_3\cdots p_n\) ，令 \(p=1+\prod_{i=1}^np_i\)

由定理1.1知，\(\exists p_j(1\le j\le n),p_j\ |\ p\) ，由性质1.4得，这是不存在的 \(p_i\nmid1\) 但\(p_j\ |\ \prod_{i=1}^np_i\) .得到矛盾。 \(\Box\)

我们记所有素数的集合为 \(\mathbb{P}\) .

辗转相除

下面我们定义公约数

定义1.3 我们称 \(d\) 是 \(a,b\) 的公约数，当且仅当

\[d\ |\ a,d\ |\ b \]

特别的，满足这个性质的最大的数 \(d^{\prime}\) 称为 \(a,b\) 的最大公约数。记作

\[d^{\prime}=\gcd(a,b) \]

为了求解最大公约数，我们可以得到一个算法，名为辗转相除法。辗转相除法的描述依赖于带余除法。

定义1.4 对于一个被除数 \(a\) 与除数 \(b\) ，带余除法给出常数 \(q,r\) 使得满足等式

\[a=qb+r \]

其中 \(0\le r<a\) .我们称 \(q\) 为商，\(r\) 为余数。

有了带余除法，可以找出一个求解最大公约数的方式

定理1.3(辗转相除法) 对于 \(a,b\) ，先用 \(b\) 除 \(a\) (带余除法)，记为 \((1)\) ，现在归纳的假设式 \((k-1)\) 已经被定义，则式 \((k)\) 则是用式 \((k-1)\) 的除数与余数分别作为 \((k)\) 式的被除数与除数。当余数为 \(0\) 时停止，即

\[\begin{align} a&=q_0b+r_0\\ b&=q_1r_0+r_1\\ r_0&=q_2r_1+r_2\\ \nonumber &\cdots\\ r_{n-2}&=q_nr_{n-1}+r_n\tag{n+1}\\ r_{n-1}&=q_{n+1}r_n\tag{n+2}\\ \end{align} \]

则 \(r_n=(a,b)\) .

证明：由余数定义知 \(r_i\) 严格递减，故递归会在有限次停止。下证 \(r_n=(a,b)\) . 将 \(\rm (n+2)\) 代入 \(\rm(n+1)\) 得到 \(r_{n-2}=(q_nq_{n+1}+1)r_n\) ，即 \(r_{n-2}|r_n\) . 同理，再代入 \(\rm(n)\) ，得到 \(r_{n-3}|r_n\) ，以此类推，得到 \(b\ |\ r_n\) 且 \(a\ |\ r_n\) ，即 \(r_n\) 是 \(a,b\) 的公约数，于是 \(r_n \le\gcd(a,b)\) . 设 \(g\) 是 \(a,b\) 的公约数，则由 \(r_0=a-q_0b\) 得到 \(g\ |\ r_0\) .同理，运用数学归纳法得 \(g\ |\ r_n\) ，于是又有 \(r_n\ge\gcd(a,b)\) .两个不等式同时成立当且仅当 \(r_n=\gcd(a,b)\) . \(\Box\)

算数基本定理

由定理1.1我们知道了每个数都可以被分解为素数相乘的形式。而算数基本定理表明这种分解在不考虑顺序的情况下是唯一的。为了证明这个定理，我们需要先证明一些引理。

定理1.4(裴蜀定理) 关于 \(x,y\in\mathbb{Z}\) 的方程 \(ax+by=d\) 有解，其中 \(d=\gcd(a,b)\) .

证明：在定理1.3中，\(r_0=a-q_0b\) ，代入 \((2)\) 中得 \(b=q_1(a-q_0b)+r_1\) ，即\(r_1=(-q_1)a+(q_0+1)b\) .以此类推，得 \(r_2,r_3\dots r_n\) 都可以被表示成 \(ax+by\) 的形式，易见证明完成。 \(\Box\)

引理1.1 对于 \(p\in\mathbb{P}\) ，若 \(p\ |\ ab\) ，则 \(p\ |\ a\) 或 \(p\ |\ b\) .

证明：不妨设 \(p\nmid a\) ，则由裴蜀定理，\(\exists x,y\in\mathbb{Z}，px+ay=1\) ，等式两边同乘 \(b\) ，得 \(pbx+aby=b\) .由 \(p\ |\ ab\) 得 \(\exists m\in \mathbb{N},mp=ab\) ，代入得 \(p(bx+my)=b\) ，即 \(p\ |\ b\) .

推论1.1 若 \(p\ |\ a_1a_2\cdots a_n\) ，则 \(\exists 1\le i\le n,p\ |\ a_i\) .

最后，我们证明算术基本定理

定理1.5(算术基本定理) 每个大于 \(1\) 的数都可以在不考虑顺序的情况下唯一地被分解为 \(p_1p_2p_3\cdots p_n\) 的形式。

证明：存在性已经证明，现在证明唯一性。假设

\[n=p_1p_2p_3\cdots p_n=q_1q_2q_3\cdots q_m \]

其中 \(p_1p_2p_3\cdots p_n\) 和 \(q_1q_2q_3\cdots q_n\) 是两个(不考虑顺序)不同的素数乘积。则约去其中相同的项，不失一般性地假设得到

\[p_1p_2p_3\cdots p_s=q_1q_2q_3\cdots q_t \]

则 \(p_1|q_1q_2q_3\cdots q_t\) 但是 \(\forall 1\le i\le t,p\nmid q_i\) ，这与推论1.1矛盾。 \(\Box\)