「末尾を2倍して引いていくと7で割り切れるかわかる」の一般化

　なにか見たので。

末尾を2倍して引いていくと7で割り切れるかわかる

• $16,415$

　は $7$ で割り切れるでしょうか。これは、以下のような操作によって判別できます。

• $1,641-5 \times 2 = 1,631$
• $163-1 \times 2 = 161$
• $16 -1 \times 2 = 14$

　$14$ はあきらかに $7$ で割り切れるので、割り切れます。

なぜこうなるのか（3の場合）

　説明がしやすいため、まずは簡単な $3$ の場合でお話しします。

　以後、あまりが同じになることを、$\equiv$ という記号で表現します。また、「何に対してのあまりか」ということを $\mod{}$ と表現します。

例）

• $10 \equiv 3 \mod 7$
• $4 \equiv -1 \mod 5$

　さて、ここで仮に、

10a+b \equiv a+b

　という関係が成り立ったとします。このとき、$10$ 進数で表現される数は、

\displaylines{
100p+10q+r \\
\equiv 10(10p+q)+r \\
\equiv 10(p + q) + r \\
\equiv (p + q) + r \\
\equiv p + q + r
}

　とドミノ倒し的に $10$ を消していくことができます。その結果、その数自体のあまりと、各桁の和のあまりは一致することがわかります。

　そして、$\mod{3}$ や$\mod{9}$ においては常にこのような関係が成り立ちます。

• $10a+b \equiv a+(3\times3)a+b \equiv a+b \mod{3}$
• $10a+b \equiv a+9a+b \equiv a+b \mod{9}$

「$3$ や $9$ で割り切れるかを調べるためには、各桁の和を見ればよい」というのはよく知られた事実だと思いますが、このように考えることもできます。

7の場合・左バージョン

　では $7$ の場合を考えてみましょう。今度は、

10a+b \equiv 3a+b

　となるので、ドミノ倒しに余計なかけ算が発生します。

\displaylines{
100p+10q+r \\
\equiv 10(10p+q)+r \\
\equiv 10(3p + q) + r \\
\equiv 3(3p + q) + r \\
\equiv 9p + 3q + r
}

　要は、左にいくごとに $3$ 倍されます。

　しかし、この状態でも 左から ドミノ倒しをすることはできます。冒頭の $16,415$ で検証しましょう。

• $1\times3 + 6 = 9$
• $9\times3 + 4 = 31 \equiv 10 \equiv 3$
• $3\times3 + 1 = 10 \equiv 3$
• $3\times3 + 5 = 14$

　$14$ はあきらかに $7$ で割り切れるので、割り切れます。

7の場合・右バージョン

　しかし、左からドミノ倒しする方式はなんとも収まりが悪いです。右からドミノ倒ししたい。そのためには、

10a+b \equiv a+?b \mod{7}

　という形で変換できると嬉しい。では、この「？」とはなにか。

　あまりが $0$ であるとき、$0$ 以外の何で割っても構わないので、$10$ で割ってみます。

10a+b \equiv 0  \Longleftrightarrow a+\frac{1}{10}b \equiv 0 \mod{7}

　では、この $\frac{1}{10}$ とはなにか。実は $\mod{7}$ においてはそれは $5$ になります。

• 通常の乗算において、$10$ をかけたら $1$ になるような数を $\frac{1}{10}$ という
• あまりを求める計算においても、$10$ をかけたらあまり $1$ になるような数を $\frac{1}{10}$ という
• $5 \times 10=50=49+1$ であり、あまり $1$ である
• よって、$\frac{1}{10}\equiv 5 \mod{7}$

　つまり、

10a+b \equiv 0  \Longleftrightarrow a+5b \equiv 0 \mod{7}

　となります。これを元に、$16,415$ を右からドミノ倒しをしていきます。

• $1,641+5 \times 5 = 1,666$
• $166+6 \times 5 = 196$
• $19+6 \times 5 = 49$

　$49$ はあきらかに $7$ で割り切れるので、割り切れます。

　さて、$7$ で割ったあまりは $5$ も $-2$ も同じなので、以下のことも言えます。

10a+b \equiv 0  \Longleftrightarrow a-2b \equiv 0 \mod{7}

　これで、なぜ「末尾を $2$ 倍して引いていくと $7$ で割り切れるかわかる」かが証明できました。

一般化

　こうなると、当然「他の数ではどうなるのか」という疑問が湧いていきます。

　今までの議論をまとめると、

• $\frac{1}{10} \mod P$（$10$ の逆元）が存在するならば、右からのドミノ倒しができる

　ということになります。

　では、「$10$ の逆元が存在するか？」については、これは $10$ と $P$ が互いに素である場合には存在します。逆に、そうでない場合には存在しません。プログラムで実際に $10^n \mod P$ を計算してみます。

#include <iostream>
#include <vector>
#include <numeric>  // for std::gcd

int main() {
    const int lim = 30;
    std::vector<std::vector<int>> p(lim);

    for (int i = 1; i < lim; ++i) {
        int mod = i + 1;
        // 10 と (i+1) が互いに素でない場合はスキップ
        if (std::gcd(10, mod) > 1) {
            continue;
        }

        // p[i] を大きさ i+1 で初期化
        p[i].assign(mod, 0);

        std::cout << mod << " : ";

        // p[i][0] = 1
        p[i][0] = 1;

        // 10^j mod (i+1) を順に計算
        for (int j = 0; j < i; ++j) {
            int value = p[i][j] * 10;
            value %= mod;
            p[i][j + 1] = value;
        }

        // ベクトルの中身を出力
        std::cout << "[";
        for (int j = 0; j < mod; ++j) {
            std::cout << p[i][j];
            if (j + 1 < mod) {
                std::cout << ", ";
            }
        }
        std::cout << "]\n";
    }

    return 0;
}

output

3 : [1, 1, 1]
7 : [1, 3, 2, 6, 4, 5, 1]
9 : [1, 1, 1, 1, 1, 1, 1, 1, 1]
11 : [1, 10, 1, 10, 1, 10, 1, 10, 1, 10, 1]
13 : [1, 10, 9, 12, 3, 4, 1, 10, 9, 12, 3, 4, 1]
17 : [1, 10, 15, 14, 4, 6, 9, 5, 16, 7, 2, 3, 13, 11, 8, 12, 1]
19 : [1, 10, 5, 12, 6, 3, 11, 15, 17, 18, 9, 14, 7, 13, 16, 8, 4, 2, 1]
21 : [1, 10, 16, 13, 4, 19, 1, 10, 16, 13, 4, 19, 1, 10, 16, 13, 4, 19, 1, 10, 16]
23 : [1, 10, 8, 11, 18, 19, 6, 14, 2, 20, 16, 22, 13, 15, 12, 5, 4, 17, 9, 21, 3, 7, 1]
27 : [1, 10, 19, 1, 10, 19, 1, 10, 19, 1, 10, 19, 1, 10, 19, 1, 10, 19, 1, 10, 19, 1, 10, 19, 1, 10, 19]
29 : [1, 10, 13, 14, 24, 8, 22, 17, 25, 18, 6, 2, 20, 26, 28, 19, 16, 15, 5, 21, 7, 12, 4, 11, 23, 27, 9, 3, 1]

　$P$ を引いても同じことですので、以下のように調整することもできます。こうすると絶対値が小さくなるとともに、周期性がある場合はわかりやすくなります。（鳩の巣原理より、周期が必ず $P$ 未満になることは示せます）

3 : [1, 1, 1]
7 : [1, 3, 2, -1, -3, -2, 1]
9 : [1, 1, 1, 1, 1, 1, 1, 1, 1]
11 : [1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1]
13 : [1, -3, -4, -1, 3, 4, 1, -3, -4, -1, 3, 4, 1]
17 : [1, -7, -2, -3, 4, 6, -8, 5, -1, 7, 2, 3, -4, -6, 8, -5, 1]
19 : [1, -9, 5, -7, 6, 3, -8, -4, -2, -1, 9, -5, 7, -6, -3, 8, 4, 2, 1]
21 : [1, 10, -5, -8, 4, -2, 1, 10, -5, -8, 4, -2, 1, 10, -5, -8, 4, -2, 1, 10, -5]
23 : [1, 10, 8, 11, -5, -4, 6, -9, 2, -3, -7, -1, -10, -8, -11, 5, 4, -6, 9, -2, 3, 7, 1]
27 : [1, 10, -8, 1, 10, -8, 1, 10, -8, 1, 10, -8, 1, 10, -8, 1, 10, -8, 1, 10, -8, 1, 10, -8, 1, 10, -8]
29 : [1, 10, 13, 14, -5, 8, -7, -12, -4, -11, 6, 2, -9, -3, -1, -10, -13, -14, 5, -8, 7, 12, 4, 11, -6, -2, 9, 3, 1]

　このとき、$1$ になる直前の値が $10$ の逆元になります。

• $3 \rightarrow 1$
• $7 \rightarrow 5 \equiv -2$
• $9 \rightarrow 1$
• $11 \rightarrow 10 \equiv -1$
• $13 \rightarrow 4$
• $17 \rightarrow 12 \equiv -5$
• $19 \rightarrow 2$
• $21 \rightarrow 19 \equiv -2$
• $23 \rightarrow 16 \equiv -7$
• $27 \rightarrow 19 \equiv -8$
• $29 \rightarrow 3$

検証

P=3または9

　その数自体のあまりと、各桁の和のあまりが等しいことは良く知られた事実です。

P=11

　その数自体のあまりと、奇数桁と偶数桁を差し引きしたもののあまりが等しいことは良く知られた事実です。

P=13

• $16,042\quad(=13 \times 1234)$
• $1,604 + 2\times4 = 1,612$
• $161 + 2\times4 = 169$
• $16 + 9\times4 = 52$
• $5 + 2\times4 = 13$

P=17

• $20,978\quad(=17 \times 1234)$
• $2,097-8\times5 = 2,057$
• $205 - 7\times5 = 170$

P=19

• $23,446\quad(=19 \times 1234)$
• $2,344 + 6\times2 = 2,356$
• $235 + 6\times2 = 247$
• $24 + 7\times2 = 38$
• $3 + 8\times2 = 19$

P=29

• $35,786\quad(=29 \times 1234)$
• $3,578 + 6\times3 = 3,596$
• $359 + 6\times3 = 377$
• $37 + 7\times3 = 58$
• $5 + 8\times3 = 29$

　現実的な実用性はともかく、このような組み合わせは無限にあることがわかります

ドミノ倒しの仕組み

　ここで、これまで「ドミノ倒し」と呼んでいた仕組みについてもう少し詳しく見ています。

\displaylines{
1\cdot10^4 + 6\cdot10^3 + 4\cdot10^2 + 1\cdot10^1 + 5\cdot10^0 \equiv 0 \mod 7\\
\Leftrightarrow 1\cdot3^4 + 6\cdot3^3 + 4\cdot3^2 + 1\cdot3^1 + 5\cdot3^0 \equiv 0 \mod 7\\
\Leftrightarrow 1\cdot4 + 6\cdot6 + 4\cdot2 + 1\cdot3 + 5\cdot1 \equiv 0 \mod 7\\
}

　これが左からのドミノ倒しの表現。

\displaylines{
1\cdot10^{0} + 6\cdot10^{-1} + 4\cdot10^{-2} + 1\cdot10^{-3} + 5\cdot10^{-4} \equiv 0 \mod 7\\
\Leftrightarrow 1\cdot5^0 + 6\cdot5^1 + 4\cdot5^2 + 1\cdot5^3 + 5\cdot5^4 \equiv 0 \mod 7\\
\Leftrightarrow 1\cdot1 + 6\cdot5 + 4\cdot4 + 1\cdot6 + 5\cdot2 \equiv 0 \mod 7\\
}

　これが右からのドミノ倒しの表現。

\cdots \rightarrow 1 \rightarrow 5 \rightarrow 4 \rightarrow 6 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow \cdots

　左からの表現も、右からの表現も、この無限ループを異なる位置で切り出した係数を選んでいる に過ぎないことがわかります。

　ここで面白いのは、あまりが $0$ であるとき、この切り出し位置は どこからでも良い ことです。なぜなら、

• $0$ になにをかけても $0$ なので、当然 $10$ をかけてもよい
• $10$ をかけた場合、$10$ 進数上での桁がひとつずれることを意味する
• $10$ で割った場合、逆方向にずれることを意味する

　からです。

　実際に $16,415$ で検証してみます。

　ぜんぶ $7$ で割り切れる！