![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
ユーグリッド互除法を使って
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で質問しましょう!
似たような質問が見つかりました
- Excel(エクセル) マクロでコピーすると数式が表示される 1 2022/09/09 20:21
- Excel(エクセル) マクロだと数式が表示される 2 2022/09/10 14:48
- 数学 線形代数の正規直行系についての問題がわからないです。 1 2022/07/16 11:20
- Excel(エクセル) VBAで組み合わせ算出やCOUNTIFSの処理を高速化したいです。 4 2022/04/07 02:38
- 数学 a1,a2, a3をベクトル空間Vのベクトルとする。a1+a2,a2+a3,a3+a1が一次独立のと 2 2022/10/02 15:55
- Excel(エクセル) ユーザー定義について質問です。 2 2023/06/28 13:21
- 数学 行列の問題が分かりません。 3次正則行列Aの列ベクトル分割をA=(a1 a2 a3)とおくとき,次を 4 2022/06/23 08:34
- Visual Basic(VBA) 顧客ごとに違う点検案内を作成するマクロ 4 2022/09/16 05:34
- Excel(エクセル) SUMIF関数について 4 2023/06/14 13:13
- 数学 3次元実ベクトル空間において, 平面 P:x-y+z+1=0 と直線 L:2(x-1)=-y=-z 3 2022/10/29 14:39
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
電磁気学の流束の問題
-
この産み分けの計算でハズレの...
-
エクセル関数で源泉徴収額を計...
-
100以下の自然数のうち、次のよ...
-
エクセルで60進法計算の仕方...
-
3桁の自然数の中で、次の個数を...
-
経費率の計算方法を教えて下さい。
-
線型空間であることの証明
-
○+○=5
-
工事の共通仮設費率の計算がで...
-
歪度がある分布図でのz-soreを...
-
勝率50%の事象を100回やって勝...
-
問1.絶対値が3より小さい整数に...
-
就職率の求め方について
-
ユーグリッド互除法について
-
関数のパラメータ推定について
-
例5の青線の2/3はどこから求め...
-
IEEEの浮動小数点数の表現形式...
-
置き換えた理由と計算法
-
常用対数と自然対数の違い
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
100以下の自然数のうち、次のよ...
-
エクセルで60進法計算の仕方...
-
エクセル関数で源泉徴収額を計...
-
工事の共通仮設費率の計算がで...
-
3桁の自然数の中で、次の個数を...
-
エクセルでのシグマ計算
-
この産み分けの計算でハズレの...
-
経費率の計算方法を教えて下さい。
-
ラプラス変換の「s」とは?
-
Excelで勤務の過不足時間を計算...
-
問1.絶対値が3より小さい整数に...
-
勝率50%の事象を100回やって勝...
-
最小公倍数と最大公約数の求め...
-
A÷(B×C)=?
-
整式を整理する・計算する
-
関数電卓の使い方
-
数Aの「割り算のあまりの性質」...
-
公務員試験の問題
-
端数を習うのは小学何年生の頃...
-
高校時代電離平衡の計算に関し...
おすすめ情報