这篇是<
一些基础的数论概念
素数与合数
首先要有素数和合数的概念．
如果一个整数a > 1且只能被平凡约束1和它自身整除，则这个数是素数．
如果一个整数a>1且不是素数，则称为合数．要注意的是1既不是素数也不是合数.
公约数与最大公约数
如果d是a的约数并且d也是b的约束，则d是a与b的公约数．
在两个不同时为0的整数a与b的公约数中最大的成为其最大公约数．
欧几里得算法即gcd算法，就是用来求两个不同时为0的整数的最大公约数的．
下列性质是gcd函数的基本性质：
- gcd( a, b ) = gcd( b, a )
- gcd( a, b ) = gcd( -a, b )
- gcd( a, b ) = gcd( abs(a), abs(b) )
- gcd( a, 0 ) = abs( a )
- gcd( a, k * a ) = abs( a )
部分相关定理
１．如果任意整数a和b不都为0，则gcd( a, b )是a与b的线性组合集{ a * x + b * y : x, y ∈ Ｚ }中最小的元素．
２．类似于分配律的一个定理，gcd( a * n, b * n ) = n * gcd( a, b )．其中a和b可以是所有整数，n为任意非负整数．
３．对于两个整数a与b只有公约数1，即gcd( a, b ) = 1，则a与b成为互质数．
４．对任意整数a, b和p，如果gcd( a, p ) = 1 且 gcd( b, p ) = 1，则gcd( a * b, p ) = 1．
５．唯一因子分解定理，合数a仅能以一种方式写成如下乘积形式：
[latexpage]
$a$ = $p_1 ^ e_1 * p_2 ^ e_2 *…*p_r ^ e_r $
[latexpage]
其中$p_i$为素数，$ p_1 < p_2 < … <p_r $，且 $e_i$为正整数．
这条定理还是很重要的．
最大公约数和最小公倍数
原则上讲，可以根据a和b的素因子分解求出正整数a和b的最大公约数gcd( a, b )以及最小公倍数lcm( a, b )，如果有
[latexpage]
\[$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); }
确实，可以短到一行．这个代码很重要，是那种写时不用想的代码，要记住的．
欧几里得算法的扩展形式
[latexpage]
扩展欧几里得算法可以用来解决类似与直线上的点的问题．求直线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 ); }
}
[latexpage]
对于方程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 ) + 15 * 3 = 9,
即x = -6,y = 3时6 * x + 15 * y = 9
又有 6 * x + 15 = ８，两边同除以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的倍数时无整数解．