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の倍数判定だけで十分ということですね！

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

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

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