![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
ユーグリッド互除法を使って
a0 = 497, a1 = 284 とすると
497 = 284 + a2
284 = 213 + a3
213 = 71 * 3 + a4
ここでa4 == 0 となるので計算終了.
こういった手順ですが、
497 = 284 + a2
497 = 213 + a3
497 = 71 + 3 + a4
ここでa4 == 0となるので計算終了.
この手順でも答えがでてしまい以下のような結論がでました.
つまり,
a0 = a1 * q1 + a2
a1 = a2 * q2 + a3
....................................
とa0 → a1 を更新しなくても答えが上記のようにでてるのでa0 → a1のような手順を行わなくてもいいのではないか?ということです.
ですが、いろいろサイトを見てもa0 → a1のように各プロセスで更新を行っていて混乱しています.
ご教授ねがいます.
No.4ベストアンサー
- 回答日時:
No.1です。
No.3さん、間違いを指摘してくださってありがとうございます。
No.3で反例が示されてますから、やっぱりダメってことですね。
確かに
52=11 × 4 + 8
52= 8 × 6 + 4
52=13 × 4
で? みたいな感じですね。
きちんと考えると、
a0 = a1 * q1 + a2 で a0とa1の最大公約数rについて
b0*r=b1*r*q1+a2 と書けるので(b0,b1は互いに素)、a2=(b0-b1*q1)*r
ここで、a0=b0*r、a2(b0-b1*q1)*r なので、
a0とa2について最大公約数を考えると、b0と(b0-b1*q1)が 互いに素であれば、r で問題ないのですが、b0とq1に公約数があると、互いに素でなくなって、もっと大きな公約数がでてきてしまうところが問題ですね。
通常の互除法は、
a1とa2について最大公約数を考えるのですが、b0,b1は互いに素なので、b1と、b0-b1*q1 も互いに素で問題なし というわけだったんですね。
No.2
- 回答日時:
理屈は合っているようですが、a1よりもa0の方がものすごく大きい数の
場合は、やはりa2,a3,・・・と置き換えて数字を小さくしていった方が計算が楽だと思います。
No.1
- 回答日時:
497 = 284 + a2
497 = 213 + a3
497 = 71 + 3 + a4
つまり,
a0 = a1 * q1 + a2
a1 = a2 * q2 + a3
ですが、
497 = 284 + a2
497 = 213×2 + a3
497 = 71×7 + a4
つまり
a0 = a1 * q1 + a2
a0 = a2 * q2 + a3
本当は、こう書きたかった ということでいいですか?
おおざっぱにやると
a0 = a1 * q1 + a2 で a0とa1の公約数rについて
b0*r=b1*r*q1+a2 と書けるので、a2=(b0-b1*q1)*r なので、
rは、a2の約数でもあります。
(a0 ,a1) の公約数は、(a1 , a2)の公約数である
(a1 ,a2) の公約数は、(a2 , a3)の公約数である
を繰り返すのが、互除法ですが、ご質問の方法は、
(a0 ,a1) の公約数は、(a0 , a2)の公約数である
(a0 ,a2) の公約数は、(a0 , a3)の公約数である
をやっているわけで、実質的には同じことをやっているので、これでも問題はないと思います。
実用上は、数字が小さい方が計算がしやすいので、従来法のほうが好ましいかもしれません。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
この産み分けの計算でハズレの...
-
エクセルで60進法計算の仕方...
-
100以下の自然数のうち、次のよ...
-
ローン支払いにおける金利の計...
-
エクセル関数で源泉徴収額を計...
-
数学の試験問題についての質問...
-
工事の共通仮設費率の計算がで...
-
論理的思考が弱いです。考える...
-
文字を含む三角関数の定積分の...
-
10分の1は「10/1 それとも1/10...
-
1億x1億はいくらでしょうか?
-
50以下は“50”も入るのですか?
-
実績を積むという表現
-
5進法を10進法への直し方
-
dBm/HzからdBm/MHzへの単位変換
-
10進数の50を2進数で表すといく...
-
dBm→dBμV/mの換算について
-
フーリエ変換、逆変換の「2π」の...
-
敬語の使い方
-
味の表現で「どっきりする」っ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
エクセル関数で源泉徴収額を計...
-
100以下の自然数のうち、次のよ...
-
エクセルで60進法計算の仕方...
-
工事の共通仮設費率の計算がで...
-
この産み分けの計算でハズレの...
-
エクセルでのシグマ計算
-
ラプラス変換の「s」とは?
-
Excelで勤務の過不足時間を計算...
-
3桁の自然数の中で、次の個数を...
-
A÷(B×C)=?
-
経費率の計算方法を教えて下さい。
-
最小公倍数と最大公約数の求め...
-
中3の問題です
-
関数電卓の使い方
-
高校時代電離平衡の計算に関し...
-
公務員試験の問題
-
8進数から16進数への変換
-
整式を整理する・計算する
-
勝率50%の事象を100回やって勝...
-
電磁気学の流束の問題
おすすめ情報