数论算法:基础数论概念

数论算法中有几个重要的定理,这里先对这部分定理进行证明。

数论基本定理

1)若$a>b>0$,且$c=a+b$,则 $c \ mod \ a=b$
证明:$c \ mod \ a \ =(a+b) \ mod \ a = 0+(b \ mod \ a) $
因为$a>b>0$,所以$b \ mod \ a = b$

2)证明有无穷多个素数
证明: 假设$2,3,4,5, \cdots ,p$是无穷多个素数组成的集合,并且令
$q=2 \times 3 \times 5 \times \cdots \times p+1$,则可以发现$q$不能够被$2,3,5 \cdots , p$中的任何一个整除。

$q$要么是一个素数,要么能够被$p \cdots q$中的任何一个素数整除。
无论哪种情形,肯定有大于$q$的素数存在。

3) 证明:如果$a|b$且$b|c$,则$a|c$
证明: 可知$b=k_1a$,$c=k_2b$,则$c=k_1k_2a$,原式成立。

4)证明:如果$p$是素数并且$0<k<p$,则$gcd(k,p)=1$
证明: 这是显然成立的,依据素数的定义

5) 证明: 对任意的正整数$n,a,b$,如果$n|ab$且$gcd(a,n)=1$,则$n|b$
证明: 由题中条件可以知道:$ab=kn$,存在$x,y$, 使得$ax+ny=1$
因为$gcd(a,n)=1$,$k/a$是一个整数。
所以$b=n(k/a)=k_1n$,其中$k_1=k/a$
所以很显然$n|b$

6) 证明:如果$p$是素数,且$0<k<p$,则$p|{p \choose k}$,证明若对所有的整数$a,b$和素数$p$,有
$(a+b)^p \equiv a^p+b^p (mod \ p)$

证明:这个结论可以由$(a+b)^p$的二项展开式显然得出

7) 证明:如果$a$和$b$是任意正整数,且满足$a|b$,则对任意$x$
$(x \ mod \ b) \ mod \ a = x \ mod \ a$
在相同的假设下,证明对任意整数$x,y$,如果$x \equiv y (mod \ b)$,则 $x \equiv y(mod \ a)$

证明:从完全剩余系的观点来理解。
$x \ mod \ a$可以写出$x \in [\cdots,l-a,l,l+a,\cdots]$
$(x \ mod \ b) = (x \ mod \ ka) =l$
$(x \ mod \ b) \ mod \ a = l \ mod \ a = l$

$此时x \equiv y \equiv l(mod \ b)$
而很显然$x \in [\cdots,l-a,l,l+a,\cdots]$
可以得出$x \equiv l \ (mod \ a)$

8) 证明一系列等式

利用一部分结论:
$a= \prod_p p^{\alpha} \quad (\alpha \geq 0)$
$b= \prod_p p^{\beta} \quad (\beta \geq 0)$
$gcd(a,b)= \prod_p p^{min(\alpha, \beta)}$

上述结论的证明,可以利用素数的唯一分解定理。
由此可以知道,
1)$gcd(a,b)=gcd(b,a)$

2)$-a=- \prod_p p^{\alpha} \quad (\alpha \geq 0)$
$b= \prod_p p^{\beta} \quad (\beta \geq 0)$
$gcd(-a,b)= \prod_p p^{min(\alpha, \beta)}=gcd(a,b)$

3)$|a|=\pm \prod_p p^{\alpha} \quad (\alpha \geq 0)$
$|b|=\pm \prod_p p^{\beta} \quad (\beta \geq 0)$
$gcd(a,b)= \prod_p p^{min(\alpha, \beta)}=gcd(|a|,|b|)$

4)$gcd(a,ka)$
可知,$a=\prod_p p^{\alpha} \quad (\alpha \geq 0)$
$ka=\prod_p p^{\alpha+\alpha_{0}}$
$min(\alpha, \alpha+\alpha_{0})=\alpha$
$gcd(a,ka)=|a|$

9) 证明:最大公约数满足结合律,对所有的整数$a,b,c$有:
$gcd(a,gcd(b,c))=gcd(gcd(a,b),c)$

由以上分析可知:
$a=\prod_p p^{\alpha} \quad b=\prod_p p^{\beta1} \quad c=\prod_p p^{\beta2}$
$gcd(a,gcd(b,c))=gcd(gcd(a,b),c)=\prod_p p^{min(\alpha,\beta1,\beta2)}$

10)素数唯一分解定理
证明:如果$p$是素数,并且$p|ab$,那么$p|a$或者$p|b$
假设某个数可以被分解成$ab$,那么由于$p|a$,则$a$可以继续往下分解。

更严格的证明表述如下:
$n=p_1p_2p_3 \cdots = q_1q_2 \cdots \quad (p_i \neq q_j)$
$p_1$最小,则$p_1^2 \leq n$
$q_1$最小,则$q_1^2 \leq n$
因为$p_1q_1<n$,则$N=n-p_1q_1=p_1q_1(m-1)$
可见$N$只有一种分解$p_1,q_1,m-1$

$p_1|n$,则$p_1|N$
$q_1|n$,则$q_1|N$
$(p_1q_1)|N \quad (p_1q_1)|n$
$q_1|(n/p_1)$
则$q_1|(p_2p_3\cdots)$,但q与p各不相同,矛盾