もう一人のY君

iPhoneアプリのレビューやアップデートレビューなどを書いています. たまに数学の記事も書きます.

もう一人のY君 MENU  MENU

【ショートカット】一次合同方程式を求めるショートカット

181110_65

 今回は一次合同方程式を求めるショートカットを作ってみました.

 

ショートカット

ショートカット

  • Apple
  • 仕事効率化
  • 無料

※価格は記事執筆時のものです. 現在の価格はApp Storeから確認ください.

 レビュー時のバージョン : v2.1.1

 

スポンサーリンク

 

 

一次合同方程式の解

 今回, 法は5以上の素数 { \displaystyle p } とします.

 合成数の法はちょっとややこしいですからね.

 

 整数 { \displaystyle a,\,b } と法 { \displaystyle p } による合同方程式

 

{ \displaystyle ax\equiv b\pmod p }

 

は, { \displaystyle \text{gcd}(a,p)=1 } であるときのみただ一つの解を持ちます.

 

 今回も絶対値最小剰余として求めるため, { \displaystyle ab\equiv 1 } なる { \displaystyle b } を { \displaystyle \left[ \frac{p}{2} \right] } から一つずつカウントダウンして探します.

 

 

フロー

181110_66

 まず法の入力を要求し, 素数判定の関数を呼び, 問題なければそれを変数 p として扱います.

 逆数の候補として { \displaystyle \left[ \frac{p}{2} \right] } の結果を変数 a^-1 に置きます.

 

 

181110_67

 続いて x の係数に相当する a を入力させます.

 

 

181110_68

 a および p が互いに素であるかを確認するため, ユークリッドの互除法を計算する関数を呼び出します.

 結果が 1 より大きければ本ショートカットを初めからやり直します.

 

 

181110_69

 { \displaystyle ac\equiv b } の { \displaystyle b } に相当する値の入力を要求すれば準備が整いました.

 あとは a と 逆数候補 a^-1 を掛け合わせ, 法 p で 1 と合同になるかチェックします.

 

 

181110_70

 結果が 1 になるならば変数 a^-1 は a の逆数なので一旦変数 x に代入します.

 1でないならば a^-1 を1つ減らして繰り返しを戻ります.

 

 

181110_71

 得られた a の逆数 a^-1(変数は x) を呼び出し, 変数 b をかけ合わせて法 p で整除すれば求める答えが出てきます.

 

 

実行

181110_72

 3つの数を代入し, 結果が正しいことを確かめます.

 

 

 法の値に応じて繰り返し処理を行っているため, 法の大きさにおよそ比例して処理時間は長くなります.

 

 a, b を予め整除するのを忘れていましたね, それを行えば各々が大きな整数でも高々 { \displaystyle p } 未満の小さな整数に帰着されます.