数論の範囲に入ると思われる事柄で質問があります。

質問

数論の範囲に入ると思われる事柄で質問があります。

18n mod(31)≡1　　-式(1)

この方程式は
n mod(31)≡19　　-式(2)

のときに満たされますが、
この１９を求めるときに、
m:0→30まで試す力技ではなくて、
スマートに説く方法はありますでしょうか？

さらに言えば、もっと一般的に
A×n mod(B)≡C　　-式(1)
でA,B,Cが与えられてる場合にnを求める方法を知りたいです。

回答No.2

Mr_Holland

合同式を使って求める方法もあります。
　（ただしスマートとはいえませんが。）

　式（1）から
18n=31m+1　　・・・・（3）
⇔31m=18n-1
31m≡-1 mod(18)
13m≡-1 mod(18)
∴13m=18n'-1　　・・・・（4）
⇔18n'=13m+1
　18n'≡1 mod(13)
　5n'≡1 mod(13)
∴5n'=13m'+1　　・・・・（5）
⇔13m'=5n'-1
　13m'≡-1 mod(5)
　3m'≡-1 mod(5)
∴3m'=5n''-1　
∴n''=3k+2, m'=5k+3

　式（5）に代入して、　5n'=13m'+1=13(5k+3)+1=65k+40
∴n'=13k+8
　式（4）に代入して、　13m=18n'-1=18(13k+8)-1=234k+143
∴m=18k+11
　式（3）に代入して、　18n=31m+1=31(18k+11)+1=558k+342
∴n=31k+19

∴n mod(31)≡19

＞さらに言えば、もっと一般的に
A×n mod(B)≡C　　-式(1)
でA,B,Cが与えられてる場合にnを求める方法を知りたいです。

　上記のように両辺の入れ替えを行って、法とする数を小さくしていくことになると思います。
　とてもスマートとは言い難いですが。

お礼

ax + by =q

を控除方で解くのと同じようなルーティンで解けるのですね。
ありがとうございました。

31程度大きさの法であっても
数論の高等な知識があれば、
式を見た瞬間にわかるというものでは無いのですね

回答No.1

banakona

あまりスマートとは言えませんが、一般的にはユークリッドの互除法を使います。

３１を１８で割って　１あまり１３　　３１＝１８・１＋１３　　A
１８を１３で割って　１あまり５　　　１８＝１３・１＋５　　　B
１３を５で割って　　２あまり３　　　１３＝５・２＋３　　　　C
５を３で割って　　　１あまり２　　　　５＝３・１＋２　　　　D
３を２で割って　　　１あまり１　　　　３＝２・１＋１　　　　E

Eを変形して　　　　　　　１＝３－２・１
Dを使って２を消去して　　　＝３－（５－３・１）・１＝３－５
Cを使って３を消去して　　　＝（１３－５・２）・２－５＝１３・２－５・５
Bを使って５を消去して　　　＝１３・２－（１８－３・１）・５＝１３・７－１８・５
Aを使って１３を消去して　　＝（３１－１８・１）・７－１８・５＝３１・７－１８・１２

つまり　　　１＝３１・７－１８・１２
となるので、ｎ≡－１２　であることが分かり、－１２≡１９（mod３１）なので　ｎ＝１９

お礼

解答ありがとうございます。
一般的な方法があるのですね。
コーディングして計算させる関数を簡単に作りたいのが目的なので助かりました。