More than 1 year has passed since last update.

1001法 - 素因数分解を暗算で効率よく行う方法

Last updated at 2023-06-04Posted at 2023-06-04

この記事は？

複数の素数をまとめて判定することで素因数分解を効率的に行う方法を紹介します。

はじめに

素因数分解を暗算・手計算で高速に行う方法として、各素数について割り切れるかを判定する方法が知られていますが、ひとつずつ判定するのは手間がかかります。 $1001$ 法 ¹ を使うと、整数 $n$ が素因数 $7$、$11$、$13$ について割り切れるかについて 同時に 判定できる方法です。
本稿では、 $31$ までの素因数に対して、素因数をひとつずつ判定するのではなくまとめて判定する方法を紹介します。

2、 3、 5（1 の位・桁和）

$2$ および $5$ で割り切れるかどうかは $1$ の位を見ると分かります。
$3$ で割り切れるかどうかは桁和が $3$ の倍数であるかどうかを見れば分かります ² 。

7、 11、 13（1001法）

$1001=7 \times 11 \times 13$ なので、次のことが分かります。

次の各操作を行うことは $7$、 $11$、 $13$ で割り切れるかどうかに影響を与えない。

$1001$ の倍数を加える、$1001$ の倍数から引く
$7$、$11$、$13$ と互いに素な整数を掛ける
$7$、$11$、$13$ と互いに素な整数で割る（割り切れる場合）

これらの操作による遷移で簡単な整数に帰着することによって、 $7$、 $11$、 $13$ のうちどの素因数で割り切れるかを同時に判定します。
遷移結果と割り切れるかどうかの判定は次のとおりです。〇印はその素数で割り切れること、×印は割り切れないことを示しています。なお、どんな正整数から始めても、遷移を繰り返すとこの表のどれかに到達することが証明できます。

遷移の結果	$7$	$11$	$13$
$0$	〇	〇	〇
$1$ ³	×	×	×
$7$、 $49$ ⁴	〇	×	×
$11$、 $121$ ⁴	×	〇	×
$13$、 $169$ ⁴	×	×	〇
$77$	〇	〇	×
$91$	〇	×	〇
$143$	×	〇	〇

例1

$21229$ を考えます。
$21229$ → $208$ → $52$ → $13$ みたいに遷移できる ⁵ ので、これは $13$ では割り切れるが $7$ や $11$ では割り切れないことが分かります。

イメージ

上の遷移のイメージとしては左の $2$ 桁を右に $3$ 桁分に移動させてマイナスするイメージです。

21229
^^

  229
>> 21
-----
  208

あるいは、下 $2$ 桁を左に $3$ 桁移動して

21229
   ^^

29 <<
212
-----
 78

のようにして、 $21229$ → $78$ → $13$ と遷移する方法もあります。

例2

$12467$ を考えます。
$12467$ → $455$ → $91$ みたいに遷移できる ⁶ ので、これは $7$ および $13$ では割り切れるが $11$ では割り切れないことが分かります。

工夫

$1001$ 法は簡単に $3$ 桁以下まで遷移できますが、 $3$ 桁の結果が大きく暗算での判定が難しい場合は引き算などを使ってさらに進めると良いです。例えば結果が $761$ になった場合は $761$ → $240$ と遷移できます ⁷ 。 $240$ は $2$、 $3$、 $5$ しか素因数を持たないので、この場合は $7$、 $11$、 $13$ のいずれでも割り切れないことが分かります。

23、 29（2001法）

$2001=3 \times 23 \times 29$ なので、次のことが分かります。

次の各操作を行うことは $23$、 $29$ で割り切れるかどうかに影響を与えない。

$2001$ の倍数を加える、$2001$ の倍数から引く
$23$、$29$ と互いに素な整数を掛ける
$23$、$29$ と互いに素な整数で割る（割り切れる場合）

例3

先ほどと同じ $21229$ を考えます。
$21229$ → $368$ → $92$ → $23$ みたいに遷移できる ⁸ ので、これは $23$ では割り切れるが $29$ では割り切れないことが分かります。

左に $3$ 桁移動させて $2$ 倍にするイメージですね。

21229
   ^^

58 <<
212
-----
368

17、 19、 31（10013法）

$10013=17 \times 19 \times 31$ なので、次のことが分かります。

次の各操作は $17$、 $19$、 $31$ で割り切れるかどうかに影響を与えない。

$10013$ の倍数を加える、$10013$ の倍数から引く
$17$、$19$、$31$ と互いに素な整数を掛ける
$17$、$19$、$31$ と互いに素な整数で割る（割り切れる場合）

例4

先ほどと同じ $21229$ を考えます。
$21229$ → $1203$ → $401$ みたいに遷移できます ⁹ が、 $401$ は素数なので、これは $17$、$19$、$31$ のいずれでも割り切れないことが分かります。

1003法、 1007法、 992法

$10013$ 法では $4$ 桁ぐらいまでしか下げられないこともあるので、残った数が大きくて暗算が難しいようなら、さらに $1003$ 法・ $1007$ 法・ $992$ 法で進めることができます。
$1003=17 \times 59$ 、$1007=19 \times 53$ 、$992=2^5 \times 31$ なので、それぞれ $17$、 $19$、 $31$ で割り切れるかどうかが判定できます ¹⁰ 。例えば先ほどの例だと、 $1203$ まで進んだあと、 $17$ で割り切れるかのチェックでは $1203$ → $200$ → $1$ 、$19$ で割り切れるかのチェックでは $1203$ → $196$ → $1$ 、$31$ で割り切れるかのチェックでは $1203$ → $211$ → $180$ → $1$ などのように遷移することができ、いずれも割り切れないことが確認できます。
この場合は各素数ごとに判定する必要があり、同時に判定するのに比べると少し手間が増えてしまいます。なるべく複数の素数での判定を同時に進め、どうしても暗算が難しい場合にのみ個別の素数ごとに判定すると良いでしょう。

その他の素数

上記で $31$ 以下の素数についてまとめて判定できることが分かりました。 $37$ 以上の素数についても同様の方法を考えることはできそうですね。気が向いたら書きます ¹¹ 。

宣伝（素数電卓）

素因数分解を手元でやりたいときに便利な電卓です。普通の電卓に比べると整数演算に特化しています。

Android 限定だけど、「素数電卓」で検索すると出てくるきりさんアプリがおすすめです！
大きな整数でも比較的高速に素因数分解してくれます。 pic.twitter.com/Yl2p9yxqT4
— きり (@kiri8128) May 15, 2023

まとめ

素因数分解を暗算や手計算で行う場合は、各素因数で割り切れるかどうかを判定する必要がある。
複数の素因数で割り切れるかどうかを同時に行う方法を使うと効率よく素因数分解ができることがある。

$1001$ 法という名称は筆者が勝手に呼んでいるものです。正式名称があるのかは知りません。 ↩
桁和が $9$ で割り切れるかどうかを見ると、 $3$ で $2$ 回以上割り切れるときの判定が少なくて済みます。 ↩
$7$、 $11$、 $13$ 以外の素数のみで構成される合成数になった場合は一気に $1$ に遷移できます。どの段階からジャンプするかは、どの段階まで暗算できるかによるので、慣れるまでは少しずつ遷移するので大丈夫です。 ↩
平方数の形になったときも $49$ → $980$ → $21$ → $7$ や $121$ → $880$ → $11$ のように遷移することはできるので、平方数は必ずしもこの表に入れなくてもよいのですが、遠回りになってしまうので遷移結果として覚えてしまうと良いかもしれません。 ↩ ↩² ↩³
最初の遷移は $21021$ を引いています。 $2$ 番目と $3$ 番目ではそれぞれ $4$ で割っています。 ↩
最初の遷移は $12012$ を引いています。 $2$ 番目の遷移では $5$ で割っています。 ↩
$1001$ から引いた。もちろん $761$ が素数であることを覚えていれば一気に $1$ に遷移してよい。 ↩
最初の遷移では $58029$ から引いています。 $2$ 番目と $3$ 番目ではそれぞれ $4$ で割っています。 ↩
最初の遷移では $20026$ を引いています。一万の位の $13$ 倍を引くイメージです。 $2$ 番目の遷移は $3$ で割っています ↩
これは $10013$ 法である程度小さくした後に行うことができます。なお $10013$ 法を使わずに最初から $1003$ 法、 $1007$ 法を使うと、それ自体はそれぞれ $59$、 $53$ で割り切れるかの判定にもなっています。 ↩
ちなみに $37$ については $999$ 法が効率良いですが、複数の素数を同時に判定している訳ではありません。 ↩
このツイート見て思い出したけどフェルマー法が使える場合もあるんだった。これも気が向いたら書くかもです。 ↩
このツイートが記事書こうと思ったきっかけだったりします。 $1001$ 法もう少し広まって欲しいですね。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up