\gcd 是出现在数论而又披着同余的外衣的唯一的函数。

因为关于 \gcd 的东西实际上非常多非常杂，写一个博客记录一下。

而且数论里面基本上是个东西就离不开 \gcd 所以这也是个非常重要的东西。

---

1.基础计算

常用欧几里得算法计算，也就是我们经常用的 \gcd(a,b) = \gcd(b,a \bmod b)

证明（直接抄OI-Wiki的，只是为了不误人子弟，日常谁无聊证明这个啊）：

设 a=bk+c，显然有 c=a \bmod b。设 d \mid a,~d \mid b，则 c=a-bk, \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k。

由右边的式子可知 \frac{c}{d} 为整数，即 d \mid c 所以对于 a,b 的公约数，它也会是 a \bmod b 的公约数。

反过来也需要证明：

设 d \mid b,\mid (a \bmod b)，我们还是可以像之前一样得到以下式子 \frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}。

因为左边式子显然为整数，所以 \frac{a}{d} 也为整数，即 d \mid a，所以 b,a\bmod b 的公约数也是 a,b 的公约数。

既然两式公约数都是相同的，那么最大公约数也会相同。

所以得到式子 \gcd(a,b)=\gcd(b,a\bmod b)

Code

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

2.裴蜀定理

设 \gcd(a, b) = d，则对任意整数 x, y，有 d|(ax + by) 成立

特别地，一定存在 x, y 满足 ax + by = d

等价的表述：不定方程 ax + by = c (a,b,c \in \mathbb{Z})有解的充要条件为 (a, b)|c

推论：a, b 互质等价于 ax + by = 1 有解

证明

显然有 d | a,d | b

根据之前的引理有 d | ax,d | by

故 d | (ax+by)

对于第二个结论（

若任何一个等于 0 , 则 \gcd(a,b)=a . 这时定理显然成立。

若 a,b 不等于 0 .

由于 \gcd(a,b)=\gcd(a,-b) ,

不妨设 a,b 都大于 0 , a\geq b,\gcd(a,b)=d .

对 ax+by=d , 两边同时除以 d , 可得 a_1x+b_1y=1 , 其中 (a_1,b_1)=1 .

转证 a_1x+b_1y=1 .

我们先回顾一下辗转相除法是怎么做的，由 \gcd(a, b) \rightarrow \gcd(b,a\bmod b) \rightarrow ... 我们把模出来的数据叫做 r 于是，有

\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1

把辗转相除法中的运算展开，做成带余数的除法，得

\begin{aligned} a_1 &= q_1b+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n \end{aligned}

不妨令辗转相除法在除到互质的时候退出则 r_n=1 所以有（ q 被换成了 x ，为了符合最终形式）

r_{n-2}=x_nr_{n-1}+1

即

1=r_{n-2}-x_nr_{n-1}

由倒数第三个式子 r_{n-1}=r_{n-3}-x_{n-1}r_{n-2} 代入上式，得

1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}

然后用同样的办法用它上面的等式逐个地消去 r_{n-2},\cdots,r_1 ,

可证得 1=a_1x+b_1y . 这样等于是一般式中 d=1 的情况。

3.Exgcd

重头戏，也是写这篇博客的原因之一

由裴蜀定理可得，方程 ax + by = \gcd(a,b) 必有一组解。

所以我们考虑如何求出这样的方程的一组解。

证明：

设

\begin{aligned} &ax_1 + by_1 = \gcd(a,b) \\ &bx_2 + (a \bmod b)y_2 = \gcd(b,a \bmod b) \end{aligned}

则

\begin{aligned} &\because \gcd(a,b) = \gcd(b,a \bmod b)\\ &\therefore ax_1 + by_1 = bx_2 + (a \bmod b)y_2 \\ &\because (a \bmod b ) = a - (\lfloor \frac{a}{b} \rfloor \times b)\\ &\therefore ax_1 + by_1 = bx_2 + (a-\lfloor \frac{a}{b} \rfloor \times b) y_2 \\ \end{aligned}

展开得

\begin{aligned} &ax_1 + by_1 = ay_2 + bx_2 - \lfloor \frac{a}{b} \rfloor by_2 = &ay_2 + b(x_2 - \lfloor \frac{a}{b} \rfloor y_2)\\ &\because a = a,b = b \\ &\therefore x_1 = y_2 , y_1 = x_2 - \lfloor \frac{a}{b} \rfloor y_2 \end{aligned}

所以就可以递归求解了。

Code

ll exgcd(ll a,ll b,ll& x,ll& y) {
    ll ret,tmp;
    if (!b) {
        x = 1,y = 0;
        return a;
    }
    ret = exgcd(b,a%b,x,y);
    tmp = x,x = y,y = tmp -a/b * y;
    return ret; 
}

拓展

考虑形如 ax + by = c (a,b,c \in \mathbb{Z}) 的方程的所有解

首先由裴蜀定理得，不定方程 ax + by = c (a,b,c \in \mathbb{Z})有解的充要条件为 (a, b)|c 。

先考虑求一组特殊解的情况：首先将 a,b,c 都除以 \gcd(a,b) 得 a_0x + b_0y = c_0

此时 \gcd(a_0,b_0) = 1,所以我们可以求出 a_0x + b_0y = 1 的一组解 x_0,y_0 ，则原方程的一组特解为

x_1 = \frac{x_0c}{\gcd(a,b)},y_1 = \frac{y_0c}{\gcd (a,b)}

然后我们考虑构造所有解的形式：

设有 d (d \in \mathbb{Q}) 那么必有 a(x_1 + db) + b(y_1 - da) = c

同时，这组解需要保证 db,da \in \mathbb{Z}

令当 d 取到最小可能的正值的 d_x = db,d_y = da ,那么任意解中这两个变量与 x_1,x_2 的偏差一定分别是 d_x,d_y 的倍数。

显然，最小的时候 d_x = \frac{b}{\gcd (a,b)},d_y = \frac{-a}{\gcd (a,b)}

所有解就是 x = x_0 + kd_x,y = y_0 + kd_y (k \in \mathbb{Z})

例题：P5656 【模板】二元一次不定方程 (exgcd)

---

4.\varphi(n)

欧拉函数 \varphi(n)，表示 1 \sim n-1 里和 n 互质的数的个数。

性质

它有以下重要性质：

性质1：当 x \perp y 时， \varphi(xy) = \varphi(x) \varphi(y)

证明：对于每个 z \nmid xy，必有 z = ab，其中 a\nmid x,b\nmid y。所以就比较显然了。

性质2：当 p 为素数，\varphi(p^k) = p^k - p^{k-1}

证明：考虑每个 x | p^k 有 x = ap。这样的 a 在 1 \sim p^k - 1 里面有 p^{k-1} - 1 个，所以易得。

性质3：