未知数があるとき ユークリッド互助法 適用 方法

問題
8n+4と7n+1の最大公約数が5になるような100以下の自然数nはいくつあるか？


解答
ユークリッドの互助法を使う
8n+4と7n+1の最大公約数＝7n+1とn+3の最大公約数＝n+3と20の最大公約数
さらに………



という問題と解答なのですが、疑問があります
（以下　自然数～　を　自～　と表記します）



ユークリッドの互助法とは

自aと自bの最大公約数＝　
(自a＝自b×自c＋自d　∧　0≦自d＜自b ⇔ 自b＝～ ∧ 自d＝～)で定まる自dの値　と　自b　
の最大公約数

が成り立つという事実を使って2数の最大公約数を、より簡単な2数の最大公約数に還元し
もとめる方法ですよね？

そうなるとこの場合にどのように適用していいのかわかりません。



8n+4と7n+1の最大公約数＝7n+1とn+3の最大公約数　の部分は
8n+4＝(7n+1)×自c＋自d　∧　0≦自d＜7n+1 ⇔　　自ｃ＝1　∧　自ｄ＝n+3
で自dが一通りに定まるのがわかるのですが

7n+1とn+3の最大公約数＝n+3と20の最大公約数　の部分は
7n＋1＝(n+3)×自d+自d　∧　0≦自d＜n+3 ⇔　　自c＝　　∧　　自d＝
となるので
自ｃが7以下であることはわかりますが、自cは1.2.3.4.5.6のどれでもokですよね
そうすると自ｄが一通りに定まらず、どうやっていいのかわかりません

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2013/01/25 01:05

実のところ何をもって「ユークリッドの互除法」とするかは難しいところだけど....

本来は
a ≧ b のとき gcd(a, b) = gcd(a-b, b)
発展させると
任意の整数 r に対して gcd(a, b) = gcd(a-rb, b)

この回答へのお礼

回答ありがとうございます

『ユークリッドの互助法とは本来は
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つの自然数～～～」のようなわかりにくい表現が使われているのはなぜなのでしょうか？

お礼日時：2013/01/25 11:31

No.2 回答者： Tacosan 回答日時： 2013/01/25 15:18

すみません, どこで見たのかは覚えていません. もともとのユークリッドの「原論」に書いてあることを今の表記に直すと

a > b のとき gcd(a, b) = gcd(a-b, b)
になる, ってのが記憶にあるくらい.

今調べてみると, 中国の「九章算術」という書籍で全く同じことが書かれているようです... ということで見つかったところを適当に挙げておきます.

でこれを繰り返せば任意の整数 r に対し
gcd(a, b) = gcd(a-rb, b)
になるわけです.

今の形になっているのは, おそらく使い方によるものだと思います. 実際に互除法を使って最大公約数を計算しようとすると, 本来の形では引き算を繰り返す必要があります. でも, 今の形ならこの繰り返しを 1回の割算で済ませることができます. 参照に挙げた「九章算術」の例では, 最後に 42 と 7 が残ったところで今なら「42 は 7 で割り切れる」とすれば終わりですよね. つまり, 割算の余りを使った方がはるかに手間が少なくなるんです.

参考URL：http://mail2.nara-edu.ac.jp/~asait/pythagorean/s …

この回答へのお礼

回答ありがとうございました
とてもよくわかりました！

わざわざお調べいただいて、感謝です

お礼日時：2013/01/25 16:22