最大公約数

　２つの整数 $a$, $b$ の最大公約数を $\gcd(a, b)$ と表します。 $\gcd$ は Greatest Common Divisor の頭文字です。 普通は $a$ も $b$ も自然数で考えることが多いですが、 $a$, $b$ の符号に関わらず $\gcd(a, b)$ は 0 または正に取ります。 片方が 0 なら $$ \gcd(a, 0) = |a| $$ と約束します。例えば $$ \gcd(－12, －30) = 6, \quad \gcd(5, 0) = \gcd(－5, 0) = 5 $$ 　0 は任意の整数の倍数 ( 0倍！) ですので、任意の整数は 0 の約数であり、$a$ の約数で最大のもの $|a|$ が $\gcd(a, 0)$ という理屈です。
　ただしそう考えると $\gcd(0, 0)$ は任意の整数ということになってしまいますので、これだけは $$ \gcd(0, 0) = 0 $$ と約束します。

$a x + b y$ の形の数

　２つの整数 $a$, $b$ を固定したとき、$a x + b y$ ( $x$, $y$ は整数 ) の形に書ける整数全体の集合 $G$ を考えましょう： $$ G = \{ a x + b y \, | \, x, y \mbox{ は整数 }\} $$ $G$ は、全ての整数の集合 $\ZZ$ の、加法群としての部分群になりますので、ある非負整数 $d$ を用いて $$ G = \{ d z \, |\, z \mbox{ は整数 }\} $$ と書き直せることが分かります。$d$ を $G$ の生成元と呼びます。

　最大公約数や最小公倍数の性質を使うと、実はこの $d$ は $\gcd(a, b)$ に他ならないことが示せます。 （ $\gcd(0, 0) = 0$ という約束事も、丁度この事実に当てはまります。) ということは、任意の整数 $a$, $b$ に対して $$ \gcd(a, b) = a x + b y \mbox{ を満たす整数 } x, y \mbox{ が存在する} $$ ということが分かります。

てんびんクイズ

　充分大きな天秤と、$a$ グラムと $b$ グラムの分銅が充分たくさんあるとします。 これらを用いて測ることのできる最小の重さは何グラムでしょうか。

　答えは $\gcd(a, b)$ グラムです。

　$\gcd(a, b) = a x + b y$ を満たす整数 $x$, $y$ が存在することを先程述べましたが、$x$, $y$ の一方は正、他方は負であり、 $a$ グラムの分銅 $|x|$ 個を左の皿に、$b$ グラムの分銅 $|y|$ 個を右の皿に乗せれば、 その差として $\gcd(a, b)$ グラムを測ることができます。

$a = 3, b = 5$	のとき	$3 \times 2 + 5 \times (-1) = 1$	⇒	$3g \times 2個 = 5g \times 1個 + 1g$
$a = 6, b = 10$	のとき	$6 \times 2 + 10 \times (-1) = 2$	⇒	$6g \times 2個 = 10g \times 1個 + 2g$
$a = 5, b = 7$	のとき	$5 \times 3 + 7 \times (-2) = 1$	⇒	$5g \times 3個 = 7g \times 2個 + 1g$
$a = 7, b = 11$	のとき	$7 \times (-3) + 11 \times 2 = 1$	⇒	$7g \times 3個 + 1g = 11g \times 2個$

拡張ユークリッドアルゴリズム

　上述の $x$, $y$ は、整数論では「$\ZZ$ 上での変換」に欠かせないものですし、 暗号理論においても、例えば RSA 暗号の復号鍵を計算するときに必要になります。 単に存在が証明されているだけでは役に立ちません。 構成的証明(アルゴリズム)を与えましょう。Python で書けばこんな感じです：

# Extended Euclidean algorithm
# returned value = [d, x, y]
#   where  d = gcd(a, b) = a + x + b * y
def euclid(a, b):
    if b == 0:
        if a >= 0:
            return [a, 1, 0]
        else:
            return [-a, -1, 0]
    else:
        r0, x0, y0 = a, 1, 0
        r1, x1, y1 = b, 0, 1
        while r1 != 0:
            q = r0 // r1
            r2 = r0 - q * r1
            x2 = x0 - q * x1
            y2 = y0 - q * y1
            r0, x0, y0 = r1, x1, y1
            r1, x1, y1 = r2, x2, y2
        if r0 < 0:
            r0, x0, y0 = -r0, -x0, -y0
        return [r0, x0, y0]

　$r_0$, $r_1$, $r_2$ は所謂「ユークリッドの互除法」で計算する剰余列です。 メモリ節約のため変数を使い回ししています。 $x_0$, $y_0$, $x_1$, $y_1$, $x_2$, $y_2$ との間には常に $$ r_0 = a \times x_0 + b \times y_0, \ r_1 = a \times x_1 + b \times y_1, \ r_2 = a \times x_2 + b \times y_2 $$ が成り立っており、アルゴリズム終了時には $r_0 = \gcd(a, b)$ となるので $$ \gcd(a, b) = a \times x_0 + b \times y_0 $$ となる、という仕組みです。

モジュラー群 $SL_2(\ZZ)$

　整数係数で行列式が 1 の2次行列たちが成す乗法群をモジュラー群と呼びます。 保型形式の整数論を勉強するときに最初に出て来る群です。 $$ SL_2(\ZZ)= \left\{\left(\left. \begin{array}{cc} a & b \\ c & d \\ \end{array} \right) \,\right|\, a, b, c, d \in \ZZ,\, ad-bc = 1 \right\} $$ $SL_2(\ZZ)$ を複素上半平面 $H = \{ \tau \in C \, | \, \mbox{Im}(\tau) > 0 \}$ に作用させるとき、 その商空間のコンパクト化 $(\Gamma \backslash H)^{\ast}$ はリーマン球であり、 $(\Gamma \backslash H)^{\ast}$ の関数体（ = $SL_2(\ZZ)$ に関する保型関数の成す体 ) は $j$-関数で生成され、 その $j$-関数は楕円曲線の $j$-不変量を与えるもので ... と話が広がってゆきます。

$SL_2(\ZZ)$ の生成元

　$SL_2(\ZZ)$ の2つの元 $$ T=\mat{rr}{0 & -1 \\ 1 & 0}, \quad S=\mat{rr}{1 & 1 \\ 0 & 1} $$ は $$ T^2=\mat{rr}{-1 & 0 \\ 0 & -1}, \quad S^{-1}=\mat{rr}{1 & -1 \\ 0 & 1}, \quad (S^{-1}T)^3 = I =\mat{rr}{1 & 0 \\ 0 & 1} $$ のような関係式を満たしますが、この2つの元が $SL_2(\ZZ)$ を生成することが、 ユークリッドのアルゴリズムを用いて構成的に証明できます。 $$ A = \mat{cc}{ a & b \\ c & d} $$ を $SL_2(\ZZ)$ の元とします。 $a d－b c = 1$ が成り立つためには $\gcd(a, c) = 1$ でなければならないことを覚えておいてください。 $a$ を $c$ で割った商を $q$, 余りを $r$, すなわち $a = q c + r$ とすると、 $$ S^{-q} A = \mat{cc}{ a - q c & b - q d \\ c & d} = \mat{cc}{ r & b - q d \\ c & d} $$ $$ T S^{-q} A = \mat{cc}{ -c & -d \\ r & b - q d} $$ となります。 $A$ の左から $S$, $S^{-1}$, $T$ をいくつか掛けることによって第1列成分が $a$, $c$ から $-c$, $r$ に変化しました。 ユークリッドのアルゴリズムを $r_0 = a$, $r_1 = c$ で開始したときの $r_2$ が $r$ ですから、 $\pm$ がずれますが、第1列成分は $r_0$, $r_1$ が $-r_1$, $r_2$ へ変化したことになります。 この操作を続ければ最終的に (2,1)-成分 ( $r$ の部分 ) は 0、 (1,1)-成分の絶対値は $\gcd(a, c) = 1$ になり、 $S$ のべき乗と高々 $\pm$ だけ違う行列に変形できます。

　例をひとつ挙げておきましょう： \begin{eqnarray*} && A = \mat{rr}{ 35 & 27 \\ 22 & 17} \\ && T S^{-1} A = \mat{rr}{ -22 & -17 \\ 13 & 10} \\ && T S^2 T S^{-1} A = \mat{rr}{ -13 & -10 \\ 4 & 3} \\ && T S^4 T S^2 T S^{-1} A = \mat{rr}{ -4 & -3 \\ 3 & 2} \\ && T S^2 T S^4 T S^2 T S^{-1} A = \mat{rr}{ -3 & -2 \\ 2 & 1} \\ && T S^2 T S^2 T S^4 T S^2 T S^{-1} A = \mat{rr}{ -2 & -1 \\ 1 & 0} \\ && T S^2 T S^2 T S^2 T S^4 T S^2 T S^{-1} A = \mat{rr}{ -1 & 0 \\ 0 & -1} \\ && T^2 T S^2 T S^2 T S^2 T S^4 T S^2 T S^{-1} A = \mat{rr}{ 1 & 0 \\ 0 & 1} \\ \end{eqnarray*} 従って \begin{eqnarray*} A &=& (T^3 S^2 T S^2 T S^2 T S^4 T S^2 T S^{-1})^{-1} \\ &=&S T S^{-2} T S^{-4} T S^{-2} T S^{-2} T S^{-2} T^3 \end{eqnarray*} 　この変形は次の Python プログラムで得られます：

#-*- coding: utf-8 -*-
# SL2Z.py

import random

# Euclidean algorithm
# returned value = [d, x, y]
#   with d = gcd(a, b) = a + x + b * y
def euclid(a, b):
    if b == 0:
        if a >= 0:
            return [a, 1, 0]
        else:
            return [-a, -1, 0]
    else:
        r0, x0, y0 = a, 1, 0
        r1, x1, y1 = b, 0, 1
        while r1 != 0:
            q = r0 // r1
            r2 = r0 - q * r1
            x2 = x0 - q * x1
            y2 = y0 - q * y1
            r0, x0, y0 = r1, x1, y1
            r1, x1, y1 = r2, x2, y2
        if r0 < 0:
            r0, x0, y0 = -r0, -x0, -y0
        return [r0, x0, y0]

# multiplication of (2,2)-matrices
def matmul(a, b):
    c00 = a[0][0] * b[0][0] + a[0][1] * b[1][0]
    c01 = a[0][0] * b[0][1] + a[0][1] * b[1][1]
    c10 = a[1][0] * b[0][0] + a[1][1] * b[1][0]
    c11 = a[1][0] * b[0][1] + a[1][1] * b[1][1]
    return [[c00, c01], [c10, c11]]

# display (2,2)-matrix
def matprint(a):
    print("%2d %2d" % (a[0][0], a[0][1]))
    print("%2d %2d" % (a[1][0], a[1][1]))
    print()

# random integer in [m, n]
def r(m = 0, n = 64):
    return random.randint(m, n)

s = [[1,  1], [0, 1]]
t = [[0, -1], [1, 0]]

# initialization
while 1:
    r0 = r()
    r1 = r()
    d, x, y = euclid(r0, r1)
    if d == 1:
        break
z = r(-5, 5)    
a = [[r0, -y + r0 * z], [r1, x + r1 * z]]
#a = [[35, 27], [22, 17]] # test data
w = "A :" # transformation
v = ""    # expression
u = 0      
op = []   # operations

print(w)
matprint(a)

while a[1][0] != 0:
    q = a[0][0] / a[1][0]
    sq = [[1, -q], [0, 1]] # (-q)-th power of S
    a = matmul(t, matmul(sq, a))
    w = ("T S^(%d) " % (-q)) + w
    v = v + (" S^(%d) T" % q)
    u = 1 - u
    op = op + [[[1, q], [0, 1]], t]
    print(w)
    matprint(a)

if a[0][0] == -1:
    a = [[-a[0][0], -a[0][1]], [-a[1][0], -a[1][1]]]
    w = "T^2 " + w
    if u == 0:
        v = v + " T^2"
        op = op + [t, t]
    print(w)
    matprint(a)

if a[0][1] != 0:
    q = a[0][1]
    sq = [[1, -q], [0, 1]]
    a = matmul(sq, a)
    w = ("S^(%d) " % (-q)) + w
    v = v + (" S^(%d)" % q)
    op.append([[1, q], [0, 1]])
    print(w)
    matprint(a)

print("A =", v)
print()

b = [[1, 0], [0, 1]]
for c in op:
    b = matmul(b, c)    
print("Check: ")
matprint(b)