a = 19561222, b = 19560124 として A · a + B · b = GCD{a, b} となる整数 A, B を求めよ
問題の位が大きすぎて、計算が不安です よろしくお願いします
|
No.73939 - 2021/04/27(Tue) 15:54:20
| ☆ Re: ユークリッドの互除法 / ヨッシー | | | 19561222=19560124+1098 19560124=1098×17814+352 1098=352×3+42 352=42×8+16 42=16×2+10 16=10+6 10=6+4 6=4+2 4=2×2
ここまでが互除法
上からたどると、 1098=19561222−19560124 352=19560124−1098×17814 =19560124−(19561222−19560124)×17814 =19560124×17815−19561222×17814 42=1098−352×3 =(19561222−19560124)−(19560124×17815−19561222×17814)×3 =19561222×53443−19560124×53446 16=352−42×8 =(19560124×17815−19561222×17814)−(19561222×53443−19560124×53446)×8 =19560124×445383−19561222×445358 これを繰り返すんですかね。
|
No.73950 - 2021/04/27(Tue) 20:57:59 |
| ☆ Re: ユークリッドの互除法 / 関数電卓 | | | (参考まで) a=19,561,222=2・3^2・11・223・443=2・19・514,769 b=19,560,124=2^2・37・149・887 GCD(a,b)=2 よって, 3^2・11・223・443A+2・37・149・887B=1 の整数解 A,B を求める。
私なんぞは,とても筆算ではできません。
こちら にあるように, A=7,784,131=31・297・857 B=−7,784,170=−2・5・778,417 となるようですね。 高校生が使う問題集の問題とはとても思えない。出典は何ですか? ※ 失礼しました。(事後修正)
|
No.73951 - 2021/04/27(Tue) 21:25:33 |
| ☆ Re: ユークリッドの互除法 / らすかる | | | > 関数電卓さん a=19561222なので9780111→9780611ですね。 正しくはA=6056869, B=-6057209となるようです。
|
No.73953 - 2021/04/27(Tue) 23:27:16 |
| ☆ Re: ユークリッドの互除法 / IT | | | a=19561222, b=19560124 a-b=1098=2×3×3×61 aは2で割り切れ,3,61で割り切れない。 よって gcd(a,b)=2 c=a/2=9780611,d=b/2=9780062 とおき c,dについてユークリッドの互除法を使うと
9780611=9780062+549 9780062=549×17814+176 549=176×3+21 176=21×8+8 21=8×2+5 8=5+3 5=3+2 3=2+1
逆にたどると 1=3-2 =3-(5-3) =3×2-5 =(8-5)×2-5 =8×2-5×3 =8×2-(21-8×2)×3 =8×8-21×3 =(176-21×8)×8-21×3 =176×8-21×67 =176×8-(549-176×3)×67 =176(8+3×67)-549×67 =176×209-549×67 =(d-17814×549)×209-549×67 =209d-(17814×209+67)×549 =209d-3723193(c-d) =-3723193c+3723402d
A=-3723193,B=3723402 が答えの1つ よって 一般解は A=-3723193+dt,B=3723402-ct,tは整数。
(途中電卓の力を借りました。)
|
No.73958 - 2021/04/28(Wed) 00:21:27 |
| ☆ Re: ユークリッドの互除法 / takuna 高2 | | | みなさんご回答誠にありがとうございます! 学内テストで出された問題でしたが、制限時間内に解けずにいました… ありがとうございました
|
No.73978 - 2021/04/28(Wed) 19:41:15 |
|