• ベストアンサー

最大公約数

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

質問者が選んだベストアンサー

  • ベストアンサー
回答No.2

ユークリッドの互助法を使い、その逆算を行う 2020 + 1022 * (-2) = -24 1022 + 24 * (-42) = 14 24 + 14 * (-2) = -4 14 + 4 * (-3) = 2 4 + 2 * (-2) = 0 となるから最大公約数は 2。ここから逆算を行う 2 = 14 + 4 * (-3) = 14 + (14 * 2 - 24) * (-3) = 14 * (-5) + 24 * 3 = (1022 + 24 * (-42) ) * (-5) + 24 * 3 = 1022 * (-5) + 24 * 213 = 1022 * (-5) + (1022 * 2 - 2020) * 213 = 1022 * 421 + 2020 * (-213) となって、2 = 1022 * 421 + 2020 * (-213)　が一つの答えとなる

その他の回答 (1)

  • notnot
  • ベストアンサー率47% (4847/10258)
回答No.1

＞整数a=2020,b=1022の最大公約数dを求めよ。 最大公約数を求めるには、 方法1：それぞれ素因数分解して、共通部分を見る 方法2：ユークリッドの互除法を使う 普通は方法2ですが、2020 1022はどちらも簡単に素因数分解出来るので方法1も簡単です。 ＞また、d=ax+yb となるx,y€Zを1組求めたいです。 これは難しいですね。 プログラムを書いて探すと、x=-213 y=421 しかし、問題になっている以上、プログラムを書かないでも求められる方法はあるはずです。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 最大公約数

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

  • 最大公約数に関する問題です。

    最大公約数に関する問題です。 『２つの整数6186と4709の最大公約数(6189,4709)を求めよ。また、この最大公約数に対して、(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』という問題です。最大公約数は1と求められたのですが、後半の『(6189,4709) = 6186X + 4709YとなるX,Yを見つけよ。』は、X,Y の組み合わせが無数にあると思うのですが、どうしたら良いのでしょうか？宜しくお願い致します。

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

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

  • 最大公約数　と　互いに素　の関係

    自然数aと自然数bの最大公約数＝G　 ⇒　 自然数a＝整数x × G　 かつ 自然数b＝整数y × G　 かつ 整数xと整数yは互いに素 という定理について疑問があります 自然数a＝整数x × G　 かつ 自然数b＝整数y × G　 の部分は最大公約数の定義から明らかなのですが 整数xと整数yは互いに素 がなぜこう言えるのかわかりません 教えてください またこれは⇔はなりたつのでしょうか？ また自然数a　自然数b　ではなく　整数a　整数b　といった場合には成り立つのでしょうか？ ※ここでは「倍数」、「約数」とうは負の数まで考える定義を採用しています 例:6の約数＝-6,-3,-2,-1,1,2,3,6

  • {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の約数である。を説明してください。お願いします。

  • 最大公約数

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

  • 最大公約数について

    「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となり互いに素ではありませんよね？

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

    ある数　XとY　の最大公約数をnとすると X=an Y=bn このように表せますが このときにaとbはなぜ必ず素になるのでしょうか? あまり数学が得意ではないので 小学生レベルでも理解できるように説明していただけるとありがたいです。

  • ３数の最大公約数

    ２つの整数の最大公約数は分かるのですが、３つの整数の最大公約数は分かりません。 ご教授宜しくお願いします。

  • 最大公約数の問題

    数学の問題の解説を読んでいる途中で、 ＞ここで２つの正の整数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であることが証明できません。 誰か解決してくれませんか。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する