- ベストアンサー
※ ChatGPTを利用し、要約された質問です（原文：未知数があるとき ユークリッド互助法 適用 方法）
未知数があるとき ユークリッド互助法 適用 方法
このQ&Aのポイント
- 8n+4と7n+1の最大公約数が5になるような100以下の自然数nはいくつあるか？
- ユークリッドの互助法を使う
- 8n+4と7n+1の最大公約数＝7n+1とn+3の最大公約数＝n+3と20の最大公約数
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
実のところ何をもって「ユークリッドの互除法」とするかは難しいところだけど.... 本来は a ≧ b のとき gcd(a, b) = gcd(a-b, b) 発展させると 任意の整数 r に対して gcd(a, b) = gcd(a-rb, b)
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
回答No.2
すみません, どこで見たのかは覚えていません. もともとのユークリッドの「原論」に書いてあることを今の表記に直すと a > b のとき gcd(a, b) = gcd(a-b, b) になる, ってのが記憶にあるくらい. 今調べてみると, 中国の「九章算術」という書籍で全く同じことが書かれているようです... ということで見つかったところを適当に挙げておきます. でこれを繰り返せば任意の整数 r に対し gcd(a, b) = gcd(a-rb, b) になるわけです. 今の形になっているのは, おそらく使い方によるものだと思います. 実際に互除法を使って最大公約数を計算しようとすると, 本来の形では引き算を繰り返す必要があります. でも, 今の形ならこの繰り返しを 1回の割算で済ませることができます. 参照に挙げた「九章算術」の例では, 最後に 42 と 7 が残ったところで今なら「42 は 7 で割り切れる」とすれば終わりですよね. つまり, 割算の余りを使った方がはるかに手間が少なくなるんです.
質問者
お礼
回答ありがとうございました とてもよくわかりました！ わざわざお調べいただいて、感謝です
お礼
回答ありがとうございます 『ユークリッドの互助法とは本来は a ≧ b のとき gcd(a, b) = gcd(a-b, b) 発展させると 任意の整数 r に対して gcd(a, b) = gcd(a-rb, b)』 であるとのことですが、これは一般的な表現とは違いますよね？ 私が調べた限りだと、どの本やサイトも 「2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。」 という表現をしていました 他の本やサイトの表現よりもTacosanさんの回答のほうが、はるかに簡潔でわかり易いです Tacosanさんはこの表現をどこでお読みになったのでしょうか？ また一般的に「2つの自然数～～～」のようなわかりにくい表現が使われているのはなぜなのでしょうか？