- 締切済み
- 暇なときにでも
証明
a,bを整数とするときZ次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとｂの最大公約数は1である。 (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在する。 という問題です。 参考書の答えに Zを整数の集合とし J={}ax+by|x,y∈ｚ｝ とおく 定義からJは和と整数倍について閉じている a∈J,b∈J と書いてるのですがよく分かりません。 考え方など教えて貰えたら嬉しいです
- suika_11
- お礼率16% (51/305)
- 数学・算数
- 回答数1
- 閲覧数78
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- 回答No.1
- take_5
- ベストアンサー率30% (149/488)
この問題のベースには、以下のユークリッドの互除法があります。 それを集合論で焼きなおしたものです。 整数係数のx、yの一次方程式 ax＋by＝cは、cがaとbの最大公約数の倍数のとき解を持ち、又解を持つのはその時に限る。 ax+by＝1 ‥‥(1)を満たす整数x、yの特別値を各々α、βとする。 従って、aα＋bβ＝1 ‥‥(2) (1)-(2)より a(x-α)＝b(β-y)‥‥(3)。 x-αとβ-yは共に整数であるから、a＝bの時は (1)は a(x＋y)＝1となり 整数x、yの値はない。 a≠bの時は (3)を満たす整数x、yの値が存在するためには a,bはお互いに素である。 a、bがお互いに素でない場合を考えてください。例えば、a＝2、b＝4の時。 逆に、a,bはお互いに素である時に (1)は整数値を持つ。 このとき、mを整数として、x-α＝bm、β-y＝amが一般解である。
関連するQ&A
- 証明について
a,bを整数とするとき次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとｂの最大公約数は1である。 (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在する。 (i)の問題について ２つの整数aとbの最大公約数をGとおくと a=a'G,b=b'G(a',b'はお互いに素）とする。 (1)aをbで割ったときの商をq,余りをrとするとa=bq+r rについて解くと r=a-bq 2つの整数はaとbはa=a'G,b=b'G(a',b'とおけるので r=a'G-b'G この後どのように証明するのでしょうか？ (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在はどのように証明するのでしょうか？
- 締切済み
- 数学・算数
- 証明
a,bを整数とするとき次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとｂの最大公約数は1である。 (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在する。 ★(i)⇒(ii)の証明について ○a, 2a, 3a, …, (b-1)aというb-1個のb-1が分かりません。どうしてb-1と考えるのでしょうか？ また、b-1ではなくnと置いてもいいですか？ ○（1≦k＜l≦b-1）の範囲がどのように現れたのでしょうか？ ○差la-ka=(l-k)aはbで割り切れると分かるのですか？ ○、1≦k＜l≦b-1から1≦l-k≦b-2がどうして現れるのか分かりません ○k-lはbで割り切れないのですか？ またk-ｌはどこから現れたのですか？ ○kaをbで割った余りが1であるような整数kが存在するのkaはどこから現れたのですか？ ○ka-lb=1となるとax(0)+by(0)=1となる２つの整数x(0),y(0)が存在することが分かりません ○x(0)=k,y(0)=-lはどこから出たのですか？ ★(ii)⇒(i)の証明 aとbが共通の素因子pをもつと仮定すると、ax+byはいつもpの倍数になるので、ax+by=1となることはない。 ことについてよく分かりません。 例えば数字を使った表現を利用することができるのでしょうか？ 数字を使っても証明はできるでしょうか？ 沢山質問をしてすいません。
- ベストアンサー
- 数学・算数
- {ax+by|x,y∈Z}
aとbが互いに素とは限らないときは、{ax+by|x,y∈Z}は、aとbの最大公約数の倍数全体の集合になる。この定理の証明でわからない点があるので質問します。 これらの定理は、S={ax+by|x,y∈Z}とおくと集合Sが"差に関して閉じている"という性質をもつ。 (x_1,x_2,y_1,y_2∈Zのとき、(ax_1+by_1)-(ax_2+by_2)=a(x_1-x_2)+b(y_1-y_2)ここでx_1-x_2,y_1-y_2∈Zとなること)ので、ある正の整数dを用いてS={nd|n∈Z}(Sはdの倍数全体)と表されるのであるが、 Sの最初の定義から、a∈S(x=1,y=0とする)かつb∈S(x=0,y=1とする)であるから、aとbはdの倍数(dはa,bの公約数)であり、・・・(1) ここからがわからないところです。他方、ax_0+by_0=dとなる整数x_0,y_0が存在するのだから、a,bの任意の公約数はdの約数であるから・・・(2)、dはa,bの最大公約数というわけである。で証明は終わるのですが、 証明の大まかな流れは、(1)よりd≦(a,b) (a,b)は、aとｂの最大公約数、(2)よりd≧(a,b)よって、d=(a,b)だと思うのですが、ax_0+by_0=dをa'dx_0+b'dy_0=dとしてみたりしても、a,bの任意の公約数はdの約数であるから、というのがわかりません。どなたか、他方、ax_0+by_0=dとなる整数x_0,y_0が存在するのだから、a,bの任意の公約数はdの約数である。を説明してください。お願いします。
- ベストアンサー
- 数学・算数
- aとbをa=b=0でない２つの整数とする。a,bの公約数の集合の中の最
aとbをa=b=0でない２つの整数とする。a,bの公約数の集合の中の最大数dを、aとbの最大公約数といい、 d=(a,b)とかく 例えば(6,4)=2 このときar+bs＝(a,b)のような整数rとsが存在するというのを証明する。という問題です、教えてください。
- ベストアンサー
- 数学・算数
- ユークリッドの互除法
二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。
- ベストアンサー
- 数学・算数
- 最大公約数に関する問題です。
最大公約数に関する問題です。 『２つの整数6186と4709の最大公約数(6189,4709)を求めよ。また、この最大公約数に対して、(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』という問題です。最大公約数は1と求められたのですが、後半の『(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』は、X,Y の組み合わせが無数にあると思うのですが、どうしたら良いのでしょうか？宜しくお願い致します。
- ベストアンサー
- 数学・算数
質問者からの補足
ありがとうございます