整数的可除性

整除

Eratoshenes筛法

定理：设n是一个正合数，p是n的一个大于1的最小正因数，则p一定是素数且 $p\leq\sqrt{n}$
Eratoshene筛法：设n是正整数，如果对所有素数 $p\leq\sqrt{n}$ 都有p $\nmid$ n，则n一定是素数。

证明：显而易见，如果第一个定理是成立的，那么就很容易得到Eratoshenes筛法，所以这里只需要证明第一个定理
反证法，假设n的大于1的最小正因数p是合数，那么显然 $\exists$ q>1， q | p，则有q | n，所以q也是n的一个大于1的正因数，且q<p，这与p是n的大于1的最小正因数的前提相违，故p是素数。
对于第二个部分同样使用反证法，假设n的大于1的最小正因数 $p>\sqrt{n}$ ，因为p是n的因数，所以可以设n=pq
$\because$ p是n的最小正因数
$\therefore q>p>\sqrt{n}$
则 $pq>\sqrt{n}*\sqrt{n}=n$ ，这与前提条件相违背
故 $p\leq\sqrt{n}$

欧几里得除法

设a，b是两个整数，其中b>0，则存在唯一的整数q，r，使得a=qb+r且 $0\leq r <b$

证明：存在性
可以将数轴分成无数个长度为b的区间，即 $\cdots,-2b,-b,0,b,2b,\cdots$
则整数a必然落在其中的一个区间上
$\therefore\exists q$ 使得 $qb\leq a < (q+1)b$
令 $r=a-qb$ ，则 $a=qb+r$
唯一性
假设分别有整数 $q,r,q_1,r_1$ 使得：
$a=qb+r$ $(0\leq r<b)$
$a=q_1b+r_1$ $(0\leq r_1<b)$
则 $(q-q_1)b=-(r-r_1)$
如果 $q\neq q_1$ 则 $|(q-q_1)b|\geq b$ ，而 $|-(r-r_1)|<b$ ，显然矛盾
故 $q=q_1$ $r=r_1$

定理：设a,b,c是三个全不为零的整数，如果存在整数q使得a=qb+c，则(a,b)=(b,c)

证明：设d=(a,b)，则d | a，d | b，由整除的运算定理可知：
d | (a-qb)，d | c
$\therefore$ d是b，c的一个公因数
设d'=(b,c)，则d $\leq$ d'且d' | b，d' | c
则d' | (qb+c)，d' | a
$\therefore$ d'是a,b的一个公因数，则d' $\leq$ d
$\therefore$ d=d'
即(a,b)=(b,c)

广义欧几里得除法：设a,b是两个任意的正整数，记 $r_{-2}=a, r_{-1}=b$ ，则反复运用欧几里得除法有：
$r_{-2}=q_0r_{-1}+r_0$
$r_{-1}=q_1r_0+r_1$
$\dots$
$r_{n-1}=q_{n+1}r_n+r_{n+1}$
$r_n=q_{n+2}r_{n+1}+0$
则 $r_{n+1}$ 是a,b的最大公因数
通过上面的定理就很容易得到广义欧几里得除法的证明
贝祖等式：设a,b是任意的两个正整数，则存在整数s,t使得sa+tb=(a,b)

贝祖等式的证明同样可以由广义欧几里得除法得到，因为广义欧几里得除法得出了一系列的等式，而 $r_{n+1}$ 就等于(a,b)，那么在上面的等式用 $r_{n+1}$ 依次向上取代便可得到贝祖等式

定理：整数a,b互素的充分必要条件是存在整数s,t使得sa+tb=1

证明：必要性，不难证明，(a,b)=1 $\rightarrow$ sa+tb=1
充分性
设d | a, d | b
$\because$ sa+tb=1
$\therefore$ d | (sa+tb) = 1
$\therefore$ d = 1
也就是说只有1能够同时整除a,b，即(a,b)=1

算术基本定理

任意整数n>1都可以表示成素数的乘积，且不考虑乘积顺序的情况下，该表达式是唯一的，即 $n=p_1\cdots p_s$ ，其中 $p_1\leq\cdots\leq p_s$
标准分解式：任意整数n>1可以唯一的表示成： $n=p_1^{a_1}\cdots p_s^{a_s}$ ，其中 $a_i$ >0， $p_i<p_j(i<j)$ 是素数。

定理：设a,b是两个正整数，且都有素数因数分解式
$a=p_1^{a_1}\cdots p_s^{a_s}$
$b=p_1^{b_1}\cdots p_s^{b_s}$
则a,b的最大公因数和最小公倍数为：
$(a,b)=p_1^{\varphi_1}\cdots p_s^{\varphi_s}$ ，其中 $\varphi_i=min(a_i,b_i),i=1,\dots,s$
$[a,b]=p_1^{\psi_1}\cdots p_s^{\psi_s}$ ，其中 $\psi_i=max(a_i,b_i),i=1,\dots,s$

推论1：(a,b)[a,b]=a,b

证明.
$\because(a,b)=p_1^{\varphi_1}\cdots p_s^{\varphi_s}$
$[a,b]=p_1^{\psi_1}\cdots p_s^{\psi_s}$
$\therefore (a,b)[a,b]=p_1^{\varphi_1+\psi_1}\cdots p_s^{\varphi_s+\psi_s}$
而 $\varphi_i=min(a_i,b_i)$ ， $\psi_i=max(a_i,b_i)$
$\because max(a,b)+min(a,b)=a+b$
$\therefore \varphi_i+\psi_i=a_i+b_i$
$\therefore (a,b)[a,b]=p_1^{a_i+b_i}\cdots p_s^{a_s+b_s}=ab$

推论2： $\frac{a}{(a,b)}$ 与 $\frac{b}{(a,b)}$ 互素

证明.
$\because (a,b)=p_1^{\varphi_1}\cdots p_s^{\varphi_s}(\varphi_i=mid(\alpha_i,\beta_i))$
$\therefore \frac{a}{(a,b)}=p_1^{\alpha_1-mid(\alpha_1,\beta_1)}\cdots p_s^{\alpha_s-mid(\alpha_s,\beta_s)}$
$\frac{b}{(a,b)}=p_1^{\beta_1-mid(\alpha_1,\beta_1)}\cdots p_s^{\beta_s-mid(\alpha_s,\beta_s)}$
$\because mid(a-mid(a,b),b-mid(a,b))=0$
$\therefore (\frac{a}{(a,b)},\frac{b}{(a,b)})=p_1^0\cdots p_s^0=1$
即 $\frac{a}{(a,b)}$ 与 $\frac{b}{(a,b)}$ 互素

整数的可除性

整除

Eratoshenes筛法

欧几里得除法

算术基本定理

推荐阅读更多精彩内容