ここでは最大公約数を数列の総和にて表示する。ただしこの表示によって、計算量の減少や、なにかふかーい事実が得られるというわけではない。ただ、この和表示によってなにかしらの一つの新しい解釈が得られることは保証されよう(もしも既に知っていることだったら・・・う~ん残念!)。
ここでは級数表示のために使うあるアイディアを紹介する。おそらく多くの人が最大公約数と結びつけたことのない話題であろう。
格子点同士を結ぶ直線を考える(面倒くさいからExcelで撮影)。
直線が通る正方形の数を考えるときに、直線がいくつの格子点を通るかが重要となる。$(x_1, y_1)$と$(x_2,y_2)$を結ぶ直線の通る(始点終点を除く)格子点の個数$n$は、明らかに次の式で与えられる。
$$
n=\gcd{(|x_1-x_2|,|y_1-y_2|)}-1
$$
ただし直線は垂直や水平でないものとする。
ここで直線と、格子の線の交点に注目する
このように見てみると、あることが分かってくる。赤い丸である交点は、直線が通る隣り合う正方形と正方形の間に位置しているのだ。したがって、植木算より
「交点の個数$=$正方形の数 $-1$」
と分かる。じゃあ交点の個数は?これは直線の始点と終点の間にある、縦線と横線の個数に関係がある。小さい赤い丸の点では線と一回交わっている。一方で大きな赤い丸の点は格子点なので、縦線と横線両方に交わっている。だから
「交点の個数$=$縦線の数$+$横線の数$-$通る格子点の数」
となる。ここで$a=|x_1-x_2|,b=|y_1-y_2|$とすると、交点の個数は
$$
(a-1)+(b-1)-(\gcd{(a,b)}-1)=a+b-\gcd{(a,b)}-1.
$$
となる。すると正方形の数は
$$
(a+b-\gcd{(a,b)}-1) + 1 = a+b-\gcd{(a,b)}
$$
と表される。
図の例では$a=21, b=15$より、
$$
21+15-\gcd{(21,15)}=21+15-3=33
$$
より、$33$つ通っているとわかる。
ちなみにこの式を$\gcd{(a,b)}$で割るともう一つの導出方法も見えてくるが…これは各自に任せる。
正方形の個数は求まった。でも考えてみてほしい。直線の通る正方形(図の黄色い部分)の個数を、一列ごとに足していけばいいのではないだろうか。
道具の解説も終わったので、ついに和表示の導出である。とはいっても、直線の通る正方形の個数の表示式
$$
\begin{eqnarray}
&&a+b-\gcd{(a,b)} \\
&&ab-2\sum_{k=1}^{a-1} \left \lfloor
\frac{bk}{a}
\right \rfloor \\
&&\sum_{k=0}^{a-1} \left(
\left \lceil
\frac{b(k+1)}{a}
\right \rceil
-\left \lfloor
\frac{bk}{a}
\right \rfloor
\right)
\end{eqnarray}
$$
を使うとばすぐ導出できる:
$$
\begin{eqnarray}
\gcd{(a,b)}
&=&
a + b + 2 \sum_{k=1}^{a-1} \left \lfloor
\frac{bk}{a}
\right \rfloor
-ab \\
&=& a + b - \sum_{k=0}^{a-1} \left(
\left \lceil
\frac{b(k+1)}{a}
\right \rceil
-\left \lfloor
\frac{bk}{a}
\right \rfloor
\right)
\ \cdots (*)
\end{eqnarray}
$$
$(*)$を証明してみよう(これは正方形の個数の導出が帰納的で直感的、すなわち厳密性を欠いたものであったためだ)。まずは一行目の式を変形する:
$$
\begin{eqnarray}
a + b + 2 \sum_{k=1}^{a-1} \left \lfloor
\frac{bk}{a}
\right \rfloor
-ab
&=&
a + b + \sum_{k=1}^{a-1}
\left(
\left \lfloor
\frac{bk}{a}
\right \rfloor
+
\left \lfloor
\frac{b(a-k)}{a}
\right \rfloor
\right)
-ab \\
&=&
a + b + \sum_{k=1}^{a-1}
\left(
\left \lfloor
\frac{bk}{a}
\right \rfloor
+
\left \lfloor
\frac{-bk}{a}
\right \rfloor
+b
\right)
-ab \\
&=&
a + b + \sum_{k=1}^{a-1}
\left(
\left \lfloor
\frac{bk}{a}
\right \rfloor
-
\left \lceil
\frac{bk}{a}
\right \rceil
\right)+(a-1)b
-ab \\
&=&
a - \sum_{k=1}^{a-1}
\left(
\left \lceil
\frac{bk}{a}
\right \rceil
-
\left \lfloor
\frac{bk}{a}
\right \rfloor
\right)
\end{eqnarray}
$$
これは$(*)$の二行目の式
$$
\begin{eqnarray}
a + b - \sum_{k=0}^{a-1} \left(
\left \lceil
\frac{b(k+1)}{a}
\right \rceil
-\left \lfloor
\frac{bk}{a}
\right \rfloor
\right)
&=&
a + b - \left(
\sum_{k=1}^{a-1} \left(
\left \lceil
\frac{bk}{a}
\right \rceil
-\left \lfloor
\frac{bk}{a}
\right \rfloor
\right)
+b
\right)
\\
&=&a - \sum_{k=1}^{a-1} \left(
\left \lceil
\frac{bk}{a}
\right \rceil
-\left \lfloor
\frac{bk}{a}
\right \rfloor
\right)
\end{eqnarray}
$$
と一致している。また、この式に
$$
\begin{eqnarray}
\left \lceil
\frac{bk}{a}
\right \rceil
-\left \lfloor
\frac{bk}{a}
\right \rfloor
=
\left\{
\begin{array}{l}
1 \, (bk \equiv 0 \, ( \mathrm{mod}\, a)) \\
0 \, (\mathrm{otherwise})
\end{array}
\right.
\end{eqnarray}
$$
を適用することで
$$
\begin{eqnarray}
a - \sum_{k=1}^{a-1} \left(
\left \lceil
\frac{bk}{a}
\right \rceil
-\left \lfloor
\frac{bk}{a}
\right \rfloor
\right)
&=&
a- \{ ( a-1 ) - ( \gcd{(a,b)} - 1 ) \}\\
&=&
\gcd{(a,b)}
\end{eqnarray}
$$
と証明ができる。
先ほどの和表示は次の関係式を用いることで、一応拡張することができる
$$
\gcd{(a,b,c)} = \gcd{(\gcd{(a,b)},c)}
$$
でもこれだと式がめっちゃ汚くなる。そこで先ほどのアイディアが使えないかと考えてみる。
$2$つの数では$2$次元の格子を使用したのだから、$3$つの数では$3$次元の格子を用いてみる。通る立方体の数は、交点個数$+1$より、次のように求められる。
$$
(a+b+c-\gcd{(a,b)}-\gcd{(b,c)}-\gcd{(c,a)}+\gcd{(a,b,c)})+1
$$
しかし問題は、どうしても立方体の個数を和表示できないのだ。おそらくはこの方針では解決不能であり、新しいアイディアが必要である。もしくは、和表示は$2$つの最大公約数に限った表示という考え方もできるかもしれない。