そういえば去年末に勉強してたのを復習する. ここでは数としてはすべて整数を扱う.
2つの数 \(n,a\) について, \[\exists q, n = qa\] とあるとき, これを \[a \divisor n\] と書いて, \(a\) は \(n\) の 約数 であるだとか, \(n\) は \(a\) の 倍数 であるだとか, \(a\) は \(n\) を 割り切る だとかいう.
\(a \mid n\) という記法が一般的であるが, 視認性が最悪な上に, 対称でもなんでもない関係を左右対称な記号で書くのはナンセンスなので使わないことにする.
例えば,
特に,
この関係 \(\divisor\) には次のような性質がある. 簡単に確認できるので証明はしない.
2つの数 \(n,a\) があるとき, 次を満たす \(q,r\) が 唯一 存在する: \[\exists! q, \exists!r ,~~ 0 \leq r < a ~ \land ~ n = qa + r\]
\(n,a\) から上の形式を導く操作を 除算 という（\(n\) を \(a\) で除算する）. この \(q\) のことを 商, \(r\) のことを 剰余 という. この剰余 \(r\) のことを \(n\%a\) と書く.
この基本原理は定理として証明できるが省略.
2つの数 \(a,b\) に対して \[c \divisor a \land c \divisor b\] とあるとき, この \(c\) を \(a,b\) の 公約数 という. 最大の公約数を \[\gcd(a,b)\] と書いて表す. ただし例外的に \[\gcd(0,0)=0\] だと定める. これ以外の値のときは性質 (d4) があるので gcd は一意に定まる.
gcd の定義は簡単に一般化できて, 数 \(z_1, \ldots, z_N\) に対して \(\gcd(z_1, \ldots, z_N)\) が定まる. ただし \(\gcd(0, \ldots, 0)=0\) であるとする.
\(\gcd(z_1, \ldots, z_N) = 1\) のとき, \(z_1, \ldots, z_N\) は 互いに素 であるという.
整数全体の集合を \(\Z\) と書く. \[\Z = \{0,\pm1, \pm2, \ldots\}\] この要素をそれぞれ \(\alpha\) 倍したものを \(\alpha \Z\) と書く. \[\alpha \Z = \{ 0, \pm \alpha, \pm 2\alpha, \ldots \}\]
特に \(0\Z = \{0\}\).
それぞれからの要素を足したものを \(\alpha \Z + \beta \Z\) と書く. \[\alpha \Z + \beta \Z = \{ \alpha z_1 + \beta z_2 \mid \alpha z_1 \in \alpha \Z, \beta z_2 \in \beta \Z\}\] 一般に, \(\alpha_1, \ldots, \alpha_N\) に対して, \[\alpha_1 \Z + \cdots + \alpha_N \Z\] が定まる.
\(a,b\) について, \[a \Z + b \Z = \gcd(a,b) \Z\] が成り立つ.
\((a,b)=(0,0)\) の場合は自明（両辺とも \(\{0\}\)）. \((a,b) \ne (0,0)\) の場合を証明する.
まずは何かしらの \(g\) によって, \(a \Z + b \Z = g \Z\) と表されることを見て, そして \(g=\gcd(a,b)\) であることを最後に確認する.
\(I = a\Z + b\Z\) とおく. この正の部分 \(I^+ = \{ z \in I \mid z > 0 \}\) を考えるとこれは非空である. なぜなら \(|a|\) や \(|b|\) が自明に含まれるので. そこで \[g = \min I^+\] を持ってくる. では任意に \(c \in I\) を取ってきたときにこれを \(g\) で除算してみる（除算の基本原理）. \[c = qg + r ~~~(0 \leq r < g)\] さて \(c, g \in I\) より \(r \in I\) でもある. \(g\) が \(I^+\) の最小元であることために \(r=0\) でないといけない. すなわち \[\forall c \in I ,~~ g \divisor c\] が得られる. というわけで \(I = g \Z\) である.
さて \(a,b \in I\) なので \(g \divisor a \land g \divisor b\) である. すなわち \(g\) は \(a,b\) の公約数である. 逆に \(a,b\) の公約数として任意に \(d\) を持ってきたとき,
\[\begin{align*} d \divisor a \land d \divisor b & \implies d \divisor xa+yb & (\forall x,y) \\ & \implies d \divisor g & (\exists x,y,~ g=xa+yb) \\ & \implies |d| \leq g \\ \end{align*}\]
\(g\) は公約数でしかも, 公約数はすべて \(g\) 以下であることが示された. これは \(g = \gcd(a,b)\) にほかならない.
以上で定理が示された.
この定理は次のようにも言い換える事ができる.
定数 \(a,b,n\) と変数 \(x,y\) の方程式 \[ax + by = n\] は, \(\gcd(a,b) \divisor n\) のときに限って解を持つ.
定数 \(a,b\) と変数 \(x,y\) の方程式 \[ax + by = \gcd(a,b)\] は必ず解を持つ.
1 は gcd の定義より明らか. 2 について見る. \(a\) を \(|b|\) で除算する. \[a = q |b| + r\]
そこで
とおくと, \(g_1 \divisor |b|\), \(g_1 \divisor r\) なので, \(g_1 \divisor g_2\). 同様に \(g_2 \divisor g_1\) も導ける. これらから \(g_1 = g_2\).
上の定理はそのまま, \(a,b\) から \(\gcd(a,b)\) を求めるアルゴリズムを提示する.
ループにおいて \(|b|\) に注目するとこれが狭義単調減少していることから停止性が保証される.
ユークリッドアルゴリズムの \(a,b\) に対して,
とする. \(r_{k+1}=0\) のとき \(r_k=\gcd(a,b)\) であるというのがユークリッドアルゴリズムであった.
さて \(r_{k-1}\) を \(r_k\) で除算する際の商を \(q_k\) とする. \[r_{k-1} = q_k r_k + r_{k+1}\]
更に
を定める. 次が成り立つ.
\[r_k = (-1)^k x_k a + (-1)^{k+1} y_k b\]
\(k=0,1\) については自明. \(k>1\) は数学的帰納法から導かれる.
特に \(r_{k+1}=0\) になったとき,
を得る.
この定理は \(ax+by = \gcd(a,b)\) の解 \(x,y\) を得るための具体的なアルゴリズムをそのまま提示している.
正の数 \(m\) について, \[a - b \in m \Z\] とあることを, \(m\) を法にする合同関係といって \[a \equiv b \pmod m\] と書く. \(a \equiv b \pmod m \iff \exists k, a = b + km\) である.
互いに素な正の数 \(m_1, \ldots, m_K\) と数 \(a_1, \ldots, a_K\) に関する次のような連立方程式
を \(x\) に関して解きたい.
とおく. \((m_i)\) が互いに素なことから \(\gcd(m_i, M_i)=1\). 定理から \(\exists x_i, y_i\) で, \[x_i m_i + y_i M_i = 1\] これは \(m_i\) を法にすることで \[\exists y_i ,~~ y_i M_i \equiv 1 \pmod{m_i}\] と言い直せる.
そこで \[x = \left( \sum_i a_i y_i M_i \right) \% m\] とするとこれが解になる.
\(m_j \divisor m, m_j \divisor M_i (i \ne j), m_j \not\divisor M_j\) に注意すると,
\[\begin{align*} x \% m_j & = (a_j y_j M_j) \% m_j \\ & = (a_j 1) \% m_j \\ & = a_j \end{align*}\]
となって確かに連立方程式を満たしている.