魔方陣と37

偶然見つけた魔方陣についての事実について考えてみたことのメモです。
事実を知った情報源はこちら：
https://www.hibari.jp/weblog00/archives/2009/07/post_139.html

３×３の魔方陣は実質的に一つしかなくて、回転や反転によって８通りの異なる表し方があります。列挙してみると次の通りです。

$$
\begin{bmatrix}
2 & 9 & 4 \\ 7 & 5 & 3 \\ 6 & 1 & 8
\end{bmatrix},\quad
\begin{bmatrix}
4 & 3 & 8 \\ 9 & 5 & 1 \\ 2 & 7 & 6
\end{bmatrix},\quad
\begin{bmatrix}
8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2
\end{bmatrix},\quad
\begin{bmatrix}
6 & 7 & 2 \\ 1 & 5 & 9 \\ 8 & 3 & 4
\end{bmatrix},
$$

$$
\begin{bmatrix}
2 & 7 & 6 \\ 9 & 5 & 1 \\ 4 & 3 & 8
\end{bmatrix},\quad
\begin{bmatrix}
4 & 9 & 2 \\ 3 & 5 & 7 \\ 8 & 1 & 6
\end{bmatrix},\quad
\begin{bmatrix}
8 & 3 & 4 \\ 1 & 5 & 9 \\ 6 & 7 & 2
\end{bmatrix},\quad
\begin{bmatrix}
6 & 1 & 8 \\ 7 & 5 & 3 \\ 2 & 9 & 4
\end{bmatrix}
$$

上のリンク先の記事に書いてあることは、(1) 魔方陣に書き込まれた９個の数を左上から右下に向けて順番に並べて出来る９桁の数は必ず37の倍数になり、(2) それらの数で各桁の数字を巡回的に並べ替えてできる９桁の数もすべて37の倍数になる、という事実です。実際、魔方陣の８通りの表し方のそれぞれから得られる９桁の数を37で割ってみると、確かに割り切れます。たとえば SageMath で

MS = [294753618, 276951438, 438951276, 492357816, 618753294, 672159834, 816357492, 834159672]
[i / 37 for i in MS]

というコードを実行してみると、結果は

[7966314, 7485174, 11863548, 13306968, 16723062, 18166482, 22063716, 22544856]

となって、確かにどれも37で割り切れていることが分かります。これで (1) が確かめられました。後で書きますが、これは（準）魔方陣ならではの性質です。

一方で (2) については、次の一般的な事実の特別な場合なので、魔方陣に特有の性質というわけではないです（37 は $${10^9-1}$$ の約数です）。

［主張］$${d}$$ を $${10^m-1}$$ の約数として $${N}$$ を $${d}$$ で割り切れる$${m}$$桁の数とすれば、$${N}$$ を巡回的に並べ替えて出来る数も $${d}$$ で割り切れる。

【証明】$${N}$$ の一の位を先頭に移動させて出来る数を $${N'}$$ とすれば $${N' = 10^{m-1}\times N - (10^m-1)\times\lfloor{N/10}\rfloor}$$ であることが分かる。仮定より $${N}$$ と $${10^m-1}$$ は $${d}$$ で割り切れるので、$${N'}$$ も $${d}$$ で割り切れる。（証明終わり）

１から９を一度ずつ全て使って出来る９桁の数のうちで 37 の倍数になるものは魔方陣由来の数意外にもたくさんあります。たとえば  472158369 は 37 の倍数です（$${472158369 = 37 \times 12761037}$$）。そしてこれを 947215836 や 694721583 のように巡回的に数字を並べ替えて出来る９桁の数もやはり37の倍数です。だから、(2) の性質は、１から９を一度ずつ全て使って出来る９桁の数に限定しても「ありふれている」という感じだけれども、(1) の性質はそうではありません。たとえば上で挙げた 472158369 について、それをいったん３×３の方陣に書き込んだ上で「転置をとって」から９桁の数に読み戻すという操作をすると 413756289 になりますが、これは 37 の倍数ではありません。

$$
472158369
\to
\begin{bmatrix} 4 & 7 & 2 \\ 1 & 5 & 8 \\ 3 & 6 & 9\end{bmatrix}
\xrightarrow{\text{転置}}
\begin{bmatrix} 4 & 1 & 3 \\ 7 & 5 & 6 \\ 2 & 8 & 9\end{bmatrix}
\to
413756289
$$

では、１から９を一度ずつ全て使って出来る9桁の数のうちで (1) を満たすものはどれぐらいあるでしょうか？ちょっと考えてみます。

$${a_1, a_2, \dots, a_9}$$ を $${1, 2, \dots, 9}$$ の順列として

$$
\begin{bmatrix}
a_1 & a_2 & a_3 \\
a_4 & a_5 & a_6 \\
a_7 & a_8 & a_9
\end{bmatrix}
$$

と方陣の中に並べます。この方陣が (1) を満たすと仮定します。まず、ここから作られる９桁の数を $${N}$$ とすれば

$$
N = a_1 \cdot 10^8 + a_2 \cdot 10^7 + a_3 \cdot 10^6 \\
\qquad \qquad {} + a_4 \cdot 10^5 + a_5 \cdot 10^4 + a_6 \cdot 10^3 \\
\qquad \qquad \qquad \qquad {} + a_7 \cdot 10^2 + a_8 \cdot 10^1 + a_9 \cdot 10^0
$$

です。記号を簡単にするために

$$
\alpha = a_1 + a_4 + a_7, \quad
\beta = a_2 + a_5 + a_8, \quad
\gamma = a_3 + a_6 + a_6
$$

とおいておきます。仮定から $${N \equiv 0 \pmod{37}}$$ ですが、$${10^2 \equiv 26 \pmod{37}}$$ および $${10^3 \equiv 1 \pmod{37}}$$ であることから（つまり 37 は $${10^3-1}$$ の約数）

$$
26 \alpha + 10 \beta + \gamma \equiv 0 \pmod{37}
$$

という関係式が得られます。最初の方陣を180度回転させた

$$
\begin{bmatrix}
a_9 & a_8 & a_7 \\
a_6 & a_5 & a_4 \\
a_3 & a_2 & a_1
\end{bmatrix}
$$

に対して同じことを実行すれば

$$
26\gamma + 10 \beta + \alpha \equiv 0 \pmod{37}
$$

という別の関係式が得られます。これら２つの関係式から

$$
26\alpha + \gamma \equiv 26\gamma + \alpha \pmod{37}
$$

つまり

$$
25(\alpha-\gamma) \equiv 0 \pmod{37}
$$

が得られますが、25 と 37 は互いに素であることから

$$
\alpha - \gamma \equiv 0 \pmod{37}
$$

となります。ところが仮定から $${a_i}$$ たちは１から９のいずれかなので一般に $${1+2+3 \le a_i+a_j+a_k \le 7+8+9}$$ のはずですから、$${-18 \le \alpha-\gamma\le 18}$$ ということになります。よって上の合同式が成り立つのは $${\alpha=\gamma}$$ のときのみです。そうすると一つ目の合同式から

$$
27\alpha + 10\beta \equiv 0 \pmod{37}
\Longrightarrow
10(\beta-\alpha) \equiv 0 \pmod{37}
$$

となるので（$${27 \equiv -10 \pmod{37}}$$ を使いました）、$${\alpha=\gamma}$$ の場合と同様の理屈で $${\beta=\alpha}$$ も言えます。つまり方陣に並べた数たちについて、各列（縦の並び）の和は一致しなくてはならないことになります。

ここまでの考察を、90度および270度回転させた方陣について行えば、同様にして方陣の各行（横の並び）の和も一致しなくてはならないことになります。というわけで、(1) の性質を満たすような数は準魔方陣（縦と横の並びの和が全て等しいような方陣、つまり魔方陣から「斜めの並びの和も等しい」という条件をはずしたもの）に由来する数であることが分かりました。