前提として \(n\) は \(10\) 進数展開された形で与えられるものとする。

まず除数 \(m\) は素冪であると仮定してよい。 そうでなければ因数の素冪ごとに考えればよい。 剰余を求めたい場合は 中国人剰余定理 を用いる。

知る限りどの手法もすべて \(10^k \bmod m\) の値に対する知識を利用する。 列 \(a_0 = 1, a_1 = (10 \bmod m), a_2 = (100 \bmod m), a_3 = (1000 \bmod m), \dots\) があれば \(n = (n _ l n _ {l - 1} \dots n _ 0) _ {10}\) に対し \(n \equiv \sum a_i n_i \pmod{m}\) が成り立ち、これが \(0\) であれば \(m\) の倍数である。

これをすべて覚えるのは難しいので、小さい \(k, a\) で \(10^k \equiv a \pmod{m}\) が成り立つ部分に絞って考える。

  • \(a = 0\) であれば下から \(k\) 桁を \(m\) で割ればよい
  • \(a = 1\) であれば下から \(k\) 桁ごとに区切ってそれらを足し合わせその結果を \(m\) で割ればよい
  • \(a = -1\) であれば下から \(k\) 桁ごとに区切ってそれらの正負を入れ替えながら足し合わせその結果を \(m\) で割ればよい
  • 一般に、下から \(k\) 桁ごとに区切って \(a\) をかけながら足し合わせてその結果を \(m\) で割ればよい

例えば \(m = 13\) の場合では \(1000 \equiv -1 \pmod{13}\) であるので \(123456789 \equiv (123 \cdot (-1) + 456) \cdot (-1) + 789 \equiv 333 \cdot (-1) + 789 \equiv 456 \pmod{13}\) のように畳み込み、その後は普通に筆算などで \(456 \equiv 1 \pmod{13}\) と求める。 畳み込みの途中で数が大きくなってきたら途中で \(m\) で剰余を取ってもかまわない。

特に以下の式が有用だろう。

  • \[1000 \equiv -1 \pmod{7}\]
  • \[1000 \equiv 0 \pmod{8}\]
  • \[10 \equiv 1 \pmod{9}\]
  • \[10 \equiv -1 \pmod{11}\]
  • \[1000 \equiv -1 \pmod{13}\]
  • \[10000 \equiv 0 \pmod{16}\]
  • \[100 \equiv 1 \pmod{33}\]
  • \[100 \equiv 1 \pmod{99}\]
  • \[100 \equiv -1 \pmod{101}\]
  • \[1000 \equiv 1 \pmod{111}\]
  • \[100000 \equiv 1 \pmod{11111}\]
  • \[\dots\]

\(11111 = 41 \cdot 271\) をあわせて知っていれば \(100000 \equiv 1 \pmod{41}\) と \(100000 \equiv 1 \pmod{271}\) も導けるのでrepunitsの素因数分解も知っておくとよいかもしれない。

\(100 \equiv -2 \pmod{17}\) などを追加で覚えてもよいかもしれないが、筆算をするのでもかわらないように思う。 一般に除数 \(m\) が大きくなると手頃な \((k, a)\) の組が見付かりにくくなることから利用は難しくなる。

参考