欧几里得算法

Posted by

这篇是<<What Is Mathematics>>,紫书以及<<算法导论>>中欧几里得以及其扩展内容的笔记.

一些基础的数论概念

素数与合数

首先要有素数合数的概念.

如果一个整数a > 1且只能被平凡约束1和它自身整除,则这个数是素数

如果一个整数a>1且不是素数,则称为合数.要注意的是1既不是素数也不是合数.

公约数与最大公约数

如果d是a的约数并且d也是b的约束,则d是a与b的公约数

在两个不同时为0的整数a与b的公约数中最大的成为其最大公约数

欧几里得算法即gcd算法,就是用来求两个不同时为0的整数的最大公约数的.

下列性质是gcd函数的基本性质:

  1. gcd( a, b ) = gcd( b, a )
  2. gcd( a, b ) = gcd( -a, b )
  3. gcd( a, b ) = gcd( abs(a), abs(b) )
  4. gcd( a, 0 ) = abs( a )
  5. gcd( a, k * a ) = abs( a )

部分相关定理

1.如果任意整数a和b不都为0,则gcd( a, b )是a与b的线性组合集{ a * x + b * y : x, y ∈ Z }中最小的元素.

2.类似于分配律的一个定理,gcd( a * n, b * n ) = n * gcd( a, b ).其中a和b可以是所有整数,n为任意非负整数.

3.对于两个整数a与b只有公约数1,即gcd( a, b ) = 1,则a与b成为互质数

4.对任意整数a, b和p,如果gcd( a, p ) = 1 且 gcd( b, p ) = 1,则gcd( a * b, p ) = 1.

5.唯一因子分解定理,合数a仅能以一种方式写成如下乘积形式:

a = p_1 ^ e_1 * p_2 ^ e_2 *...*p_r ^ e_r

其中p_i为素数,p_1 < p_2 < ... <p_r,且 e_i为正整数.

这条定理还是很重要的.

最大公约数和最小公倍数

原则上讲,可以根据a和b的素因子分解求出正整数a和b的最大公约数gcd( a, b )以及最小公倍数lcm( a, b ),如果有

    \[$a$ = $p_1 ^ e_1 * p_2 ^ e_2 *...*p_r ^ e_r $\]

    \[$b$ = $p_1 ^ f_1 * p_2 ^ f_2 *...*p_r ^ f_r $\]

那么 

    \[gcd( a, b ) =p_1 ^ min(f_1, e_1 ) * p_2 ^ min( f_2, e_2 ) * ... *p_r ^ min( f_r, e_r) \]

             

    \[lcm( a, b ) =p_1 ^ max(f_1, e_1 ) * p_2 ^ max( f_2, e_2 ) * ... *p_r ^ max( f_r, e_r) \]

并且由此不难得到gcd( a, b ) * lcm( a, b ) = a * b

( LaTeX不会用公式都好难打啊 )

GCD递归定理,对任意非负整数a和任意整数b,

gcd( a, b ) = gcd( b, a mod b ).

欧几里得算法代码

int gcd(int a, int b){ return a == 0 ? b : gcd(b % a, a); } 

确实,可以短到一行.这个代码很重要,是那种写时不用想的代码,要记住的.

欧几里得算法的扩展形式

扩展欧几里得算法可以用来解决类似与直线上的点的问题.求直线a * x + b * y + c = 0 上有多少个整点( x, y )满足x[ x_1, x_2 ], y[ y_1, y_2 ].

推广欧几里得算法用于计算出满足下列条件的整系数x和y:

d = gcd( a, b ) = a * x + b * y

注意,x与y可能为0或者负数.我们将发现这些系数对计算模乘法逆元是非常有用的.

例如gcd( 6, 15 ) = 3, 6 * 3 – 15 * 1 = 3,其中x = 3, y = -1.这个方程还有其他解,如x = -2, y = 1.

扩展欧几里得算法代码

void ex_gcd( int a, int b, int &d, int &x, int &y )
{
    if ( !b ) { d = a; x = 1; y = 0; }
    else { ex_gcd( b, a % b, d, y, x ); y -= x * ( a / b ); }
}

对于方程a * x + b * y = gcd( a, b ) 有一组特解( x_0, y_0 ), 假设另一组解为( x_1, y_1 ),则

a * x_1 + b * y_1 = a * x_2 + b * y_2 = gcd( a, b )

a * ( x_1 - x_2 ) = b * ( y_2 - y_1 )

假设gcd( a, b ) = g,方程两边同时除以g.

a' * ( x_1 - x_2 ) = b' * ( y_2 - y_1 )

其中a’ = a / g,b’ = b / 并且a’与b’互素.

因此不难得出x_1 - x_2一定是b’的整数倍( 笔写一下就好了 ),设它为Kb’,计算得

y_2 - y_1 = K * a

那么就有任意整数解

( x_0 + k * b', y_0 - k * a' )

a’ = a / gcd( a, b )   

b’ = b / gcd( a, b )  

   k是任意整数

有了这个结论,移项得a * x + b * y = -c,然后求出一组解即可.

例如 6 * x + 15 * y = 9,求得一组特解( -2, 1 ).两边同时乘以3得到6 * ( -6 ) + 15 * 3 = 9,

即x = -6,y = 3时6 * x + 15 * y = 9

又有 6 * x + 15 = 8,两边同除以3得到2 * x + 5 = 8 / 3.左边是整数,右边不是整数,显然无解.综合起来有下面结论:

设a, b, c为任意整数,g = gcd( a, b ),方程a * x + b * y = g的一组解是( x_0, y_0 ),则当c是g的倍数时a * x + b * y = c的一组解是( x_0 * c / g, y_0 * c / g ),当c不是g的倍数时无整数解.

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注