欧拉函数

欧拉函数的定义：1 N1~N 中与 NN 互质的数的个数被称为欧拉函数，记为φ(N)\varphi (N)。欧拉函数公式
如果 n 的唯一分解式:

n=P1a1∗P2a2∗⋯∗Pkakn=P^{a_1}_1*P^{a_2}_2* \cdots * P^{a_k}_k

则:

φ(n)=n∗(1−1p1)∗（1−1p2）∗⋯∗(1−1pk)\varphi(n) = n * (1- \frac{1}{p_1}) *（1-\frac{1}{p_2}）* \cdots *(1-\frac{1}{p_k})

例如φ\varphi(72)，72分解质因数得:

72=23∗3272=2^3*3^2

φ(72)=72∗(1−12)∗(1−13)=72∗12∗23=24\varphi(72)=72*(1-\frac{1}{2})*(1-\frac{1}{3})=72*\frac{1}{2}*\frac{2}{3}=24

裴蜀定理

裴蜀定理，又称贝祖定理(Bézout’slemma)。是一个关于最大公约数的定理。

其内容是:

设a,ba,b是不全为零的整数，则存在整数x,yx,y，使得ax+by=gcd(a，b)ax+ by= gcd(a，b)也就是说对于方程ax+by=gcd(a，b)ax + by = gcd(a，b)，一定存在一组整数解。

裴蜀定理推论
a,ba, b互质⇔gcd(a,b)=1⇔\Leftrightarrow gcd(a, b)=1 \Leftrightarrow存在整数x,yx,y,使得ax+by=1ax + by=1

对于方程 ax+by=zax + by =z，如果满足 d∣zd|z，那么方程一定有整数解，否则无整数解。

证明:

两边同时除以gcd(a，b)gcd(a，b)，

得到:

[a/gcd(a,b)]x+[b/gcd(a,b)]y=z/gcd(a,b)[a/gcd(a, b)]x+ [b/gcd(a, b)]y= z/gcd(a, b)

由于gcd(a,b)gcd(a, b)为a，ba，b的最大公约数，[a/gcd(a,b)]和[b/gcd(a,b)][a/gcd(a, b)]和[b/gcd(a, b)]一定为整数,

要想x，yx，y有整数解，所以z/gcd(a,b)z/gcd(a,b)也一定为整数，所以z一定是gcd(a,b)gcd(a,b)的倍数

对于方程ax+by=1ax + by =1，只有当整数a，ba，b互质时，方程才有整数解。

对于方程ax+by=zax + by = z，只有满足gcd(a,b)∣zgcd(a,b)|z，方程才有整数解.

扩展欧几里得

用于求解方程 ax +by = gcd(a, b)的解

当b=0b=0时ax+by=aax+ by=a,故而一组特解是x=1,y=0x=1,y=0

当b≠0b≠0时

根据式子ax+by=gcd(a,b)ax + by = gcd(a, b)，同理可以得到:

bx+(a mod b)y=gcd(b,a mod b)bx +(a\bmod b)y= gcd(b,a\bmod b)

假设上面两个式子的解分别为(x,y)，(x′,y′)(x,y)，(x',y')，代入得到:

ax+by=gcd(a,b),bx′+(a mod b)y′=gcd(b,a mod b)ax + by = gcd(a, b), bx'+ (a \bmod b)y'= gcd(b, a \bmod b)

因为:

gcd(a,b)=gcd(b,a mod b)gcd(a, b)= gcd(b,a \bmod b)

所以得:

ax+by=bx′+(a mod b)y′ax + by = bx'+(a \bmod b)y'

由于

a mod b=a−−∗ba \bmod b=a--*b

因此

ax+by=bx′+(a−a∗b)yax + by = bx' +(a-a * b)y

整理一下得:

ax+by=ay′+b(x′−∗y′)ax + by = ay' + b(x'- *y')

由等式相等，则各项对应相等，可以得到:

x=y′,y=x′−ab∗y′x=y', y=x'-\frac{a}{b}*y'

解不定方程ax+by=c

若c mod gcd(a,b)=0c\bmod gcd(a, b)= 0,则该方程存在整数解，否则不存在整数解。

因此当c mod gcd(a,b)=0c \bmod gcd(a, b)= 0，先用扩展欧几里得算法求岀ax+by=gcd(a,b)ax + by = gcd(a, b)的一组解x,y1x,y1。

则x2=x1∗cgcd(a,b),y2=y1∗cgcd(a,b)x_2 = x_1 * \frac{c}{gcd(a,b)} , y_2=y_1*\frac{c}{gcd(a,b)}为ax+by=cax+by=c的一组解

求解过程:

ax+by=gcd(a,b)ax + by = gcd(a, b)的一组解为:x1,y1x_1,y_1

ax1+by1=gcd(a,b)ax_1+ by_1 = gcd(a, b)

两边同除 gcd(a b)，再乘以c
即得方程

a∗x1∗cgcd(a,b)+b∗y1∗cgcd(a,b)=ca*x_1*\frac{c}{gcd(a,b)}+b*y_1* \frac{c}{gcd(a,b)}=c

因此

x2=x1∗cgcd(a,b),y2=y1∗cgcd(a,b)x_2=x_1*\frac{c}{gcd(a,b)},y_2=y_1*\frac{c}{gcd(a,b)}

若c mod gcd(a,b)=0c\bmod gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。

因此当c mod gcd(a,b)=0c\bmod gcd(a, b) =0，先用扩展欧几里得算法求出ax+by=gcd(a,b)ax + by = gcd(a, b)的一组解x,yx, y

则x2=x1∗cgcd(a,b),y2=y1∗cgcd(a,b)x_2=x_1*\frac{c}{gcd(a,b)},y_2=y_1*\frac{c}{gcd(a,b)}为ax+by=cax + by =c的一组解。

通解则为:

x=x2+k∗bgcd(a,b),y=y2−k∗agcd(a,b)x=x_2+k*\frac{b}{gcd(a,b)} ,y=y_2-k*\frac{a}{gcd(a,b)}

若令t=bgcd(a,b)t=\frac{b}{gcd(a,b)}则对于xx的最小非负整数解为:

(x2 mod t+t) mod t(x_2\bmod t+t)\bmod t