modの計算について

質問

例えば、
11239*d = 1 (mod40872)においてdを求めるにはどうしたらいいのでしょうか？

計算サイトなどの紹介でもかまいません。

これって普通の電卓と手計算だけでも計算できるものなのでしょうか？

回答No.1

nag0720 · ベストアンサー

ユークリッドの互除法を利用すれば手計算でできます。

40872=11239*3+7155
11239=7155+4084
7155=4084+3071
4084=3071+1013
3071=1013*3+32
1013=32*31+21
32=21+11
21=11+10
11=10+1

これを逆算していけば、
21=11+(11-1)=11*2-1
32*2=21*2+(21+1)=21*3+1
1013*3=32*93+(32*2-1)=32*95-1
3071*95=1013*285+(1013*3+1)=1013*288+1
4084*288=3071*288+(3071*95-1)=3071*383-1
7155*383=4084*383+(4084*288+1)=4084*671+1
11239*671=7155*671+(7155*383-1)=7155*1054-1
40872*1054=11239*3*1054+(11239*671+1)=11239*3833+1

よって、
11239*(-3833) ≡ 11239*(40872-3833) ≡ 11239*37039 ≡ 1 (mod40872)

回答No.3

info22_

#2です。

A#1に計算間違いがありましたので以下のように訂正します。
>11239*d=40872n+1
d=(40872n+1)/11239=3n+(7155n+1)/11239=3n+m
7155n+1=11239m
n=(11239m-1)/7155=m+(4084m-1)/7155=m+k
4084m-1=7155k
m=(7155k+1)/4084=k+(3071k+1)/4084=k+p
3071k+1=4084p
k=(4084p-1)/3071=p+(1013p-1)/3071=p+q
1013p-1=3071q
p=(3071q+1)/1013=3q+(32q+1)/1013=3*q+r
32q+1=1013r
q=(1013r-1)/32=31r+(21r-1)/32=31r+s
21r-1=32s
r=(32s+1)/21=s+(11s+1)/21=s+t
11s+1=21t
s=(21t-1)/11=t+(10t-1)/11=t+u
10t-1=11u
t=(11u+1)/10=u+(u+1)/10=u+v
u+1=10v
u=10v-1

以上から
∴d=40872v-3833

具体的に計算すると
v=1,2,3,4,…　に対して
d=37039,77911,118783,159655,…
[検算]
11239*37039=10185*40872+1=1(mod 40872)
11239*77911=21424*40872+1=1(mod 40872)
11239*118783=32663*40872+1=1(mod 40872)
11239*159655=43902*40872+1=1(mod 40872)
…

回答No.2

info22_

11239*d=40872n+1
d=(40872n+1)/11239=3n+(7155n+1)/11239
7155n+1=11239m
n=(11239m-1)/7155=m+(4084m-1)/7155
4084m-1=7155k
m=(7155k+1)/4084=k+(3071k+1)/4084
3071k+1=4084p
k=(4084p-1)/3071=p+(1013p+1)/3071
1013p+1=3071q
p=(3071q-1)/1013=3q+(32q-1)/1013
32q-1=1013r
q=(1013r+1)/32=31r+(21r+1)/32=31r+s
21r+1=32s
r=(32s-1)/21=s+(11s-1)/21=s+t
11s-1=21t
s=(21t+1)/11=t+(10t+1)/11=t+u
10t+1=11u
t=(11u-1)/10=u+(u-1)/10=u+v
u-1=10v
u=10v+1

以上から
∴d=32640v+3061

v=1,2,3,4,…　に対して
d=35701,68341,100981,133621,…