扩展欧几里得算法应用


求解不定方程


$$ax + by = c$$
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void exgcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
return;
}

扩展欧几里得求出来的是方程
证明
\begin{align*}
\because ax + by = gcd(a,b)\\
\therefore bx + (a% b)\times y = gcd(a%b, b)\\
\therefore bx + (a - \frac{a}{b} \times b)\times y = gcd(a,b)\\
\therefore ay + b(x - \frac{a}{b} \times y) = gcd(a,b)\\
\end{align*}

当且仅当 d|c 时,不定方程 ax + by = c 有解
$$gcd(a’,b’) = 1$$
ex_gcd 求解方程
$$a’x’ + b’y’= 1$$
\begin{align*}
a’x’c’ + b’y’c’ = c’\\
a’x’c’d + b’y’c’d = c’d\\
ac’x’ + bc’y’ = c\\
\end{align*}
则方程的一组解为
$$x_0 = c’x’,y_0 = c’y’$$
因为
$$ a’x + b’y = c’\Leftrightarrow a ’ x \equiv c ‘\pmod {b’} $$
所以x是模b‘同余的一个剩余类,所以该不定方程的通解为
$$x = x_0 + b’ n, y = y_0 - a’ n (n ∈ z)$$


线性同余方程


给定整数 a,b,m ,求一个整数 x 满足
$$a \times x \equiv b \pmod m$$
或者给出无解。
该式等价于
$$a \times x + m \times y = b​$$
定理1

a,b,m是整数且m > 0,gcd(a,m) = d, 如果d|b,则方程恰有d个模m不同余的解,否则方程无解。

假设 x0是方程的任意一个解,方程的d个不同解分别为
$$x_i = x_0 + i \times (m/d) (0 \le i \le d - 1)$$

定理2

若gcd(a,m) = 1,则称 ax ≡ 1(mod m)
的一个解为a mod b的逆
当且仅当gcd(a,m)=1时方程才有解,于是其所有的解均模b同余

求关于x的同余方程 ax ≡ 1(mod m) 的最小正整数解
最小正整数解:
$$(x % b’ + b’) % b’$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>  
#include <cstdio>
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b);
k=x;
x=y;
y=k-a/b*y;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin>>a>>b;
exgcd(a,b);
cout<<(x+b)%b;
}

费马小定理


当p为质数时,对于任意整数a

\begin{align*}
a^{p}\equiv a\pmod p\\
a ^{p-1} \equiv 1 \pmod p\\
a ^{p-2} = a ^{-1} \pmod p\\
\end{align*}
证明 luogu
性质1:p-1个整数a,2a,3a,…(p-1)a 中没有一个是p的倍数
性质2:a,2a,3a,…(p-1)a 中没有任何两个同余与模p的
所以a,2a,3a,…(p-1)a 对模p的同余既不为零,也没有两个同余相同
因此,这p-1个数模p的同余一定是a,2a,3a,…(p-1)a 的某一种排列

$$a,2a,3a,…(p-1)a \equiv {1,2,3,…,p-1}! \pmod p$$
化简为
$$a^{p-1}\times (p-1)! \equiv {p-1}! \pmod p$$
根据威尔逊定理可知(p-1)!与p互质,所以同时约去(p-1)!
即得到
$$a^{p-1}\equiv 1 \pmod p$$


乘法逆元


整数b,p互质,并且b|a,则存在一个整数,使得
$$\frac{a} {b} \equiv a \times x \pmod p$$
则称x为b的模p乘法逆元,记为
\begin{align*}
b ^{-1}\pmod p\\
\because
\frac{a}{b}\equiv a\times b^{-1} \equiv \frac {a}{b} \times b \times b ^{-1}\pmod p\\
\therefore
b \times b^{-1} \equiv 1 \pmod p\\
\end{align*}
注意这里的b ^ (-1)是 modp 意义下的
若p为质数,并且b < p,根据费马小定理
\begin{align*}
b^{p-1} \equiv 1 \pmod p\\
b \times b^{p-2} \equiv 1\pmod p\\
\end{align*}
因此,当模数p为质数时,b^(p-2)即为b的乘法逆元
若仅保证b,p互质,则乘法逆元可以通过求解同余方程得到
\begin{align*}
x \equiv b ^ {-1} \pmod p\\
b x\equiv 1\pmod p\\
\end{align*}
当然,前提是b,p互质,当p为质数时,等价于b不是p的倍数


解同余方程组

tips :lcm(a,b) = a*b/gcd(a,b)

  • 理解 1
    利用数学归纳法,假设已经求出了前k-1个方程构成的方程组的一个解x0,则前k-1个方程组的通解为
    \begin{align*}
    m = lcm (m_1, m_2, … , m_{k-1})\\
    x = x_0 + i \times m (i \in Z)\\
    \end{align*}
    考虑第k个方程,求出一个整数t,使得
    $$x + t \times m \equiv a_k \pmod {m_k}$$
    然后求解,若有解,则
    $$x’ = x + t \times m $$
    就是前k个方程构成的方程组的一个解
  • 理解2
    poj2891 扩展欧几里得解同余方程组
    \begin{align*}
    x≡r_1\pmod {a_1}\\
    x≡r_2\pmod {a_2}\\
    …\\
    x≡r_n\pmod {a_n}\\
    \end{align*}
    其中模数不一定互质。
    这里我们先考虑两个方程:
    \begin{align*}
    x≡r_1\pmod {a_1}\\
    x≡r_2\pmod {a_2}\\
    \end{align*}
    我们可以写成:
    \begin{align*}
    x + y_1 a_1 = r_1 \\
    x - y_2 a_2 = r_2\\
    \end{align*}
    两式相减得
    $$y_1 a_1+y_2 a_2=r_1-r_2$$
    也就是普通不定方程
    $$ax+by=m$$
    这是可以用扩展欧几里德解的。
    若 ! ( gcd (a,b) | m ) 那么方程就无解,直接输出-1。
    否则我们可以解出上式的y1。
    回带得到一个特解
    $$x_0 = r_1-y_1 a_1 $$
    通解可以写成
    $$x=x_0+k\times lcm(a1,a2)$$
    这样我们就将两个方程合并为了一个,也就是下式
    $$x≡x_0\pmod {lcm(a1,a2)}$$
    重复进行以上操作,我们最终能将n个方程全部合并,再用扩展欧几里德得解出来就好了。
    随便copy一份代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ll solve(){
ll M = a[1], R = r[1], x, y, d;
//M:lcm
//R:当前得到的特解x
for(int i = 2; i <= n; ++ i){
d = exgcd(M, a[i], x, y);
//Mx + a[i]y = gcd(M, a[i]);
if((R-r[i])%d != 0) return -1;
x = (R-r[i])/d * x % a[i];
//x0 = c'x
R -= x*M;
//回带
//注意理解这里的R,也就是特解,指的是上面的y1
M = M/d * a[i];
//更新lcm
R %= M;
//让它变得小一点便于计算(?)
}
return (R%M+M)%M;
}