36x = 1 mod 1019 の解を求めるには？

質問

36x = 1 mod 1019
x はどのように求めたら良いでしょうか。
解法、または関連した解説サイト等あれば教えて下さい。
お願いします。

ちなみに解そのものは判明しています。
x = 368 + 1019k (k=0,1,2,...)
です。

回答No.3

info22 · ベストアンサー

>36x = 1 mod 1019
これを言葉に直せは
36x　は　1019で割ると1 余る数
となります。
つまり
(36x-1) は1019の倍数
という事です。

式で書けば
(36x-1)=1019m　(mはゼロ以上の整数)
これを
xについて解けば
x=(1019m+1)/36=28m+(11m+1)/36
xが整数であるためには
(11m+1）が36の倍数
つまり
11m+1=36n(nは1以上の整数)
m=(36n-1)/11=3n+(3n-1)/11
mがゼロ以上の整数なので(3n-1)は11の倍数
(3n-1)=11p(pは1以上の整数)
n=(11p+1)/3=3p+(2p+1)/3
(2p+1)は3の倍数
2p+1=3q(qは1以上の整数)
p=(3q-1)/2=q+(q-1)/2
q-1は2の倍数
q-1=2k(kはゼロ以上の整数）
q=2k+1
ここから順に遡って代入していくと
p=(3q-1)/2=3k+1
n=(11p+1)/3=11k+4
m=(36n-1)/11=36k+13
x=(1019m+1)/36=28m+(11m+1)/36
=368+1019k(k=0,1,2,...)
と辿り着きます。

回答No.4

zk43

xが一つの解ならば、x+1019kも解である。
逆に、他の解をyとすると、36y≡1（mod 1019）だから、
36x≡1（mod 1019）と辺々引くと、
36(x-y)≡0（mod 1019）
x≡y（mod 1019）
y=x+1019k
と表せる。
よって、一般解は、xを一つの解とすれば、x+1019kの形のもの
全部である。
そこで、一つの解を探す。
普通は、ユークリッドの互除法による。
1019=28・36+11…(1)
36=3・11+3…(2)
11=3・3+2…(3)
3=2+1…(4)
(1)より、11=1019-28・36…(1)’
(2)より、3=36-3・11…(2)’
(3)より、2=11-3・3…(3)’
(4)より、1=3-2…(4)’
(3)’を(4)’に代入すると、
1=3-(11-3・3)=4・3-11
これに(2)’を代入すると、
1=4(36-3・11)-11=4・36-13・11
これに(1)’を代入すると、
1=4・36-13(1019-28・36)=368・36-13・1019
よって、36・368≡1（mod 1019）で、一つの解368が見つかった。
よって、一般解は、368+1019k
自然数解という条件ならば、k=0,1,2,…であり、整数解ということ
ならば、k=0,±1,±2,…
ユークリッドの互除法で検索すれば詳しく分かると思います。

回答No.2

take_5

普通の不定方程式を解けば良い。

条件から、36x-1019y＝1　‥‥(1). xとyの特別解の一つを各々α、βとすると、36α-1019β＝1　‥‥(2).
(1)－(2)より、36*（x-α）＝1019*（y-β）であるが、36と1019は互いに素であるから、kを0以上の整数として、x-α＝1019*kであるから、αの具体値を一つ求めると良い。
(2)より　36（α-28β）-11β＝1と変形できるから、α-28β＝aとすると、36a－11β＝1　‥‥(3).
3a-11（β-3a）＝1と変形して、β-3a＝bとすると、3a-11b＝1となるから、a＝4、b＝1.
β＝3a＋b＝13で、α＝28β＋a＝368.
以上から、x＝α＋1019*k＝368＋1019*k　（k=0、1、2　‥‥）

回答No.1

nious

36x≡1≡1+(13*1019)≡13248 (mod 1019)
36と1019は互いに素だから36で割って、x≡368 (mod 1019)