代数学

質問

mod997での191の逆元と、191x＋1≡3（mod997）でのxを教えてください。

回答No.3

alice_44

997 と 191 に、ユークリッドの互除法を使うと、
997 = 191・5 + 42
191 = 42・4 + 23
42 = 23・1 + 19
23 = 19・1 + 4
19 = 4・4 + 3
4 = 3・1 + 1
3 = 1・3 ←割り切れた
より、最大公約数は 1 だが、

上記の各式を「余り=…」の形に書き換えると、
42 = 997 - 191・5
23 = 191 - 42・4
19 = 42 - 23
4 = 23 - 19
3 = 19 - 4・4
1 = 4 - 3

これらの式を下から順に使って、中間の余りを
次々に消去してゆくと、
1 = 4 - 3
　= 4 - (19 - 4・4)　　←3を消した
　= 4・5 - 19
　= (23 - 19)・5 - 19　　←4を消した
　= 23・5 - 19・6
　= …
　= 191・261 - 997・50 ←(*)
という式が得られる。
いわゆる「ベズーの等式」というやつ。

質問の前半：
(*)式より、191・261 ≡ 1 (mod 997)。
997 と 191 が互素(最大公約数が 1)であることより、
逆数はただひとつに決まり、261 がソレである。

質問の後半：
方程式は 191x ≡ 3-1 (mod 997) であり、
両辺に上記の 261 を掛けて、x ≡ 522 (mod 997)。
あるいは、(*)式の両辺に 3-1 を掛けてもよい。

回答No.2

アウストラロ ピテクス（@ngkdddjkk）

ちょい訂正

2行目の後ろは
191×6≡149(mod 997)
って書きたかったんですが、間違えてかいてしまいました。

回答No.1

アウストラロ ピテクス（@ngkdddjkk）

191X≡997a+1
997=191×6-149≡149(mod997)
997=149×7-46
997=46×22-15
997=15×67-8
997=8×125-3
997=3×333-2
997=2×499-1
∴191×(6×7×22×67×125×333×499)≡1(mod997)
6×7×22×67×125×333×499≡261(mod997)
逆元は261

191x＋1≡3（mod997）となるxは、
191×(6×7×22×67×125×333)+1≡3(mod997)
x=522