色々検索してみましたが、やはりさっぱり理解できなかったため、お聞きしたいです。

タイトルの通りなのですが、例えば「11x+19y=1という等式を満たす整数x,yの組を一つ求めよ」という問題があったとき、その解説を見てもなぜそうするのかを理解できませんでした。そもそも何をやっているのか本当に理解していないからなのかもしれませんが……。どうかご教授願います。

質問者からの補足コメント

  • ご指摘を受け、どこが分からないか具体的に自分自身が理解できておらず、質問の説明不足を痛感したため補足いたします。

    (模範解答)
    19=11・1+8 移項すると8=19-11・1
    11=8・1+3 移項すると3=11-8・1
    8=3・2+2 移項すると2=8-3・2
    3=2・1+1 移項すると1=3-2・1
    よって 1=3-2・1=3-(8-3・2)・1
    =8・(-1)+3・3=8・(-1)+(11-8・1)・3
    =11・3+8・(-4)=11・3+(19-11・1)・(-4)
    =11・7+19・(-4)
    すなわち11・7+19・(-4)=1……①
    ゆえに、求める整数x,yの組の一つはx=7,y=-4

    計算作業としては何をしているのか分かっているのでしょうが、なぜこのやり方で答えの一つが出てくるのかがよく分かっていないのだと思います。

      補足日時:2017/03/17 23:17
  • 認識できていません。なぜこの問題でそれを使ったのか理解した上で使えていないのだと思います。無理矢理よく分からない道具を使わされている感じです。
    模範解答以外のやり方で、係数を減らす為に互除法を利用して、模範解答で導き出したもの(移項していない方)を利用して
    11x+19y=1
    ⇔11x+(11+8)y=1
    ⇔11(x+y)+8y=1
    ここでx+y=p……①とおいて
    11p+8y=1
    ⇔(8・1+3)p+8y=1
    ⇔3p+8(y+p)=1
    ここでy+p=q……②とおいて
    3p+8q=1
    これを満たす整数解の一組はp=-5,q=2
    よってその時のy,xは
    y=q-p=2-(-5)=7(∵②)
    x=p-y=-5-7=-12(∵①)
    よって求める整数解のうち一組は(x,y)=(-12,7)
    という風にもできるようですが、模範解答と違う値が出る理由もよく分かりません……。

    No.1の回答に寄せられた補足コメントです。 補足日時:2017/03/17 23:18
  • 係数が比較的少ないときなら、工夫をせずとも少し調べれば簡単に出せますね。互いに素だから、互除法を使えば必ず1は出てくる。1=の形にしたいから、余り1になるまで互除法の計算をして、それを元の係数の形に戻していっているのですね。
    ax+by=d は左辺が(a,b)の最大公約数の倍数になってるから、dも(a,b)の最大公約数の倍数である。というのは理解できましたし、ユークリッドの互除法が最大公約数を見つけやすくするためのものだということも分かるのですが……その二つをつながりが理解できていないです。

    No.2の回答に寄せられた補足コメントです。 補足日時:2017/03/17 23:27

A 回答 (3件)

う~ん、整数問題むずかしいよね。


互除法で最大公約数を求めるのを知っているのならば、こう考えたらどうですか?
互除法で計算してると、最後はどこかで割り切れますね。そしてその割り切れる式の
1つ前の式の計算で出る余りが最大公約数になるということだから、2数が互いに素ならば
最大公約数はもともと1なので、この割り切れる式の前の式の余りはかならず1でなくちゃいけない。
ということは、互いに素な2数の互除法の計算ではかならず余りが1になる式が出てくるということです。
だからこの式を1=・・・と書きなおして逆算すれば、1=2数の整数倍の和として表わせるので、
整数解の1つが互除法によって求められるということです。

それと、11x+19y=1は一般の整数解としてx=7+19t、y=-4-11t(tは任意の整数)となるのです。
つまり、解は無数にあります。
ここでt=0とすれば互除法で求めた整数解x=7、y=-4が、またt=-1とおけば
主さんが出したx=-12、y=7 が出てきます。
    • good
    • 0
この回答へのお礼

先の問題を解いていて、具体的な整数解をとにかく一組出せれば必ず一般式を求められるのだな、つまり一次不定方程式を解くことができるのだなとようやく理解できました。
互除法を用いるやり方はsyotaoさんの説明してくださったように捉えておこうと思います。この度は回答をありがとうございました。

お礼日時:2017/03/19 04:02

互除法を使わなくてはイケナイ訳じゃあ無い。


11を何倍かした物を19で割って1余る数を求めれば良いわけで、x=7,y=4の場合にそうなる事は少し試すと解る。だから特殊解はx=7,y=-4。

これを機械的にする。
余りが1をなるまで繰り返す。理由は1=の形にしたいから・・。

19=11×1 + 8
11=8×1 + 3
8=3×2 + 2
3=2×1 + 1・・・・+1が出てきたから、ここまで

上の式を余り= ○ に変形しながら、下から上に辿る

①1=3 - 2×1
②2=8 - 3×2
③3=11 - 8×1
④8=19 - 11×1 この最後の式が11×○ + 19×□の形になる。

①の2に②を代入
1=3 - (8-3×2)×1 = 3-8+3×2 = 3×3 - 8

この右辺の3に③を代入
1=(11 - 8×1)×3 - 8 =11×3 -8×4

この右辺の8に④を代入
1=11×3 -(19 - 11×1)×4 = 11×7 + 19×(-4)

1=11×○ + 19×□ の形になった。

ユークリッドの互除法は最大公約数を求める時に便利。
ax+by=d を解くというのは、左辺が(a,b)の最大公約数の倍数になってるから、dも(a,b)の最大公約数の倍数。

最大公約数をmとすれば
a(mx)+b(my)=d と書ける。
この回答への補足あり
    • good
    • 1

どのような解説のどこが理解できなかったのかまったくわからんのだけど....



「互除法を使わなければならない」などということはない, ということは認識できていますか?
この回答への補足あり
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aと関連する良く見られている質問

Qx^y=y^x (x>y)を満たす整数解は、x=4,y=2以外にありま

x^y=y^x (x>y)を満たす整数解は、x=4,y=2以外にありますか?

また、この解の求め方が分る方がいらっしゃったら教えて下さい。

Aベストアンサー

自然数の範囲で、やってみよう。

xのy乗 = yのx乗 = z が成立しているとする。
z の素因数分解を考えれば、
x と y の素因数は共通であることが解る。
素因数 p の x における指数を a、
y における指数を b と置くと、
p の z における指数から
ay = bx である。
x > y > 0 より、a > b と解る。
これが各 p で成り立つから、
x は y で割り切れる。

x = ky と置く。
x > y より、k > 1 である。
ここで、最初の式に戻ると、
zのy乗根 = kx = yのk乗 が成り立つ。
D(n) = (yのn乗) - ny と置くと、
任意の y に対して D(1) = 0 であるが、
y > 2 のときは、D(n+1) - D(n) = (y-1)(yのn乗) - y
> (yのn乗) - y ≧ 0 だから
n > 1 で D(n) > 0 となる。
従って、D(k) = 0 となる解があるのは、
y ≦ 2 に限られる。

y = 2 の場合を解く際も、
上記の考えをたどって、k = 2 に絞られるから、
(x,y) = (4;2) のみが得られる。

y = 1 を代入すると、x = 1 となって、
x > y より、これは解でない。

自然数の範囲で、やってみよう。

xのy乗 = yのx乗 = z が成立しているとする。
z の素因数分解を考えれば、
x と y の素因数は共通であることが解る。
素因数 p の x における指数を a、
y における指数を b と置くと、
p の z における指数から
ay = bx である。
x > y > 0 より、a > b と解る。
これが各 p で成り立つから、
x は y で割り切れる。

x = ky と置く。
x > y より、k > 1 である。
ここで、最初の式に戻ると、
zのy乗根 = kx = yのk乗 が成り立つ。
D(n) = (yのn乗) - ny ...続きを読む

Qx^2=y^2+15を満たす整数の組(x,y)

数学Iの問題です。x^2=y^2+15を満たす整数の組(x,y)を求めてください。
一応こんな風にはなったんですがここからが分かりません。

x^2=y^2+15
x^2-y^2=15
(x+y)(x-y)=15
従って
(x+y,x-y)=1,15 3,5 5,3 15,1 -1,-15 -3,-5 -5,-3 -15,-1

よろしくお願いします。

Aベストアンサー

(x+y)(x-y)=15なのだから、かけて15になる組み合わせ1,15 3,5 5,3 15,1 -1,-15 -3,-5 -5,-3 -15,-1を満足させるx,yを求めれば良いのでは…ニャっ!
x+y=1…(1)
x-y=15…(2) x=8,y=-7


x+y=3…(1)
x-y=5…(2) x=4,y=-1

 こんな感じで連立方程式を解いてゆけば良いと思うニャ。途中でxまたはyが整数以外になる組み合わせがあれば、それは除外ニャ。

Qx1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底,{y1,y2,y3}がその双対基底でx=(0,1,0)の時,y1(x),y

[問] ベクトルx1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底とする。
{y1,y2,y3}がその双対基底でx=(0,1,0)の時、
y1(x),y2(x),y3(x)を求めよ。

という問題の解き方をお教え下さい。

双対基底とは
{f;fはF線形空間VからFへの線形写像}
という集合(これをV*と置く)において、
V(dimV=nとする)の一組基底を{v1,v2,…,vn}とすると
fi(vj)=δij(:クロネッカーのデルタ)で定めるV*の部分集合
{f1,f2,…,fn}はV*の基底となる。これを{v1,v2,…,vn}の双対基底と呼ぶ。

まず、
C^3の次元は6(C^3の基底は(1,0,0),(0,1,0),(0,0,1),(i,0,0),(0,i,0),(0,0,i))
だと思うので上記のx1,x2,x3は基底として不足してると思うのです(もう3ベクトル必要?)。

うーん、どのようにしたらいいのでしょうか?

Aベストアンサー

>C^3の次元は6(

これが間違え.
「x1=(1,1,1),x2=(1,1,-1),x3=(1,-1,-1)をC^3の基底」
といってるんだから,係数体はRではなく,C.

あとは定義にしたがって,
dualな基底を書き下せばいいだけ.
y1(x1)=1,y1(x2)=y1(x3)=0であって
v=ax1+bx2+cx2と表わせるわけだし,
v=(v1,v2,v3)とすれば,a,b,cはv1,v2,v3で表現できる
#単なる基底変換の問題.

Q既出の質問 √xが整数 (x=y^2+3n+54 yは自然数)になるy

既出の質問 √xが整数 (x=y^2+3n+54 yは自然数)になるyはいくつでしょうか
で、もしも、(x=y^2+3y+54 yは自然数)になるyはいくつでしょうか
になれば、yを求められるでしょうか。

よく使う手で y^2+3y+54=k^2 自然数k>0とおく。とやって、
左辺に平方の形をつくる。となるけれど、3yでうまくいかない。
3y=2y+yにしてみてもあとが、続かない。
よろしくおねがいします。

Aベストアンサー

y^2+3y+54=k^2
とおけば
4y^2+12y+216=4k^2
(2y+3)^2+207=4k^2
4k^2-(2y+3)^2=207
(2k+2y+3)(2k-2y-3)=3*3*23

あとは、(2k+2y+3)と(2k-2y-3)の組み合わせを調べる。

Q√xが整数 (x=y^2+3n+54 yは自然数)になるyはいくつでし

√xが整数 (x=y^2+3n+54 yは自然数)になるyはいくつでしょうか

Aベストアンサー

nの条件付けは?


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング

おすすめ情報