整除
定义: 设 a,b 是两个任意的正整数, 其中 b \(\neq\) 0, 若存在一个整数 q, 使得: a=qb
则称 b 整除 a, 记为 b | a.
整除的运算定理
1. 设 a, b, c \(\neq\) 0 是三个整数, 若 c | a, c | b, 则对任意整数 s, t 有: c | (sa+tb)
2. 设 a, b 都是非零整数, 若 a | b,b | a, 则 a = \(\pm\)b
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)}\)互素
来源: http://www.bubuko.com/infodetail-3344046.html