gcd(未完成版)
\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.
由右边的式子可知 \fr