数论

emptysetvvvv · 2019-05-31 00:01:06 · 个人记录

• 【概念】数论是讨论整数性质的数学分支。参考资料：《具体数学》。

• 【概念】整除：对于非零整数a，整数b，若存在整数k满足b=ka，则a整除b，即a\mid b.

1. 最大公约数(\mathtt{greast\ common\ divisor})\qquad \gcd(m,n)=\max\{k\mid k|m,\ k|n\}.

2. 最小公倍数(\mathtt{least\ common\ multiple})\qquad \mathrm{lcm}(m,n)=\min\{k\mid m|k,\ n|k\}.

3. 若 ax+by=1 且 a\mid n,\ b\mid n,\ 则\ ab\mid n.

证明： ∵ab\mid bn,ab\mid an\qquad

∴\forall x,y\in \mathbb Z\quad ab\mid an\cdot x\ +\ bn\cdot y ∵an\cdot x+bn\cdot y=n(ax+by)=n\cdot 1\qquad∴ab\mid n

4. 裴蜀定理：若 a,b\in \mathbb Z,\ d=\gcd(a,b)，则 \forall x,y\in \mathbb Z,\ d\mid ax+by.

推论：方程 ax+by=c 有整数解当且仅当 d\mid c，特别的，a,b互质的充要条件是存在整数 x,y 使 ax+by=1.

证明：若d\nmid c，等式两边同除以d，左式为整数而右式不是，则无解，Qed.

• 【概念】素数：若大于1的正整数 a 的因子仅有 1 和 a 本身，则称 a 为素数，否则为合数，注意 0,1 均不属于任何一方。我们常用p(\mathrm{prime})表示素数。

1. 素数定理：\pi(n)：n以内的素数个数. \pi(n)\sim\displaystyle\frac{n}{\ln n}

2. 孪生素数：相差 2 的素数对。

3. 梅森素数：梅森数是形如 2^p-1 的数。其中的素数称为梅森素数，其是否有无限个还未知。

4. 素数有无限个.

由欧几里得用反证法证明：

假设仅有 k 个素数，从小到大依次为 p_1,p_2,p_3...p_k，令 M=p_1\ p_2\ p_3...p_k+1，

则p_i\nmid M，M为大于p_k的素数，矛盾，Qed.

5. 欧几里得数：e_1=2,\displaystyle e_n=\prod_{i=1}^{n-1} e_i+1.

根据我们对空的乘积的定义，e_1=1+1=2，当然，亦可以解释为第一个素数。

6. 算术基本定理：\forall N\geqslant 2，可以唯一分解成有限个质数的乘积\displaystyle p_1^{\alpha_1}\ p_2^{\alpha_2}\ p_3^{\alpha_3}...p_k^{\alpha_k}，这样的分解称为N的标准分解式.

证明略.

• 【概念】互素：若\gcd(m,n)=1,m,n\in \mathbb Z，则称m,n互素，即m\perp n.

2. 法里级数\mathcal{F}_N （《具体数学》P_{117}）

• 【概念】阶乘：n!=1\times2\times\cdots \times n=\prod_{k=1}^{n}k,n\in \mathbb N.根据我们对空的乘积的约定，0!=1.

1. 阶乘函数以指数方式增长.

证明：n!^2=(1\times2\times\cdots \times n)(n\times \cdots \times 2 \times 1)=\prod_{k=1}^{n}k(n+1-k)

∵n\leqslant k(n+1-k) \leqslant \frac{1}{4}(n+1)^2 ∴\displaystyle\prod_{k=1}^{n}n\leqslant n!^2\leqslant \prod_{k=1}^{n}\frac{(n+1)^2}{4} ∴\displaystyle \sqrt{n^n}\leqslant n! \leqslant \frac{(n+1)^n}{2^n}

\displaystyle\varepsilon_p(n!)=\bigg\lfloor\frac{n}{p}\biggr\rfloor+\bigg\lfloor\frac{n}{p^2}\biggr\rfloor+\bigg\lfloor\frac{n}{p^3}\biggr\rfloor+\cdots=\sum_{k\geqslant 1}\biggl\lfloor\frac{n}{p^k}\biggr\rfloor$. 详见《具体数学》$P_{113}

证明：n 个数中对p的幂的贡献有\lfloor\frac{n}{p}\rfloor，对p^2的贡献有\lfloor\frac{n}{p^2}\rfloor\cdots

3. 秦九韶公式

• 【概念】同余关系\bmod：a,b,m\in \mathbb{Z}，若m\mid a-b，则称 “ a关于模m与b同余 ” ，即a\mod m=b\mod m\Leftrightarrow\ a\equiv b(\bmod\ m)

1. 基本运算中仅有除法不适用于模运算，因为a-b是m的倍数并不意味着(a-b)除以某个数还是m的倍数。为了尽可能小的改变模， \displaystyle a\equiv b(\bmod\ m)\Leftrightarrow\frac{a}{c}\equiv \frac{b}{c}\left(\bmod\frac{m}{gcd(c,m)}\right).

2. 引理\bigstar: m 个数 \ 0,n,2n\cdots (m-1)n 对 m 取模后得到某种次序的 m 个数 \ 0,1,2\cdots m-1，其中n\perp m.

证明：

这是因为 $jn-kn=(j-k)n$ 不是 $m$ 的倍数 所以这 $m$ 个数模 $m$ 的结果互不相同， 由鸽巢原理，其对 $m$ 取模后必然得到 $\ 0,1,2\cdots m-1$ 的某种排列。

3. 费马定理：

证明： 令N=n\cdot 2n\cdots (p-1)n，

由引理\bigstar可知 n,2n\cdots (p-1)n 对 p 取模后得到 1,2\cdots p-1 的某种排列，

则 N\mod p=(n\mod p)\cdot (2n\mod p)\cdots ((p-1)n\mod p)=(p-1)!\mod p\qquad①

又 ∵N=n^{p-1}(p-1)!

由 ① ② 可知 $n^{p-1}(p-1)!\equiv (p-1)!(\bmod\ p)

又∵(p-1)!\perp p

∴n^{p-1}\equiv 1(\bmod\ p)

至此，费马小定理得证，此外，其更一般的形式为 n^p\equiv n(\bmod\ p),n\in \mathbb{Z},p\in\mathrm{prime}.

4. 威尔逊定理：p为素数\Leftrightarrow(p-1)!\ \equiv\ -1(\bmod\ p).

显然 p-1\equiv -1，令A=\{2,3\cdots p-2\}

证明原命题，只需证：

① \forall a\in A,\exists a'\in A满足aa'\equiv1；

② 对于不同a，其对应的a'不同且不为a本身。

由引理$\bigstar$可知 $B$ 模 $p$ 后得到 $C=\{1,2\cdots p-1\}$，因为 $1\in C$，而 $a\cdot 1\not\equiv1$ 且 $a\cdot (p-1)\not\equiv1$，故 $2,3\cdots p-2$ 中一定存在 $a'$ 满足条件，①得证。 若 $aa'\equiv1$ 且 $aa''\equiv1$，则 $aa'\equiv aa''$，$(a''-a')a$ 是$p$的倍数，显然不可能。 若$a^2\equiv 1$，则 $(a+1)(a-1)\equiv 0$ 是 $p$ 的倍数，解得 $a_1=1,a_2=p-1$，均不在集合$A$中。 ②得证。Qed.

其逆命题的证明也很有趣：

若p为合数，设p=ab,a,b\in [1,p-1]。

若a\not=b，则(p-1)!\equiv0(\bmod\ a)且(p-1)!\equiv0(\bmod\ b)，所以

若$a=b$，则 $(p-1)!\equiv0(\bmod\ a)$ 且 $(p-1)!\equiv0(\bmod\ 2a)$，同理可证。 故满足 $(p-1)!\equiv-1(\bmod\ p)$ 的 $p$ 不为合数，即 $p$ 为素数。

5. 费马最后定理，即费马大定理：n>2时，方程x^n+y^n=z^n无整数解。

证明：关于此，我确信已找到了一个极佳的证明，但博客的空白太窄，写不下。