tsujimotterのノートブック

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

【あけおめ】2022を素因数分解しよう

あけましておめでとうございます!

今年も楽しく日曜数学して、その様子を発信していきたいと思いますので、どうぞよろしくお願いします! ぜひ一緒に日曜数学しましょう!


2022年最初の記事では

2022

を素因数分解してみたいと思います!


f:id:tsujimotter:20220101125318p:plain:w320


もちろん、素数チェッカーWikipediaの記事を調べれば、ただちに素因数分解の結果が分かってしまいます。

それではちょっと面白くないので、今回は 手計算でできる方法 にこだわってみたいと思います。


単に素因数分解するだけではなく、分解するための方法についても紹介したいと思います。

それではいきましょう!


みなさんもよかったら自分でも計算してみてくださいね!
(自分で計算してみたい人は、一旦ここで止めて考えてみてください。)






2022は2の倍数(偶数)

2の倍数判定は下一桁だけを見れば十分です。

下一桁が偶数ならば、元の数も偶数

2022なので、明らかに2で割り切れますね。

 2022
 \downarrow
 2 \times 1011


1011は3の倍数

これ以上2で割り切れないことはわかるので、次は  1011 が3の倍数かどうか調べます。

有名な3の倍数判定法

すべての桁を足し合わせたときに結果が3の倍数ならば、元の数も3の倍数

を使えば良さそうですね。

すべての桁を足し合わせると、

 1011 \longrightarrow 1 + 0 + 1 + 1 = 3

となり、1011が3の倍数であることがわかりますね。


 1011 を3で割るとこうなります:

 1011
 \downarrow
 3 \times 337


337は素数

あとは、337を素因数分解すればよいですね。

 2, 3 の倍数でないことはすぐにわかるので、5以上の素数で割り切れるかどうか調べればよいでしょう。どこまで調べれば良いでしょうか。

 19^2 がだいたい  400 なので、19まで調べればよいとわかります。より正確には

 19^2 = (20 - 1)^2 = 20^2 - 40 + 1 = 361

なので、 337 < 19^2 となります。素因数分解したときの最小の素因数の2乗は元の数以下となるはずなので、19は考える必要はありません。

したがって、 5, 7, 11, 13, 17 の倍数判定を実行すればよいですね。順に実行してみましょう。

5の倍数判定:

5の倍数になるのは「下一桁が0または5のときだけ」なので、337は5の倍数ではありません。

7の倍数判定:

二桁ずつ区切って  3 37 とします。

 2\times 3 + 37 = 43

であり、 43 は7で割り切れないので、7の倍数ではありません。
(ここでは、 \bmod{7} 100 \equiv 2 \pmod{7} であることを使っています。)


あるいは、今回の場合は  337 - 7 = 330 で、 33 が7の倍数ではないことがわかるので、より簡単に判定できますね。

11の倍数判定:

 337 33 の部分が11の倍数で、残りの  7 が11の倍数ではないので、 337 は11の倍数ではありません。

13の倍数判定:

337の下一桁に3を足すとキリがよい数になりそうなので、それを活用します。

 337
 \downarrow +13
 350
 \downarrow \div 10
 35

最後の  35 が13の倍数ではないので、 337 は13の倍数ではありません。

17の倍数判定:

13の倍数のときと同様に、17を引くとキリがよい数になるので、それを活用します。

 337
 \downarrow -17
 320
 \downarrow \div 10
 32

最後の  32 が17の倍数ではないので、 337 は17の倍数ではありません。


 337 2, 3, 5, 7, 11, 13, 17 のいずれでも割り切れないので、 337 は素数であることがわかりました。


したがって、2022の素因数分解が

 2022 = 2 \times 3 \times 337

と確定しました! やりましたね!!



ちなみに、素数大富豪プレーヤーに聞いてみたら

733 と 373 と 337 は素数

らしいですよ。よかったらこれを機に覚えてみてくださいね。笑


より高度な方法:Legendreの定理

以上の計算は正しい計算ですが、もう少し判定すべき素因数が少なくなると嬉しいですよね。

ここでは、

 337 = 256 + 81 = 16^2 + 9^2 = 4^4 + 3^4

と表せることに着目します。
(平方数をたくさん覚えている人なら、こういう計算は得意そうですね!)


この式は  X = 4, \; Y = 3 として

 337 = X^4 + Y^4

と書けるわけですが、ここで以下の記事で紹介した「Legendreの定理」を使います。(つい最近仕入れた知識を使っていきます。笑)
tsujimotter.hatenablog.com


 X^4 + Y^4 を整数係数の多項式と見たときに、これ以上分解できません。(指数の部分の素因数に奇数があれば分解できる場合があります。)
よって、 X^m + Y^m m < 4)の形の代数的因子は存在しないので、Legendreの定理における例外ケースは考える必要がありません。

したがって、Legendreの定理によると、 337 = X^4 + Y^4 の素因数  p はすべて

 p = 8k + 1 k は正の整数)

の形に限定されます。

一般に、 N = X^n + Y^n X, Y は互いに素)という数の素因数  p は、「 X^m + Y^m m < n)という形の約数の素因数」という例外を除いて  p = (2n)k + 1 k は正の整数)の形で表せます。


つまり、判定すべき素因数は

 \require{cancel}\cancel{8\cdot 1 + 1 = 9 \;\;\;\; (素数ではない)}

 8\cdot 2 + 1 = 17(素数)

だけを考えればよいことになります! つまり、17の倍数判定だけで十分 ということですね!


こんな風に強い定理を知っていると、具体的に素因数分解に役立てられるというのは面白いですね!



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

今年もどうぞよろしくお願いいたします!