わさっきhb

大学（教育研究）とか ，親馬鹿とか，和歌山とか，とか，とか．

今どきの，冪剰余とモジュラ逆数の求め方

授業 math computing

　いきなりですが問題です．

9^{18} \bmod 25を求める，手っ取り早い方法を答えてください．

37^{-1}\equiv x \pmod{102}および1\leq x<102を満たす整数xを求める，手っ取り早い方法を答えてください．

　「何この式?」と思った人は，wikipedia:冪剰余とwikipedia:モジュラ逆数をご覧ください．2つの問題の数値は，一昨日の授業の「おさらい問題」で出題したものです．
　さっそくですが解答です．インターネット接続可能なPC（Windows/Linux/macOSを問いません）を用意して，ブラウザを起動し，以下のページにアクセスしましょう．

　9^{18} \bmod 25については，フォームに「9^18 mod 25」と打ち込んで，Enter（return）キーを押せば，結果に「21」と出ます．「9^18」だけだと，「150 094 635 296 999 121」と表示されまして，25で割った余りを考える際には，百の位以上は考えなくてよい（25で割り切れる）ので，余りは「21」と分かります．
　37^{-1}\equiv x \pmod{102}のほう，フォームに入力するのは「37^-1 mod 102」となります．結果は「91」です．検算として，「37*91%102」*1を計算させると，「(37×91)mod 102」と表示し，結果は「1」です．
　一昨日の授業では，以前に紹介したアルゴリズムに従ってそれぞれ表を作成し，手計算で求められることを解説しました．試験では値を変えて出題すること，答案にはその計算過程を式か表であらわすこと，そしてWolframAlphaへのアクセスに限らず，試験中の電子機器の使用を認めないことを，アナウンスしました．
　昨年度までは，冪剰余の確かめにはLinuxのbcコマンドを，またモジュラ逆数の計算のための拡張ユークリッド互除法に関しては，自作の計算フォームを，紹介していました．昨年度末の学内計算機環境の改変でデスクトップPCが減るとともにLinuxが使えなくなり，自作の計算フォームは時代遅れとなりましたので，今回，Webサービスの利用に切り替えました．

*1:「%」は，CやJavaなどのプログラミング言語での剰余演算子ですが，WolframAlphaでも利用可能でした．ただし「37 * 91 % 102」と空白を入れると，「37×91%×102」と解釈され，結果は「3434」となってしまいました．