質問: 代数学の問題です。 正整数a,b,nに対して、1=ab(mod n)の時、 b=a^-1 (mod n) と書く。 19^-1 (mod71) を71未満の正整数として求めよ。
回答: 正しくは bに関する合同方程式1=ab(mod n)が「解を持つとき」、その解をa^-1と書く ですね 一次合同式は必ずしも解を持たないので それはともかく、これにより19^-1は 19x≡1 (mod 71) を解けばいいことになります せっかくの合同式なのでユークリッドなんて使わずにちゃんと合同式でやります (与式) (以下法は省略) ⇔76x≡4 (両辺4倍, gcd(71,4)=1) ⇔5x≡4 (76-5=71より) ⇔70x≡56 (両辺14倍、gcd(71,14)=1) ⇔-x≡56 (70-(-1)=71より) ⇔x≡-56 (両辺-1倍) ⇔x≡15 (-56-15=-71より) 検算 19×15-1 =284 =71×4