• ベストアンサー

最大公約数、定理の証明

taropooの回答

  • taropoo
  • ベストアンサー率33% (34/103)
回答No.1

(a,b)の定義がないので定理と言われても何を主張した定理なのか分かりませんが、文脈から察するにa=2, b=3に対して12が     12 = 2*3 + 3*2 のようにa*r + b*sの形に表せるような整数r, sが存在するとき、     12 = (2,3) と表すと言う事でしょうか? それにしても左辺は一つの数を表していますが右辺は数の性質を表していて、これを等号で結んでしまって良いのでしょうか? しかし(a,b)の定義に関しては求められている証明にはあまり関係ないので置いておきましょう。     n|(a*r + b*s) ⇔ n|a かつ n|b を証明すれば良いんですよね?しかし証明は出来ません。なぜなら反例があるからです。 a=2, b=3, r=2, s=1, n=7 とおくと     n|(a*r + b*s) ⇔ 7|7 ⇔ true ですが     n|a ⇔ 7|2 ⇔ false     n|b ⇔ 7|3 ⇔ false です。 何か問題を読み違えていらっしゃいませんか?

noname#5824
質問者

補足

すみません、何の前置きもなく書いてしまいました。 (a,b) というのは、aとbの最大公約数です。 ものによっては gcd(a,b)とも書いてあります。

関連するQ&A

  • 最小公倍数 最大公約数 周辺の定理について

    自然数a=自然数aと自然数bの最大公約数×整数x 自然数b=自然数aと自然数bの最大公約数×整数y ⇒ 自然数aと自然数bの最小公倍数 =整数x × 整数y × 整数aと整数bの最大公約数 =整数x × 自然数b =整数y × 自然数a という定理の証明をおしえてください うんうん唸って考えてみたのですがどうしてもうまく証明できませんでした     

  • 最大公約数について

    「a,b,c,rが正の整数で、a=rb+cであるとき、a,bの最大公約数とb,cの最大公約数は一致することを証明せよ。」 という問題の解答の出だしが、 「aとbの最大公約数をm、bとcの最大公約数をnとおくと a=mA, b=mB(AとBは互いに素な整数) b=nB',c=nC(B'とCは互いに素な整数) と書ける」 となっているのですが、なぜこう書けるのかわかりません。 「a=mA, b=mB」「b=nB',c=nC」とかけるのはわかりますが、なぜAとB,B'とCが互いに素と言えるのかわかりません。 思いつく反例を上げると、a,b,cは異なる数とは問題文に書かれていないので、もしaとbが同じ数だとしたらA=Bとなり互いに素ではありませんよね?

  • 最大公約数 証明

    整数(環?)についての証明がわからないので質問します。 証明することは、 p,qを2整数(または数体Kにおけるxの整式)とし、式 pu+qv・・・(1)においてu及びvを整数(Kにおける整式)全体にわたって変ずるものとする。かくして得る整数(整式)の中の最小正の整数(xについての最低次の整式)をdとし、d=pu0+qv0・・・(2)とする。然るときdはp,qの最大公約数である。 です。証明は以下のように書いてあります。 実際d'がp,qの公約数ならば、(2)からd'はdの約数である。他方dはu,vのいかんを問わず常に(1)を割り切っている。何となれば(1)をdで除した剰余をr(rは0に等しくない) とすれば、 pu+qv=ad+r=a(pu0+qv0)+r つまりp(u-au0)+q(v-av0)=r ところでrはdより小なる正整数(dより低次の整式)であるから、上の関係はdが(1)が最小(最低次)であるという仮定に矛盾する。故にu,vのいかんを問わずdは(1)を整除する。今u=1,v=0とおけば(1)はpとなり,u=0,v=1とおけば(1)はqとなるから,dはpをもqをも割り切る。それゆえdはp,qの最大公約数である。 自分は、2*1+3*2=8などから、8は2と3の最大公約数ではないと思い。何かp,u,q,v に条件があるのではと考えましたが、整数という条件しか探せませんでした。 剰余をrとした後の計算と、剰余rを仮定すると矛盾するからr=0ということ、ぐらいしかわかりません。ヒントでもよいので教えてくださいお願いします。

  • 公約数で

    解答をみていてちょっと分らない部分があったのでご質問させていただきます。(表記しづらいので、数列Anで第n+1項を A(n+1)と表します)分らないのは、帰納法での証明の一部分です。また【 】の中は前問で証明されていたり条件として成り立っているとします。 【A(n+1) = An+Bn , B(n+1) = An … (1)   An,Bnは自然数で互いに素 … (2) 】 (1)、(2)からA(n+1)とB(n+1)は自然数である。 ここでA(n+1)とB(n+1)が互いに素でないとすると、 A(n+1)とB(n+1)は1より大きい公約数rを持つ。 ________________________(ここまでは分ります) (1)より Bn = A(n+1)-An であるからrはBnの約数でもありrはAnとBn の1より大きい公約数である。 ______________________ この部分が分りません^^;どうしてrはBnの約数でもありrはAnとBnの1より大きい公約数であるのでしょうか?分る方お願いします。

  • 最大公約数

    2つの正の整数をA、Bとし、AをBで割ったときの商をQ、あまりをRとすれば、A、Bの最大公約数はB、Rの最大公約数に一致するのはなぜですか?

  • 最大公約数の問題

    数学の問題の解説を読んでいる途中で、 >ここで2つの正の整数x,yの最大公約数を[x,y]とあらわすことにすると(3)( p_n = p_(n-1) + p_(n-2) )により、 > [p_(n-1),p_n]=[p_(n-2),p_(n-1)] (n=2,3,...). という部分が出てきたんですが、理屈がわかりません。 a=b+cとして、  [b,a]=[c,b] である。 ということに書き換えられると思い、a=ma',b=mb'=nb'',c=nc'とおいていろいろ考えたのですがどうもうまくm=nであることが証明できません。 誰か解決してくれませんか。

  • ユークリッドの互除法で最大公約数を求める

    <問題> n^2+2n+1とn+3の最大公約数になりうる値をすべて求めよ <解答> 整数a,bに対してa,bの最大公約数をg(a,b)とあらわす。 g(n^2+2n+1,n+3)=g(n+3,4) 4の正の約数は1,2,4であるから、g(n+3,4)として考えうるのも1,2,4である。 例えば、 n+3=5 すなわちn=2のとき、g(5,4)=1 n+3=6 ・・・ g(6,4)=2 n+3=8 ・・・ g(8,4)=4 となり、最大公約数として可能な数は1,2,4の3つの自然数である。 <質問> 「g(n+3,4)として考えうるのも1,2,4である。」 が必要条件であることはわかります。 その後、解答でなにがしたいのかよくわかりません。 なぜ例示しただけで「最大公約数として可能な数は1,2,4の3つの自然数である。」といえるのでしょうか? よろしくお願いします。 <思ったこと> 必要十分条件なら「g(n+3,4)として考えうるのも1,2,4である」場合、「4の正の約数は1,2,4である」であることを示すことになると思います。

  • 最大公約数

    整数a=2020,b=1022の最大公約数dを求めよ。また、d=ax+yb となるx,y€Zを1組求めたいです。

  • 最大公約数

    最大公約数をだしたいとき、整数なら因数分解すればいいのは分かるんですが例えばax+b,cx+dの最大公約数を求めるようなときはどうすればよいのですか?

  • 最大公約数について教えてください!

    二つの整数m、n(m>n)の最大公約数をgとすると、mをnで割ったあまりとnとの最大公約数もgであることを証明せよ ただしm、nが互いに素であるとき、nとm-nも互いに素であることを使ってもよい 解説お願いします!