ExtendedGCD ― 2015年01月20日 10:59
「数学の視点」を、例題をいくつか手計算で確認しながら読み進む。Mathematicaがあるのだから、例題に使えるか試したくなる。Cookbookには代数の例は少なかった気がしたけど。
定理２．１．３（数学の視点、から）
正整数m,nの最大公約数がdであれば、
d=pm+qn
を満足する整数p,qが存在する。特にmとnとが互いに素であれば、
1=pm+qn
を満足する整数p,qが存在する。
を受けて、
問題２．１．１
m=36, n=47に対して、36a+47b=1となるa,bを求めよ。
手計算では結構苦労したので、さて。
素人らしく、SolveやRoots、Reduceでは、求める解は出てこない。a,bを整数と指示しても変わらない。ここまでは予想のうち。
悩むこと数分、マニュアルの目次から、整数論に関連する関数の項に、そのものずばりの関数を見つける。ExtendedGCD：拡張版の最大公約数。引数の順番を変えると答えが変わる。いや、あっけない。
拡張版の最大公約数については、ユークリッドの互除法の拡張版で探すと、いろいろなサイトに説明がある。手計算でもう一度、確認。確かに、同じ答えが得られる。
コメント
トラックバック
このエントリのトラックバックURL: http://c5d5e5.asablo.jp/blog/2015/01/20/7542673/tb
※なお、送られたトラックバックはブログの管理者が確認するまで公開されません。
コメントをどうぞ
※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。
※なお、送られたコメントはブログの管理者が確認するまで公開されません。