数学 - Python - 代数学 - 整数 - 素数、素因数分解(和に分解、累乗、約数)

代数系入門

学習環境

• Surface 3 (4G LTE)、Surface 3 タイプ カバー、Surface ペン(端末)
• Windows 10 Pro (OS)
• Nebo(Windows アプリ)
• iPad Pro + Apple Pencil
• MyScript Nebo(iPad アプリ)
• 参考書籍
  • Pythonからはじめる数学入門
  • JavaScriptリファレンス 第6版
  • インタラクティブ・データビジュアライゼーション

代数系入門 (松坂 和夫(著)、岩波書店)の第1章(整数)、5(素数、素因数分解)、問題10.を取り組んでみる。

10. 
    
    $\begin{array}{}{2}^{32}+1\\ =2^{32}+1+5^4·\; <!--\; middle\; dot\; -->2^{28}-5^4·\; <!--\; middle\; dot\; -->2^{28}\\ =\left(5^4·\; <!--\; middle\; dot\; -->2^{28}+2^{32}\right)-\left(5^4·\; <!--\; middle\; dot\; -->2^{28}-1\right)\\ =2^{28}·\; <!--\; middle\; dot\; -->\left(5^4+2^4\right)-\left(5^2·\; <!--\; middle\; dot\; -->2^{14}-1\right)\left(5^2·\; <!--\; middle\; dot\; -->2^{14}+1\right)\\ =2^{28}·\; <!--\; middle\; dot\; -->641-\left(5·\; <!--\; middle\; dot\; -->2^7+1\right)\left(5·\; <!--\; middle\; dot\; -->2^7-1\right)\left(5^2·\; <!--\; middle\; dot\; -->2^{14}+1\right)\\ =2^{28}·\; <!--\; middle\; dot\; -->641-641\left(5·\; <!--\; middle\; dot\; -->2^7-1\right)\left(5^2·\; <!--\; middle\; dot\; -->2^{14}+1\right)\\ =641\left(2^{28}-\left(5-2^7-1\right)\left(5^2-2^{14}+1\right)\right)\end{array}$

    よって、

    $2^{32}+1$

    は641を約数にもつ。

コード(Emacs)

Python 3

#!/usr/bin/env python3
from sympy import pprint, factorint
import functools

n = 641
m = 2 ** 32 + 1

for t in [n, m]:
    for s in [n, factorint(n)]:
        pprint(s)
        print()
    print()

print(m % n == 0)

入出力結果(Terminal, Jupyter(IPython))

$ ./sample10.py
641

{641: 1}


641

{641: 1}


True
$