数学 - Python - 代数学 - 整数 - 最大公約数(Euclid の互除法、複数の数の最大公約数の求め方)

代数系入門

学習環境

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

代数系入門 (松坂 和夫(著)、岩波書店)の第1章(整数)、3(最大公約数)、問題2.を取り組んでみる。

2. 1. 
      
      $\begin{array}{}7935=5796·\; <!--\; middle\; dot\; -->1+2139\\ 5796=2139·\; <!--\; middle\; dot\; -->2+1518\\ 2139=1518·\; <!--\; middle\; dot\; -->1+621\\ 1518=621·\; <!--\; middle\; dot\; -->2+276\\ 621=276·\; <!--\; middle\; dot\; -->2+69\\ 276=69·\; <!--\; middle\; dot\; -->4\end{array}$

      よって、最大公約数は69。

   2. 
      
      $\begin{array}{}39600=32670·\; <!--\; middle\; dot\; -->1+6930\\ 32670=6930·\; <!--\; middle\; dot\; -->4+4950\\ 6930=4950·\; <!--\; middle\; dot\; -->1+1980\\ 4950=1980·\; <!--\; middle\; dot\; -->2+990\\ 1980=990·\; <!--\; middle\; dot\; -->2\end{array}$

      よって、 39600と32670の最大公約数は990。

      $\begin{array}{}25542=990·\; <!--\; middle\; dot\; -->25+792\\ 990=792·\; <!--\; middle\; dot\; -->1+198\\ 792=198·\; <!--\; middle\; dot\; -->4\end{array}$

      よって、990と25542の最大公約数は198。

      $\begin{array}{}16863=198·\; <!--\; middle\; dot\; -->85+33\\ 198=33·\; <!--\; middle\; dot\; -->6\end{array}$

      よって、 198と16863の最大公約数は33。

      以上より求める最大公約数は33。

コード(Emacs)

Python 3

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

print('2.')
nss = [[5796, 7935],
       [39600, 32670, 25542, 16863]]

for i, ns in enumerate(nss):
    print(f'({chr(ord("a") + i)})')
    for t in [ns, gcd_list(ns)]:
        pprint(t)
        print()
    print()

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

$ ./sample2.py
2.
(a)
[5796, 7935]

69


(b)
[39600, 32670, 25542, 16863]

33


$