tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

パッと見素数 "91" を素数判定に活用する

91 という数は、見た目が素数っぽくてつい間違えてしまうという

「パッと見素数」

です。
motcho.hateblo.jp


素数と間違えやすいので、たとえば素数を使ったカードゲーム*1においては、間違えて悔しい思いをした方もいるかもしれません。

「いやな数」と思われがちな 91 ですが、tsujimotterとしてはどんな数でも好きになってもらいたい。

そんな風に考えていたかどうかはさておき・・・

もしかしたら 91 が素数判定で活躍するかもしれない というアイデアを得ましたのでご紹介します。


「7の倍数」と「13の倍数」の判定が課題

そもそも「素数判定」ってみなさんどのようにしていますか?

基本的には判定したい数を小さい順に並べられた素数  2, 3, 5, 7 で割っていって、割り切れなければ素数とわかるわけですね。

2の倍数と5の倍数は下1桁目ですぐに判定できますし、3の倍数や11の倍数もよい判定法があります。


もし  2, 3, 5, 7, 11, 13 まで倍数判定できれば:

  •  17^2 = 289 より小さい数はすべて素数判定できたことになります
  • 5桁の数はほぼ半分の確率で素数であることがわかります*2


したがって、「7の倍数の判定」と「13の倍数の判定」ができることが重要な課題となります。

91 をどう使うか

ところで、91を素因数分解すると

 91 = 7 \times 13

となりますね。ちょうど  7 13 を素因数に持ちます。

この事実を使って,「7の倍数の判定」と「13の倍数の判定」を「同時に」行うのです!

使うのは、ユークリッドの互除法 です。

ユークリッドの互除法

ユークリッドの互除法とは、2つの数の共通の約数(公約数)を求める効率的なアルゴリズムです。

6と4の最大公約数は2ですね。このことを記号で以下のように書きます。

 (6, 4) = 2

これぐらいの桁の最大公約数であれば、暗算で簡単に計算できると思うのですが、桁数が大きくなると大変ですね。こんなときにユークリッドの互除法を使います。


ユークリッドの互除法では、「引き算」を使って最大公約数を求める数の桁数を減らしていきます。

 a, b の最大公約数  (a, b) においては、一般的に以下のような式が成り立ちます。

 (a, b) = (a-b, b)

 a > b としておきます。すなわち、一方の数で他方を引いた数の最大公約数は、元の最大公約数に一致するのです。


たとえば、 (1071, 1029) を計算してみましょう。なんでか知りませんが、よく出てくる例なのです。

まず、 1071 から  1029 を引きます。
 =(42, 1029)

次に、 1029 から  42 を引いていきます。引けるだけ引いていいので、  23 \times 42 = 966 を引きます。

 =(42, 21)

さらに  42 から  21 を引いていくと、ちょうど  0 となって消えますね。したがって、 42 21 の最大公約数は  21 となるわけです。

引き算を繰り返しても最大公約数は変わらないので、

 (1071, 1029) = 21

が得られました。

以上がユークリッドの互除法と呼ばれるアルゴリズムです。

91 を使った「7の倍数」「13の倍数」同時判定法

準備が整ったので、本記事の倍数判定法をご紹介します。

ユークリッド互除法を使って、倍数判定したい数  n と 91 との最大公約数をとります。最大公約数のパターンとしては、 1 7 13 91 のいずれかになります。

 n 91 の最大公約数 n は「 7の倍数」か? n は「 13の倍数」か?
 1NONO
 7YESNO
 13NOYES
 91YESYES

そう、ユークリッドの互除法を使うだけで、「7の倍数」と「13の倍数」の判定を同時に行うことができるのです。

すごくないですか?


実際に計算してみる前に、ユークリッドの互除法のコツを一つ紹介します。今回の互除法では、使う計算は  91 の引き算だけですが、この引き算を効率的に暗算する方法です。


暗算が得意な人は感覚でやっていると思うのですが、 91 を引くときは、

 100 を引いてから  9 を足す

という計算をすれば簡単になります。もっとやるなら、

 100 を引いてから  10 を足して  1 を引く

をしてあげればよいでしょう。


それでは、具体例を用いて実際に計算をしてみましょう。


例:4123

f:id:tsujimotter:20170129111154p:plain:w400
 4123 という数は、各桁を足しても  3 の倍数になりませんし、下一桁目は  3 なので  2 の倍数でも  5 の倍数でもありません。

そこで、ユークリッドの互除法を使って、 7 の倍数か  13 の倍数か考えてみましょう。

 (4123, 91)

 4123 から  40\times 91 を引くために、 4000 を引いてから  400 を足して  40 を引きます。

 (483, 91)

次に、 483 から  5\times 91 を引きます。このとき、 500 を引くとマイナスになってしまってやりづらいですね。ここは、一旦先に  50 を足してから  500 5 を引くといいでしょう。

 (28, 91)

さて、これで  28 91 を下回りました。二桁なので素因数分解は簡単ですね。

 28 = 4\times 7

なので  28 7 の倍数です。

したがって、元々の  4123, 91 の最大公約数が  7、つまり  4123 7 の倍数であることがわかりました。

簡単でしょう?


ちなみにこんな風に素因数分解されます。

f:id:tsujimotter:20170129111319p:plain:w400

例:4121

f:id:tsujimotter:20170129111246p:plain:w400
 4121 7 の倍数か  13 の倍数か考えてみましょう(もちろん「3の倍数」でも「2の倍数」でも「5の倍数」でもありません)。
 (4121, 91)

 4121 から  40\times 91 を引くために、 4000 を引いてから  400 を足して  40 を引きます。

 (481, 91)

 5\times 91 を引くために、 50 を足してから  500 5 を引きます。

 (26, 91)

以上より、 26 は明らかに  13 の倍数ですから、 4121 13 の倍数であることがわかりました。

f:id:tsujimotter:20170129111358p:plain:w400


ちなみに、 4127 4129 は素数です*3。ぜひ同じように計算してみてください。

まとめ

今日はユークリッドの互除法と  91 を用いて、「 7 の倍数の判定」と「 13 の倍数の判定」を同時に行う方法についてご紹介しました。


この方法の最大のポイントは、引き算をした結果を「 7 の倍数の判定」と「 13 の倍数の判定」の両方に活用できるという点です。普通に素数判定をすると、 7 の倍数の判定に使った計算は、ほかの素数の判定には利用できませんね。複数の素数を素因数に持つ  91 のような数を用いるとこんなこともできるのです。


もう一つのポイントは、引き算だけで 91 より小さい数に押さえ込めるという点です。二桁の数が 7 の倍数(13の倍数)かどうか判定することは、我々には容易ですね!
(しかも紛らわしい 91 を判定する必要がない)


最後に、こういう身近な話題から数学の一般的なお話ができるのは楽しいですね。ユークリッドの互除法が使えるというのは個人的に驚きで、素数判定の話題を通してユークリッドの互除法が解説できたのは非常に嬉しかったです。


それでは今日はこの辺で。

参考文献

www.adventar.org


*1:たとえば、「素数大富豪」という素晴らしいトランプゲームがあります。 integers.hatenablog.com

*2:参考:13までの素数判定に関する根拠

*3:4127 と 4129 は、素数大富豪なら "4" "Q(12)" "7" or "9" で出すことができるので、ぜひ覚えましょう。