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

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

「パッと見素数」

です。
motcho.hateblo.jp

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

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

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

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

「７の倍数」と「１３の倍数」の判定が課題

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

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

２の倍数と５の倍数は下１桁目ですぐに判定できますし、３の倍数や１１の倍数もよい判定法があります。

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

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

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

91 をどう使うか

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

$91 = 7 \times 13$

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

この事実を使って，「７の倍数の判定」と「１３の倍数の判定」を「同時に」行うのです！

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

ユークリッドの互除法

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

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

$(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 を使った「７の倍数」「１３の倍数」同時判定法

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

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

$n$ と $91$ の最大公約数	$n$ は「 $7$ の倍数」か？	$n$ は「 $13$ の倍数」か？
$1$	NO	NO
$7$	YES	NO
$13$	NO	YES
$91$	YES	YES

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

すごくないですか？

実際に計算してみる前に、ユークリッドの互除法のコツを一つ紹介します。今回の互除法では、使う計算は $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$ の倍数か考えてみましょう（もちろん「３の倍数」でも「２の倍数」でも「５の倍数」でもありません）。

$(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までの素数判定に関する根拠

30030=2*3*5*7*11*13なので、素数計数関数とオイラー関数による値
(π(90090)-π(30030))/(φ(90090)-φ(30030))=5480/11520
は、30030から90090までで「13以下の素数で割れないもののうち素数であるものの割合」です
— ぽ (@myulapo) 2016年11月10日

この
5480/11520≒47.6%
は、5桁の自然数についての同様の式の値
(π(10^5)-π(10^4))/(φ(10^5)-φ(10^4))
に近いはずなので、
"5桁でも13まで確かめれば2つに1つくらい素数"
と言えますね #素数大富豪
— ぽ (@myulapo) 2016年11月10日