简单数学3

· · 算法·理论

整除

定义： \exists n\in\mathbb{Z} 使得 an=b，则称 a 整除 b ，记作 a\mid b。

传递性： a\mid b,b\mid c\Rightarrow a\mid c

可加减性：n\mid a,n\mid b\Rightarrow n\mid a\pm b

可乘性： a\mid b,c\mid d\Rightarrow ac\mid bd 特别地，当 c=1 时， a\mid b\Rightarrow a\mid bd 。

例1 求证：8\mid 3^{2n+1}+5

# 最大公因数和最小公倍数 最大公因数： $\gcd(a,b)=\max\{n(n\mid a\land n\mid b)\}$ 若无歧义，$(a,b)=\gcd(a,b)

最小公倍数： \mathrm{lcm}(a,b)=\min\{n(a\mid n\land b\mid n)\} 若无歧义， [a,b]=\mathrm{lcm}(a,b)

带余除法：对于 a,b>0,\exists_1 q,r 使得 a=bq+r(0\le r<b),记作 a\div b=q\cdots r 。

定理1 ：公倍数能被最小公倍数整除，即 a\mid n,b\mid n\Rightarrow\mathrm{lcm}(a,b)\mid n。

证明：令 n\div \mathrm{lcm}(a,b)=q\cdots r ，则 n=q\mathrm{lcm}(a,b)+r 。

因为 a\mid \mathrm{lcm}(a,b),b\mid \mathrm{lcm}(a,b)

所以 a\mid q\mathrm{lcm}(a,b),b\mid q\mathrm{lcm}(a,b)

又因为 a\mid n,b\mid n

所以 a\mid r,b\mid r

因为 0\le r<\mathrm{lcm}(a,b)

所以 r=0

即 \mathrm{lcm}(a,b)\mid n

例1 : 证明： (a,b)=(b,a-b)

我们可以证明一个更强的结论，就是 \{x|x\mid a\land x \mid b\}=\{x|x\mid a-b\land x \mid b\}

证明两个集合相等通常用双包含法。

\forall x\in \{x|x\mid a\land x \mid b\}

所以 x\mid a-b

所以 x\in \{x|x\mid a-b\land x \mid b\}

\forall x\in \{x|x\mid a-b\land x \mid b\}

所以 x\mid a-b+b 即 x\mid a

所以 x\in \{x|x\mid a\land x \mid b\}

所以 \{x|x\mid a\land x \mid b\}=\{x|x\mid a-b\land x \mid b\} ，于是 (a,b)=(b,a-b)

例2 证明：若 a\div b=q\cdots r ,则 (a,b)=(b,r)

a=bq+r (a,b)=(b,a-b)=(b,a-2b)=\cdots=(b,a-qb)=(b,r)

辗转相除法和裴蜀定理

辗转相除法：根据 (a,b)=(b,r) 我们可以不断进行此操作，直至余数为 0 。 此时除数就是答案。

步骤：我们要求 (a,b) ，先令 a_1=a,b_1=b 之后 a_1\div b_1=q_1\cdots r_1 于是 (a_1,b_1)=(b_1,r_1) 再令 a_2=b_1,b_2=r_1 不断进行此操作， 令 a_{i+1}=b_i,b_{i+1}=r_i 直至 r_n=0 。此时 (a,b)=b_n 。

定理2 裴蜀定理： \forall a,b\ne 0,\exists x,y 使得 ax+by=k(a,b)

例3 证明：公因数整除最大公因数。即 n\mid a,n\mid b\Rightarrow n\mid (a,b)

根据裴蜀定理， \exists x,y 使得 ax+by=(a,b)

因为 n\mid a,n\mid b ，所以 n\mid ax+by

所以 n\mid (a,b)

例4 证明：若 (a,b)=1 则， a\mid bc\Rightarrow a\mid c

根据裴蜀定理， \exists x,y 使得 ax+by=(a,b)=1

因为 a\mid bc ，所以 a\mid axc+byc

所以 a\mid c 。

一些恒等式： (a,b,c)=((a,b),c),(a,b)=(a,b,ax),(a,b,c)=((a,b),(a,c))

例5 证明： (2^a-1,2^b-1)=2^{(a,b)}-1

不妨设 a\ge b 。

我们辗转相除 (2^a-1) \div(2^b-1)=2^{a-b}\cdots 2^{a-b}-1， 得 (2^a-1,2^b-1)=(2^b-1,2^{a-b}-1)

类比辗转相除法，不断进行此操作，于是 (2^a-1,2^b-1)=2^{(a,b)}-1

例6 证明：(2^{2^a}+1,2^{2^b}+1)=1

不妨设 a\ge b

\displaystyle (2^{2^a}+1,2^{2^b}+1)=(2^{2^a}-1+2,2^{2^b}+1)=((2^{2^{a-1}}+1)(2^{2^{a-1}}-1)+2,2^{2^b}+1)=\cdots=\Big (\prod_{i=b}^{a}(2^{2^i}+1)\Big )\times (2^{2^b}-1)+2,2^{2^b}+1)=(2,2^{2^b}+1)=1

算数基本定理

质数：满足 p\ge 2,n\mid p\Rightarrow n=1\lor n=p 的 p 为质数。

例1 证明：质数有无穷多个。

我们假设质数有有限多个为 p_1\cdots p_n

令 \displaystyle A= \prod_{i=1}^{n}p_i+1

发现 p_1\cdots p_n\nmid A 矛盾。

例2 若 2^n-1 为质数，则 n 为质数。

显然 n\ne 1 。

假设 n=ab 为合数

由上面的例5得 (2^n-1,2^a-1)=2^{(n,a)}-1=2^a-1 ,所以 2^a-1\mid 2^n-1 矛盾。

例3 若 m\mid (m-1)!+1 则 m 为质数。

因为 2\cdots m-1\nmid (m-1)!+1 ，所以 2\cdots m-1\nmid m

所以 m 为质数。

引理1 若 p\nmid a 则 (p,a)=1

因为 2\cdots p-1 \nmid p,p\nmid a 所以只有 1\mid p\land 1\mid a 所以 (p,a)=1

引理2 算数基本引理：若 p 是质数，则 p\mid ab\Rightarrow p\mid a \lor p\mid b

若 p\nmid a 则 (p,a)=1 。

所以 p\mid ab\Rightarrow p\mid b 。

同理，若 p\nmid b 则 p\mid a

所以 p\mid ab\Rightarrow p\mid a \lor p\mid b 。

定理3 算数基本定理：\forall n>1 可以分解为 \displaystyle n=\prod_{i=1}^{k}p_i^{e_i}(p_i\in \mathbb{P}) 若不考虑 p_i 的顺序， 这种分解方式唯一，将 \displaystyle \prod_{i=1}^{k}p_i^{e_i} 称为 n 的标准分解式。

先证可行性：当 n=2 时显然成立，设当 n=2\cdots k 时成立。当 n=k+1 时，若 k+1 不可分解，则 2\cdots k\nmid k+1 即 k+1 为质数，成立。若 k+1=ab 可分解，可得 2\le a,b\le k 因为 a,b 均可分解，所以 k+1 可分解。

再证唯一性：若 \displaystyle n=\prod_{i=1}^{s}p_i=\prod_{i=1}^{t}q_i

不妨设 s\ge t 。

因为 \displaystyle p_1\mid \prod_{i=1}^{s}p_i=\prod_{i=1}^{t}q_i 。根据算数基本引理，可得 p_1 整除 q_1 到 q_n 中的一个。

不妨设 p_1\mid q_1 于是 \displaystyle \prod_{i=2}^{s}p_i=\prod_{i=2}^{t}q_i 不断进行此操作，可得 \displaystyle \forall i\in[1,s] p_i\mid q_i,\prod_{i=t+1}^{s}p_i=1 于是 s=t 。

同理 \forall i\in[1,t] q_i\mid p_i

于是 \forall i\in[1,t] p_i=q_i 。

定义 v_p(n) 为 n 的标准分解式中含有质因子 p 的指数。

一些性质： v_p(n_1n_2)=v_p(n_1)+v_p(n_2)

若 n_2\mid n_1 则 v_p(\dfrac{n_1}{n_2})=v_p(n_1)-v_p(n_2)

v_p(\gcd(n_1,n_2))=\min(v_p(n_1),v_p(n_2)) v_p(\mathrm{lcm}(n_1,n_2))=\max(v_p(n_1),v_p(n_2)) v_p(n_1+n_2)\begin{cases}=\min(v_p(n_1),v_p(n_2))(v_p(n_1)\ne v_p(n_2))\\ \ge\min(v_p(n_1),v_p(n_2))(v_p(n_1)= v_p(n_2)) \end{cases}

例4 求 v_p(n!)

\displaystyle v_p(n!)=\sum_{i=1}^{\infty}\Big \lfloor \frac{n}{p^i}\Big \rfloor

例5 求 v_p(C_n^m )

**定理4** 若 $\displaystyle n=\prod_{i=1}^{k}p_i^{e_i},m=\prod_{i=1}^{k}p_i^{f_i}$ 则 $m\mid n\Leftrightarrow \forall i\in[1,k] f_i\le e_i

若 \displaystyle n=\prod_{i=1}^{k}p_i^{e_i} 。

因数个数公式： \displaystyle d(n)=\prod_{i=1}^{k}(e_i+1)

因数和公式： \displaystyle \sigma(n)=\prod_{i=1}^{k}\frac{p_i^{e_i+1}-1}{p_i-1}

因数倒数和公式： \dfrac{\sigma(n)}{n}

因数积公式：n^{\frac{d(n)}{2}}

例6 求分数 \displaystyle \frac{\prod_{i=1}^{100}(\sum_{j=1}^{i}j^2)}{100!} 的分母。

根据平方和公式得 \displaystyle \frac{\prod_{i=1}^{100}\frac{i(i+1)(2i+1)}{6}}{100!}=\frac{\prod_{i=1}^{100}i(i+1)(2i+1)}{6^{100}100!}=\frac{100!101!\prod_{i=1}^{100}(2i+1)}{6^{100}100!}=\frac{101!\prod_{i=1}^{100}(2i+1)}{6^{100}}

因此只要考虑因子 2 和 3 。

因为 \displaystyle \prod_{i=1}^{100}(2i+1) 不含因子 2 所以 v_2(6^{100})=100,v_2(101!)=97 分母含因子 8.

一种比较巧妙的想法是补一个 $2^{101}$ 上去，结果不变。 于是原式 $\displaystyle =v_3(2^{101}\times 101!\times \prod_{i=1}^{100}(2i+1))=v_3(\prod_{i=1}^{101}(2i)\times \prod_{i=1}^{100}(2i+1))=v_3(202!)=98

所以分母为 8\times 9=72 。

定理5 若 \displaystyle a=\prod_{i=1}^{k}p_i^{e_i},b=\prod_{i=1}^{k}p_i^{f_i} 则 \displaystyle (a,b)=\prod_{i=1}^{k}p_i^{\min(e_i,f_i)},[a,b]=\prod_{i=1}^{k}p_i^{\max(e_i,f_i)}

一些恒等式： (ma,mb)=m(a,b),(a,uv)=(a,(a,u)v),(u,v)=1\Rightarrow (a,uv)=(a,u)(a,v),(a,b)=(c,d)=1\Rightarrow (ab,cd)=(a,c)(a,d)(b,c)(b,d),(a,b)=1\Rightarrow (a^k,b^k)=1

例7 求证： (m,n)[m,n]=mn

\displaystyle m=\prod_{i=1}^{k}p_i^{e_i},n=\prod_{i=1}^{k}p_i^{f_i}$ 则 $\displaystyle (m,n)=\prod_{i=1}^{k}p_i^{\min(e_i,f_i)},[m,n]=\prod_{i=1}^{k}p_i^{\max(e_i,f_i)},(m,n)[m,n]=\prod_{i=1}^{k}p_i^{\min(e_i,f_i)+\max(e_i,f_i)}=\prod_{i=1}^{k}p_i^{e_i+f_i}=mn