次の方式の整数解の解き方を教えて下さい。

・58x+47y=1の整数解を求めよ。

お願い致しますm(_ _)m

No.4 ベストアンサー 回答者： htms42 回答日時： 2014/02/22 13:27

やはり、「特殊解」とか「一般解」というのは分かりにくいと思います。

＃１の回答の前半を使わせていただきます。
＞58x+47y=1　→　11x+47(x+y)=11x+47y'=1　(y'=x+y)
→　11(x+4y')+3y'=11x'+3y'=1　(x'=x+4y')
→　2x'+3(3x'+y')=2x'+3y''=1　(y''=3x'+y')
→　2(x'+y'')+y''=2x''+y''=1　(x''=x'+y'')
と、ここで行き止まり。

2x"+y"=1
x"=(1-y")/2
1-y"は偶数です。条件はそれだけです。
1-y"＝２m
x"=m
これから順に逆にたどっていくとx、yがmで表されます。
それが答です。

No.5 回答者： 178-tall 回答日時： 2014/02/23 22:56

< ANo.1

>互除法風の一例だけ…。
>58x+47y=1　→　11x+47(x+y)=11x+47y'=1　(y'=x+y)
>→　11(x+4y')+3y'=11x'+3y'=1　(x'=x+4y')
>→　2x'+3(3x'+y')=2x'+3y''=1　(y''=3x'+y')
>→　2(x'+y'')+y''=2x''+y''=1　(x''=x'+y'')
>と、ここで行き止まり。

実戦では「行き止まり」までつき合う必要なんぞありません。

たとえば途中の　11x'+3y'=1　で、「あ！ x'=2, y'=-7 で成り立つジャン」と感づくこともあり得ますよネ。
そこから戻れば、
x'=x+4y'　に入れて、x=30 。
y'=x+y　に入れて、y=-37 。

え、ANo.1 の「xo=-17, yo=21」と合わないって？

いいえ、この「特解？」は、
>「一般解？」の {x, y} は、整数 k を用いて、
>　x=xo+47*k
>　y=yo-58*k
にて、k=1 としたものなのです。

　　

No.3 回答者： spring135 回答日時： 2014/02/21 00:42

＞58x+47y=1　　　　　　(1)

の整数解を求めよ。


整数解の求め方なんて決まっていて、それに従えば基本的に解けます。

求め方は２つの部分からなっていて、

「解の例(x0,y0)を求めて、一般解(x,y)を求める。」

という手筈です。慣れてくるとこのままできますが、ウォームアップのため

(1)解の例(x0,y0)を仮定して、一般解(x,y)を求める。

(2)解の例(x0,y0)を求める。

という方針で行きます。

(1)解の例(x0,y0)は(1)を満たす。すなわち

58x0+47y0=1　　　　(2)

(1)-(2)より

58(x-x0)+47(y-y0)=0

58と47は共通の約数を持たないのでパラメターtを用いて

x-x0=47t

y-y0=-58t

と書ける。

つまり

x=x0+47t (3)

y=y0-58t　　(4)


(2)解の例(x0,y0)を求める。これは一般に泥臭い仕事になるがスマートに切り抜けるのがコツ。

(1)は

58x+47y≒0

つまりx=1とするとy=-58/47=1.234

58*1-47*1.234≒0

この誤差が1になるようにもっていけばよい。整数解であるから1000倍して

58*1000-47*1234＝2

従って

29000-28999＝1

よって

29000＝58x,x0=500

-28999=47y,y0=617


(3)以上より

x=500+47t

y=-617-58t


これでまったく正解。ただ定数はできるだけ小さいほうがかっこいいという神話が存在する。

x=500+47t＝47(t+10)+30

y=-617-58t=-58(t+10)-37


たとえばt+10を改めてtとおいて

x=47t+30

y=-58t-37

別のtを選ぶことも可能。

No.2 回答者： info22_ 回答日時： 2014/02/20 23:40

58x+47y=1

x,yを整数とすると
47y=1-58x
y=-2x +(1+36x)/47
y,-2xは整数　⇒　(1+36x)/47は整数。
1+36x=47m (mは整数)
36x=47m-1
x=m +(11m-1)/36
x,mは整数　⇒　(11m-1)/36は整数。
11m-1=36n (nは整数)
11m=36n+1
m=3n +(3n+1)/11
m,3nは整数　⇒　(3n+1)/11は整数。
3n+1=11p (pは整数)
3n=11p-1
n=3p+(2p-1)/3
n,3pは整数　⇒　(2p-1)/3は整数。
2p-1=3q (qは整数)
2p=3q+1
p=q +(q+1)/2
p,qは整数　⇒　(q+1)/2は整数。
q+1=2r (rは整数)
q=2r-1
逆順に p → n → m → x → y を求める。
p=2r-1+r=3r-1
n=3(3r-1)+(2r-1)=11r-4
m=3(11r-4)+(3r-1)=36r-13
x=(36r-13)+(11r-4)=47r-17
y=-2(47r-17)+(36r-13)=-58r+21

(答え) (x,y)=(47r-17, 21-58r) (r:任意の整数。r=0,±1,±2,±3,±4, … )

No.1 回答者： 178-tall 回答日時： 2014/02/20 22:56

>・58x+47y=1の整数解を求めよ。

イロイロ手はあるみたいです。
互除法風の一例だけ…。

58x+47y=1　→　11x+47(x+y)=11x+47y'=1　(y'=x+y)
→　11(x+4y')+3y'=11x'+3y'=1　(x'=x+4y')
→　2x'+3(3x'+y')=2x'+3y''=1　(y''=3x'+y')
→　2(x'+y'')+y''=2x''+y''=1　(x''=x'+y'')
と、ここで行き止まり。

最後の式は、x''=0, y''=1 とすれば成立つ。
これが「特解？」。

次いで、 →　を逆行していく。
0=x''=x'+y'' に「x''=0, y''=1」を入れて、x'=-1 。
y''=3x'+y' に「x'=-1, y''=1」を入れて、y'=4 。
x'=x+4y' に「x'=-1, y'=4」を入れて、x=-17 。
y'=x+y に「x=-17, y'=4」を入れて、y=21 。
この「xo=-17, yo=21」が「特解？」。

「一般解？」の {x, y} は、整数 k を用いて、
　x=xo+47*k
　y=yo-58*k
と表せる。