欧几里得算法Euclid Algorithm

@2014-01-01

辗转相除法

Euclid

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
    return a

Keypoint

带余除法,我们设b是大数,a是小数。q是quotient,r是remainder

$$\color{red}{b}=q\times a+r$$

关键之处在于 $(b,a)=(a,r)\cdots (d,0)$

也就是怎么个辗转法,所谓辗转,就是交换+反复

实例

最大公因子Greatest Common Divisor


欧几里得算法_1.png

欧几里得算法_2.png


欧几里得算法_3.png


欧几里得算法_4.png


欧几里得算法_5.png


欧几里得算法_6.png


欧几里得算法_7.png

欧几里得算法_8.png


欧几里得算法_9.png

欧几里得算法_10.png

Programming

step1 排序,大数在前,小数在后


欧几里得算法_11.png

欧几里得算法_12.png

step2 带余除法中的余数r


欧几里得算法_13.png


欧几里得算法_14.png

欧几里得算法_15.png


欧几里得算法_16.png


欧几里得算法_17.png

欧几里得算法_18.png

欧几里得算法_19.png

欧几里得算法_20.png

两个多项式的结式

    形如$P(w,z)=0$的方程对于每一个z有有穷多个解$w_1(z),\cdots ,w_m(z)$,其中P为一个二变量的多项式. 我们证明,这些根可以解释为一个全局解析函数$f(z)$的各个值,因此称$f(z)$为代数函数. 反之,如果给定了一个全局解析函数,则要明确它是否满足一个多项式方程.

定理 设$P(w,z)$$Q(w,z)$是两个互质的多项式,则只有有穷多个$z_0$的值可使方程$P\left(w,z_0\right)=0$$Q\left(w,z_0\right)=0$具有一个公共根.

PQ均按w的降幂排列,并令$Q(w,z)=b_0(z)w+\cdots +b_m(z)$,其中$b_0(z)$不恒等于零. 如果以QP,则得一个商及一个余数,它们都是w的多项式,并且是z的有理函数. 我们建立欧几里得辗转相除法如下:

$欧几里得算法_21.gif$

其中$q_k$$R_k$都是wz的多项式,而$c_k$z的多项式,用以消除分式. $R_k$w的次数是递降的,而R则只是z的多项式. 如果R恒等于零,是根据惟一因子分解定理,从上式中的最后一式可知,$R_{n-2}$将能被$R_{n-1}$的任意不可约因子所除尽,其中$R_{n-1}$w的正幂多项式. 根据同样推理,逐步推论下去,可知所有的$R_k$以及PQ都将被同一因子除尽. 这与假设相矛盾,因为$R_{n-1}$w的正幂多项式,因此必具有一个包含w的不可约因子.

现在设$P\left(w_0,z_0\right)=0$$Q\left(w_0,z_0\right)=0$. 将这些值代入上式,得到$R_1\left(w_0,z_0\right)=0,\ldots ,R_{n-1}\left(w_0,z_0\right)=0$,最后有$R_n\left(z_0\right)=0$. 但因为$R_n$不恒等于零,故所有只有有穷个$z_0$可满足这一条件,从而定理得证.