01divisibility.tex

\chapter{数的整除性}
\begin{introduction}[本章内容提要]
	\item 欧几里得算法
	\item 拓展欧几里得算法
\end{introduction}

\section{最小公倍数}
两个数$a$与$b$(不全为零)的最大公因数是整除它们两个的最大数，记为$gcd(a,b)$。如果$gcd(a,b)=1$，我们称$a$与$b$互质。

求两个数最大公因数的最有效的方法是{\heiti 欧几里得算法}，其核心操作是辗转相除，先看一个例子。

\begin{example}
	欧几里得算法求$gcd(28,93)$的例子。
	
	第一步用93除以28得商为3,余数为7，记作下面式子：
	$$
		93 = 3*28 + 7
	$$
	第二步用上一步的除数作为新的被除数，上一步的余数作为新的除数，即：
	$$
		28 = 4*7 + 0
	$$
	发现此时余数为0，算法不再继续。欧几里得算法指出当得到余数0时，除数（上一步的余数）就是最初两个数的最大公因数。所以
	$gcd(28,93)$ = 7。
\end{example}

\begin{theorem}{欧几里得算法}{label}
	要计算两个整数$a$与$b$的GCD，先令$r_{-1}=a$且$r_{0}=b$，然后计算相继的商和余数：$r_{i-1}=q_{i+1}*r_{i}+r_{i+1} \quad (i=0,1,2,...)$，
	直到某余数$r_{n+1}=0$，最后的非零余数$r_{n}$就是$a$与$b$的最大公因数。
\end{theorem}

\begin{proof}
	考虑一般情形，有
	\begin{align*}
	r_{-1} &= q_1*r_0 + r_1 \\
	r_0 &= q_2*r_1 + r_2 \\
	r_1 &= q_3 * r_2 + r_3 \\
	r_2 &= q_4 * r_3 + r_4 \\
 	&\cdot \cdot \cdot\\
	r_{n-3} &= q_{n-1}*r_{n-2} + r_{n-1} \\
	r_{n-2} &= q_{n} * r_{n-1} + {\color{red} r_n} \\
	r_{n-1} &= q_{n+1} * r_n + 0 \\
	\end{align*}
	欧几里得算法说，最后的$r_n$就是gcd，那么我们先证明$r_n$一定是$a(r_{-1})$和$b(r_0)$的因子。
	
	由最后一行知，$r_n$整除$r_{n-1}$，于是由倒数第二行知$r_n$整除$r_{n-2}$，依次类推，$r_n$整除$r_{0}$和$r_{-1}$。
	
	下面再证明$r_n$是$a$与$b$的{\heiti 最大}公因数。假设$d$是$a$与$b$的任意公因数，则由上面式子第一行知$d$整除$r_1$，
	于是由第二行知$d$整除$r_2$，依次类推，$d$整除$r_n$，即$r_n$是最大的公因数。
	
	最后，还要说明一定存在$r_{n+1}$为0，易知，每一次余数都是严格递减的，所以余数最后总能到0。那自然会问，要多少步呢？
	实际上，{\heiti 欧几里得算法的步数至多是$b$的位数的7倍}。
\end{proof}


\lstinputlisting[language=C++, style=codestyle2]{code01/gcd.cpp}

说到GCD，往往还会提到最小公倍数(LCM)，有如下式子
\begin{align*}
lcm(a,b) * gcd(a,b) &=a*b \\
lcm(S/a, S/b) &= S/gcd(a, b)
\end{align*}

\begin{note}
另外一种计算两个数最大公约数的算法，叫做{\heiti Stein算法}。这种算法是针对欧几里得算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。
感兴趣的可以自行查阅。
\end{note}


\section{线性方程定理}

已知两个整数$a,b$，现在我们观察由$a$的倍数加上$b$的倍数得到的所有可能整数，也就是说{\heiti 考察$ax+by$得到的所有整数}，其中$x,y$可以是任何整数。

例如取$a=42$，$b=30$，随意列出一些$x,y$，会发现得到的数都可以被6整除。这其实很显然，因为42和30都能被6整除。更一般的，{\heiti 显然形如$ax+by$的每个数被$gcd(a,b)$整除}，因为$gcd(a,b)$整除a与b。

接着问题又来了，$ax+by=gcd(a,b)$是否一定有整数解呢？答案是肯定的。证明是利用{\heiti 拓展欧几里得算法}，不停的将余数用$a$和$b$表示，{\heiti 最后的$gcd(a,b)$一定可以用$a,b$表示}。也称欧几里得回代法。

\begin{example}
欧几里得回代法解$60x+22y=gcd(60,22)$

首先写出欧几里得算法计算$gcd(60,22)$的过程：
\begin{align*}
60=2 * 22+16 \\
22=1 * 16+6 \\
16=2 * 6+4 \\
6=1 * 4+2 \\
4=2 * 2+0
\end{align*}

这表明$gcd=2$。下面关键来了，我们想用$a,b$表示倒数第二行$6=1*4+2$的那个2，就从第一行表示$a,b$回代，如表\ref{tab:欧几里得回代法示例}：

\begin{table}[!htbp]
	\centering
	\caption{欧几里得回代法示例}
	\begin{tabular}{cccc}
		\toprule
		原式  && & 带入过程  \\
		\midrule
		$a=2*b+16$&&  & $16=a-2*b$ \\
		$b=1*16+6$&& & $6=b-1*16=-a+3b$ \\
		$16=2*6+4$&& &  $4=16-2*6=3a-8b$ \\
		$6=1*4+2$ && & $2=6-1*4=-4a+11b$ \\
		\bottomrule
	\end{tabular}%
	\label{tab:欧几里得回代法示例}
\end{table}%
	
于是得到$x=-4, \ y=11$。

\end{example}

{\heiti 这样一行行进行，将陆续得到形如最新余数=a的倍数+b的倍数的等式，最终得到非零余数gcd，就给出了方程的解。}

\begin{note}
$gcd(a,b)$是否是形如$ax+by$的最小正整数呢？是的。因为$gcd(a,b)<=min(a,b)$。
\end{note}

\vbox{}

既然一个线性方程$ax+by=gcd(a,b)$总有整数解$x,y$，下面的问题是{\heiti 如何表述线性方程的所有解}。

先考虑$gcd(a,b)=1$的情况(即$a,b$互质，其他情况可以转换为互质)，假设$x_1,y_1$是方程$ax+by=1$的一个解。
通过$x_1$加上b的倍数和$y_1$减去a的相同倍数，可得到其他解。即对于任何整数$k$,我们得到新解$(x_{1}+kb,y_{1}-ka)$。（带入即可验证）

\begin{proof}
	$(x_{1}+kb,y_{1}-ka)$可以给出方程的{\heiti 所有}解。
	
	假设$(x_{1},y_{1})$与$(x_{2},y_{2})$是方程$ax+by=1$的两个解，即$ax_{1}+by_{1}=1$ 且$ ax_{2}+by_{2}=1$ ，我们用$y_{2}$乘以第一个方程，用$y_{1}$乘以第二个方程，再相减消去b，整理后得到$ax_{1}y_{2}-ax_{2}y_{1}=y_{2}-y_{1}$。
	类似的，用$x_{2}$乘以第一个方程，用$x_{1}$乘以第二个方程，再相减便得到$bx_{2}y_{1}-bx_{1}y_{2}=x_{2}-x_{1}$。
	令$k=x_{2}y_{1}-x_{1}y_{2}$，则得到$x_{2}=x_{1}+kb \ ,\  y_{2}=y_{1}-ka$。得证。
\end{proof}

\vbox{}

再考虑$gcd(a,b)>1$的情况，为简便，令$g=gcd(a,b)$，由前面“欧几里得回代法”知方程$ax+by=g$至少有一个解$(x_{1},y_{1})$。
{\heiti 而$g$整除$a,b$}，故$(x_{1},y_{1})$是简单方程$\frac{a}{g}x+\frac{b}{g}y=1$的解。
于是由前面证明，通过式子$x_1+k*\frac{b}{g},\ y_1-k*\frac{a}{g}$改变$k$的值可得到其他解。这就完成了对方程$ax+by=g$解的描述，我们把它概括为下面定理。


\begin{theorem}{线性方程定理}{label}
设$a$与$b$是非零整数，$g=gcd(a,b)$。方程$ax+by=g$总是有一个整数解$(x_{1},y_{1})$（也称贝祖定理），
它可由前面叙述的欧几里得回带法得到。则方程的每一个解可由$(x_{1}+k*\frac{b}{g},y_{1}-k*\frac{a}{g})$得到，其中$k$可为任意整数。
\end{theorem}

\vbox{}

现在我们想怎么用代码实现上面说到的回代法。

如果用上面的思路，我们似乎需要事先知道欧几里得的结果，然后根据结果去算系数。
但是一般用计算机求解$gcd$，是递归算法，就是说我们需要逆推（上面过程的逆过程），这样才能写出递归代码。

假设当前我们要处理的是求出$a$ 和 $b$的最大公约数，并要求出 $x$ 和 $y$ 使得 $a * x + b * y=g$。
而我们已经求出了下一个状态：$b$ 和 $a\%b$ 的最大公约数({\heiti 欧几里得算法核心，$a=b,\ b=a\%b$})，并且求出了一组$x_1$ 和$y_1$ 使得：$ b * x_1 + (a\%b) * y_1 = g$。
那么这两个相邻的状态之间存在一种关系可以求解，我们知道$a\%b = a - (a/b)*b$，那么较末状态(先开始递归计算的)有：

\begin{align*}
b * x_1 + (a\%b) * y_1 &= g\\
b*x_{1} + (a-(a/b)*b) * y_{1} &= g \\
b*x_{1} + a*y_{1}-(a/b)*b*y_{1} &=g\\
a*y_{1} + b*(x_{1}-a/b*y_{1})&= g
\end{align*}
对比较先的状态（后递归到的，需要求的），需要求一组 x 和 y 使得：$a*x + b*y = g$ ，比较对应项系数得到
\begin{align*}
x &= y_1\\
y &= x_1 - a/b * y_1 \\
\end{align*}


这就是递归的关键，我们把它称为{\heiti 拓展欧几里得算法}。之所以叫拓展，是因为它相比欧几里得算法多了一小点，但能解决模线性方程、逆元、同余方程等许多经典问题（后面会介绍）。

递归的终止条件为$b=0$,这时候$x=1,\ y=0,\ a = gcd$。

\lstinputlisting[language=C++, style=codestyle2]{code01/exgcd.cpp}

\vbox{}

\vbox{}

\begin{problemset}
	\item 拓展欧几里得算法的时间复杂度是多少？
	\item \href{http://poj.org/problem?id=1061}{青蛙的约会 \quad POJ1061} 
	\item \href{https://ac.nowcoder.com/acm/contest/201/C}{Utawarerumono \quad ac.nowcoder.com/acm/contest/201/C}
	\item \href{https://codeforces.com/problemsets/acmsguru/problem/99999/140}{SGU140 \quad 多元线性同余方程} 
\end{problemset}