今回は一次合同方程式を求めるショートカットを作ってみました.
※価格は記事執筆時のものです. 現在の価格はApp Storeから確認ください.
レビュー時のバージョン : v2.1.1
スポンサーリンク
一次合同方程式の解
今回, 法は5以上の素数 とします.
合成数の法はちょっとややこしいですからね.
整数 と法 による合同方程式
は, であるときのみただ一つの解を持ちます.
今回も絶対値最小剰余として求めるため, なる を から一つずつカウントダウンして探します.
フロー
まず法の入力を要求し, 素数判定の関数を呼び, 問題なければそれを変数 p として扱います.
逆数の候補として の結果を変数 a^-1 に置きます.
続いて x の係数に相当する a を入力させます.
a および p が互いに素であるかを確認するため, ユークリッドの互除法を計算する関数を呼び出します.
結果が 1 より大きければ本ショートカットを初めからやり直します.
の に相当する値の入力を要求すれば準備が整いました.
あとは a と 逆数候補 a^-1 を掛け合わせ, 法 p で 1 と合同になるかチェックします.
結果が 1 になるならば変数 a^-1 は a の逆数なので一旦変数 x に代入します.
1でないならば a^-1 を1つ減らして繰り返しを戻ります.
得られた a の逆数 a^-1(変数は x) を呼び出し, 変数 b をかけ合わせて法 p で整除すれば求める答えが出てきます.
実行
3つの数を代入し, 結果が正しいことを確かめます.
〆
法の値に応じて繰り返し処理を行っているため, 法の大きさにおよそ比例して処理時間は長くなります.
a, b を予め整除するのを忘れていましたね, それを行えば各々が大きな整数でも高々 未満の小さな整数に帰着されます.