Z/nZにおいて、97÷mを求めよ。 ただし、n=1511、m=503とする。 この問題が解けなくて

Z/nZにおいて、97÷mを求めよ。
ただし、n=1511、m=503とする。
この問題が解けなくてわかりません。
gcd(1511,503)=1はわかりました。
わかる方教えてください！

No.2 回答者： ありものがたり 回答日時： 2024/07/21 08:26

97÷503 ≡ x (mod 1511) となる x を求めるってことは、

97 ≡ 503 x すなわち
97 = 503 x + 1511 y となる整数 x, y を求めばよいわけです。
一次不定方程式の問題です。

gcd(1511,503) = 1 を計算した過程を思い出しましょう。
ユークリッドの互除法を使って、
1511 = 503 ・ 3 + 2,
503 = 2 ・ 251 + 1,
2 = 1 ・ 2 + 0.
1 で割ったとき余り 0 になったから gcd = 1 でしたね。

この途中計算を下から上へたどって、
1 = 503 - 2 ・ 251
　= 503 - ( 1511 - 503 ・ 3 )・ 251
　= 503 ・( 1 + 3 ・ 251 ) - 1511 ・ 251
　= 503 ・754 - 1511 ・ 251
1 = 503 u + 1511 v の解のひとつとして
u = 754, v = -251 が見つかりました。

方程式の両辺を 97 倍すると
97 = 503( 97u ) + 1511( 97v ) となり、
x = 97u, y = 97v が探したいた解(のひとつ)であることがわかります。

ｘ = 97 ・ 754 = 73138 ≡ 610 (mod 1511).
最後は、答えが見やすいように 0 ≦ x < 1511 に整えてあげましょう。

No.1 回答者： mtrajcp 回答日時： 2024/07/21 08:05

503x=97(mod1511)

1511-503*3=2
503-2*251=1
503-251(1511-503*3)=1
503(1+251*3)-251*1511=1
503*754-251*1511=1
503*754=1(mod1511)

754*503x=754*97(mod1511)
x=754*97(mod1511)

x=610(mod1511)
∴
97/503=610(mod1511)