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)の組のうち、求まるのは
最も簡単なもののような気がしますが、それは正しいですか?
「最も簡単」というのは適当な表現が見つからないのですが
絶対値が一番小さい数の組み合わせといいますか
既約分数のようなイメージです。
No.1ベストアンサー
- 回答日時:
>これ以外に、Ax+By=1を満たす整数解は存在することはありますか?
質問の意図がわかりにくいが、一般解を求めておく。それで解決なんじゃないの?
xとyの特別解の一つを(α、β)とする。
ax+by=1 ‥‥(1) aα+bβ=1 ‥‥(2) であるから (1)-(2)を作ると、a*(x-α)=b*(β-y)となる。
aとbは互いに素から、mを整数として x-α=bm、β-y=am 。
よって、(x、y)=(bm+α、β-am)。
この回答への補足
回答ありがとうございます。
解いていただいた一般解以外にも解があるかどうかなんですが
この回答からでは、他に解が無いことがよくわかりません。
No.4
- 回答日時:
"拡張 互除法" でネット検索してみましたが、
出てくるのはプログラム関連のページばかりで、
数字のサイトを見かけません。
内容的にも、普通のユークリッド互除法について
書いてあるようです。
どこが「拡張」なのか、結局解りませんでした。
代数的な説明が必要であれば、
"べズー 互除法" で検索
してみることを勧めます。
この回答への補足
回答ありがとうございます。
サイトは結構ですので
必要条件だけを辿っていることを
回答者様の方で説明いただければ結構です。
>どこが「拡張」なのか、結局解りませんでした。
単に最大公約数を求めるのが互除法
そこから、Ax+By=1の形にするのが拡張互除法
ではないのでしょうか?
No.3
- 回答日時:
>Euclidの拡張互除法
についてだけ。「拡張ユークリッドの互除法」or「拡張ユークリッド互除法」で検索したほうがたくさんヒットします。
www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html
「拡張~」のプログラムは謎の方法で書かれていることがあるので、自分で書く場合は手計算でのやり方をそのままプログラムにするというもの一つの手です。
この回答への補足
回答ありがとうございます。
自分の目的を達するためのプログラムは一応できているのですが(もちろんエラーチェック等色々な点でお粗末だとは思います)
今はむしろプログラムより数学的な意味の理解や応用面を知りたいと思っています。
検索するとプログラムが出てくることが多く、また拡張互除法以外の解を知りたいので、なかなか目的のサイトが見つかりません。
No.2
- 回答日時:
No.1 は、文字の使い方が質問文と違うだけで、
同じ方程式の一般解を求め、それが
質問者の解で全てであることを示していますよ。
必要条件をたどって変形したのだから、
他には解はありません。
質問文の x, y, n が、
No.1 では α, β, -m と
書かれています。
「拡張互除法」って、何でしょう?
普通に互除法で A,B の最大公約数を求める際、
A を B で割った余りが C[1]、
B を C[1] で割った余りが C[2]、
C[1] を C[2] で割った余りが C[3]
…と続けていくと、出てくる C[ ] は、
どれも A と B の整数倍の和です。
そして、A と B が互いに素であれば、
どこかで余りが 1 になって終わります。
そこまでの C[ ] を、順次 jA+kB の形に
メモしながら計算を進めれば、
余りが 1 になった時点で、1 = xA+yB が得られます。
この回答への補足
回答ありがとうございます。
必要条件をたどっているのかどうかがわからないのです。
例えば私が質問文に書いた方法のうち「n倍して」が抜けていたら、もちろん他に解が存在することになります。
そのような“抜け”が本当に無いのかがよくわからないのです。
回答後半についてですが、手順だけは理解できていると思います。
質問文の後半は考えた末やっと「0<|y|<A,0<|x|<Bを満たすx,yの組が必ず1組だけ存在し、拡張互除法ではそれを求めている」という言葉になりました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 2次以上の多項式g(x)であって, 任意の無理数に対して無理数の値を取るものは存在しないことを示せ. 8 2022/06/27 11:28
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
- 数学 整数問題4 16 2023/04/02 13:54
- 数学 g=gcd(a,b)とする。このときa|cかつb|cならばab|cgを示せ。という問題を c=qa, 3 2023/05/21 18:31
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 (1) 方程式 65x+31y=1の整数解をすべて求めよ。 (2) 65x+31y=2016 を満た 1 2022/06/29 11:02
- 数学 (3x+4y)・21=810という式についてなのですが、 ①810は21の倍数でない。 ②21の約数 4 2023/01/13 17:03
- 数学 某大学の数学入試問題で、フェルマーの定理絡みの問いがありました。 9 2023/02/14 08:35
- 数学 整数問題5 続き 6 2023/04/06 11:37
- 数学 N を2以上の自然数として,N 個のデータ{xn}を考える。以下の3条件が互いに同値であることを示し 1 2023/04/17 18:41
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
微分の重解条件は公式として使...
-
Excelで合計値を基にデータを均...
-
tanX=Xの解
-
16の4乗根は±2ではない!?
-
微分積分の極限についての問題...
-
cos x = 0の解の書き方について
-
微分方程式
-
文字の定数を含む4次方程式の解...
-
なんで4次方程式f(x)=0がx=2を...
-
定数係数以外の2階常微分方程...
-
無数の解が存在する=すべての...
-
一枚の板から何枚取れるか?
-
3次式の逆関数の求め方
-
x^y=y^x (x>y)を満たす整数解は...
-
中学数学についてです。 二次方...
-
3次方程式
-
次の2つの連立方程式は同じ解を...
-
二次方程式の解の絶対値二つと...
-
連立方程式の解の集合が部分空...
-
方程式についての問題。。。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
高校数学の整数問題です。
-
Excelで合計値を基にデータを均...
-
答えを教えて
-
数学II 三次方程式 x^3-5x^2+ax...
-
解なし≠解はない
-
複数の品目での単価と全体の合...
-
微分の重解条件は公式として使...
-
16の4乗根は±2ではない!?
-
x^y=y^x (x>y)を満たす整数解は...
-
解に3つ以上±や∓がある時複号...
-
点P(x+y、xy)の軌跡を求めよ。...
-
一枚の板から何枚取れるか?
-
3次関数と直線が接する場合、...
-
数学についてです 「 aを定数と...
-
aの値に関係なくとよく問題で見...
-
2次方程式X^2-3X-1=0の2つの...
-
なんで4次方程式f(x)=0がx=2を...
-
何故グラフに接するとき重解に...
-
3次関数と1次関数が接するとき
-
2次方程式の2解がともに0と3の...
おすすめ情報