
No.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 が出てきます。
この回答へのお礼
お礼日時:2017/03/19 04:02
先の問題を解いていて、具体的な整数解をとにかく一組出せれば必ず一般式を求められるのだな、つまり一次不定方程式を解くことができるのだなとようやく理解できました。
互除法を用いるやり方はsyotaoさんの説明してくださったように捉えておこうと思います。この度は回答をありがとうございました。

No.2
- 回答日時:
互除法を使わなくてはイケナイ訳じゃあ無い。
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 と書ける。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
漸化式 an+bn√3=(2+√3)^n 自...
-
「この2式の辺々を掛けて」とあ...
-
逆元の計算方法
-
【等式 x+2y+3y=12を満たす自然...
-
ルートの問題です。
-
連立方程式の解き方
-
β-α=√Dになる途中の計算の意味...
-
√(1+x)のテイラー展開のn...
-
ド忘れしたんですけど、2分の1...
-
エクセルの式がわかる方がおら...
-
acrobat8(standard)で図形を書...
-
2.5みたいな数字を分数になおす...
-
1-分数の解き方
-
1/∞=0は、なぜ?
-
ある人が、A地点を出発してから...
-
これの求め方を教えて下さい!...
-
小学校4年生の算数の教科書で...
-
式の整理
-
ルートの中が、(-6)の2乗の...
-
xを7で割ると商がaで余りがbに...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「この2式の辺々を掛けて」とあ...
-
逆元の計算方法
-
数列について
-
整式P(x)をx²+x+1で割ると余...
-
【等式 x+2y+3y=12を満たす自然...
-
一次不定方程式の整数解のうち...
-
5x+7y=1の整数解を全て求めよ ...
-
証明です
-
数値代入法による恒等式の解説...
-
剰余の定理の問題がわかりません
-
arctanxをf(x)とし、そのn回微...
-
xの二次関数y=x^2+2mx+3mの最小...
-
高校数学
-
画像の計算はエクセルで行うこ...
-
連立方程式が苦手です。ご助力...
-
複素関数 sin(x+iy)について
-
数学の恒等式について質問です...
-
(階差数列) このn=1を代入する...
-
関数、導関数
-
角の二等分線
おすすめ情報
ご指摘を受け、どこが分からないか具体的に自分自身が理解できておらず、質問の説明不足を痛感したため補足いたします。
(模範解答)
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
計算作業としては何をしているのか分かっているのでしょうが、なぜこのやり方で答えの一つが出てくるのかがよく分かっていないのだと思います。
認識できていません。なぜこの問題でそれを使ったのか理解した上で使えていないのだと思います。無理矢理よく分からない道具を使わされている感じです。
模範解答以外のやり方で、係数を減らす為に互除法を利用して、模範解答で導き出したもの(移項していない方)を利用して
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)
という風にもできるようですが、模範解答と違う値が出る理由もよく分かりません……。
係数が比較的少ないときなら、工夫をせずとも少し調べれば簡単に出せますね。互いに素だから、互除法を使えば必ず1は出てくる。1=の形にしたいから、余り1になるまで互除法の計算をして、それを元の係数の形に戻していっているのですね。
ax+by=d は左辺が(a,b)の最大公約数の倍数になってるから、dも(a,b)の最大公約数の倍数である。というのは理解できましたし、ユークリッドの互除法が最大公約数を見つけやすくするためのものだということも分かるのですが……その二つをつながりが理解できていないです。