おはようございます．
引き続き Silverman 『はじめての数論』の演習問題をやっていきます．
今回の問題は，演習問題 6.3 (c) です．
計算機を走らせて即終了という問題ですが，プログラムを書いて計算するのは初めてなので，若干丁寧めにやります．
プログラミング言語は python を使用し，実行環境については VSCode の Jupyter 拡張機能を使います．詳しくはこちらの一連の記事を参照してください．
問題文
次のアルゴリズムを考える．
Output: $a$ と $b$ の最大公約数 $g$ と $ax + by = g$ なる整数 $x, y$
$x \leftarrow 1$, $g \leftarrow a$, $v \leftarrow 0$, $w \leftarrow b$ と初期化する．
While $w \neq 0$ do
$g$ を $w$ で割った商を $q$ とおく．
$g$ を $w$ で割った余りを $t$ とおく．
$s \leftarrow x - qv$．
$(x,g) \leftarrow (v,w)$.
$(v,w) \leftarrow (s,t)$.
$y \leftarrow (g-ax)/b$ とおく．
Return $(g,x,y)$
このアルゴリズムを次の $(a,b)$ に対して実際に動かしてみなさい．
(i) (19789, 23548)
(ii) (31875,8387)
(iii) (22241739, 19848039)
解答
こないだ召喚した jupyter君(VSCodeにおけるすがた) に計算してもらいましょう．
出力をそのまま書くとこんな感じです．
(i) 7 1303 -1095
(ii) 1 -381 1448
(iii) 237 -8980 10063
ちなみに計算風景はこんなん．
やっぱり jupyter はUIが分かりやすくていいですね．
さすが jupyter君計算が早いですね．0.8秒ですか．(逆に計算機にしては遅いのかもしれない……？)
初回なので Wolfram Alpha さんに検算をお願いしましょう．
この方はですね，いろいろと計算をやってくださる Web サービスです．この方がいれば jupyter君要らない説もあるんですが，やっぱり直接命令して動かす方が楽しいので，基本的に Wolfram さんには検算しかお願いしないつもりです．
おー，合ってますね．素晴らしい．
感想とまとめ
プログラミングは初めてなので少し慎重に進めています．
数学科のひとはあまり計算機を重視しないひとが多いですが．実際に具体例の計算をがっつりやろうとすると計算機というランプの魔人が扱えるのはすごく利点が大きいと思います．習得は大変ですけど，その価値がありそう．
Wolfram Alphaさんがいるから要らないと言われればそれまでですが，でも Wolfram さんにも苦手分野はあるわけで，原理的なことがわかってれば応用が利くんじゃないかな…．
