- 締切済み
方程式
kony0の回答
- kony0
- ベストアンサー率36% (175/474)
Step1. まず割ってみる。 97÷11=8…9 11÷9=1…2 9÷2=4…1 Step2. 上の割算を、A=BQ+Rの形で表現すると 97=11*8+9...(*1) 11=9*1+2...(*2) 9=2*4+1...(*3) Step3. 与えられた式の係数に、Step2.の式を適用する。 (START)11x-97y=1 ((*1)を適用)11x-(11*8+9)y=1 11(x-8y)-9y=1 ここで、x-8y=Aとおく。(11A-9y=1) これに(*2)を適用：(9*1+2)A-9y=1 9(A-y)+2A=1 ここで、A-y=Bとおく。(9B+2A=1) これに(*3)を適用：(2*4+1)B+2A=1 2(4B+A)+B=1 さて、4B+A=kとおくと、2k+B=1⇒B=-2k+1 （4B+A=kだから）A=k-4B=9k-4 （A-y=Bだから）y=A-B=11k-5 （x-8y=Aだから）x=A+8y=97k-44 ということで、(x,y)=(97k-44,11k-5)がいえます。 x,yがいずれも整数であることから、A,B,kはいずれも整数であることが言えます。 また逆にkが整数であるならばx,yがいずれも整数であることも言えます。 ということで、kは任意の整数をとることも言えます。
関連するQ&A
- 最大値と最小値について
等式についての最大値の求め方が分からなくて、誰か知っている人がいたら教えてくれませんか？ 等式の問題は 11x-97y=1を満たす整数xとyについてで。 |ｘ－ｙ｜の最小値を求めるのですが、絶対値がでてくると、なんだ？という感じでさっぱりわかりません。 答えは39ですが、 任意の会はx＝-44＋97t y=-5＋11t です。 分かる方がいれば、詳しく教えてくれませんか？ お願いします
- 締切済み
- 数学・算数
- Euclidの拡張互除法
Euclidの拡張互除法 互いに素な自然数A,Bがあるとき、Ax+By=1を満たす整数(x,y)が存在しますね。 また、この式からAB-BA=0をn倍して辺々引くと A(x-nB)+B(y+nA)=1 が成り立つので (x-nB,y+nA)も、Ax+By=1の整数解であると言えます。 これ以外に、Ax+By=1を満たす整数解は存在することはありますか? それと、Euclidの拡張互除法で Ax+By=1を満たす整数(x,y)を求めることができますが 無限に存在する(x,y)の組のうち、求まるのは 最も簡単なもののような気がしますが、それは正しいですか? 「最も簡単」というのは適当な表現が見つからないのですが 絶対値が一番小さい数の組み合わせといいますか 既約分数のようなイメージです。
- ベストアンサー
- 数学・算数
- Euclidの互除法とAx+By=GCM(A,B)となるx,yのイメー
Euclidの互除法とAx+By=GCM(A,B)となるx,yのイメージ Euclidの互除法のイメージとして、 A×Bの長方形を、なるべく大きな正方形で埋めていくようなイメージで捉えていました。 すると最大公約数が求められるイメージはわかるのですが x,yがどういう数なのか今一つ掴めません (代数的にAx+By=GCM(A,B)の式が得られることは理解できています)。 私が思っているようなイメージでなくて結構ですので 互除法のイメージとx,yのイメージが両方掴めるようなモデルをご呈示ください。 また、Euclidの互除法の回数は、最大でも桁数の5倍だそうですが なぜ10進数表記の桁数、つまり常用対数に依存するのでしょうか? 正確な式は自然対数の2倍くらいだったりするのでしょうか。
- ベストアンサー
- 数学・算数