Weekend Mathematics／問題／問題92

９２．最大公約数の求め方　　　*問題文の一部訂正(8/1、0:30）

１以上の２つの整数ｍ、ｎ（ただし、ｎはｍより大きい）について次のような操作を行う。
ｎをｍで割ったときの商を書いておいて、余りがあれば今度ｍをその余りで割って、余りがある限りくり返す。

例えば、ｍ＝７、ｎ＝１０のときはこうなる。
　１０÷７＝１、余りは３
　７÷３＝２、余りは１
　３÷１＝３、余りがない、操作終了

紙に書いたのは「１−２−３」である。そこで７と１０の関係は、「１−２−３」であるという。 関係に出てくる数の個数（７と１０の時は３）を関係の長さという。

例えば、３と５の関係は「１−１−２」、その長さは３。 ４と６の関係は「１−２」、その長さは２である。

(1)　関係が「１−３−１−１−２」となる整数の組を、１以上１００以下の範囲で すべて答えなさい。

(2)　１以上１００以下の範囲で「関係の長さ」が最も長くなるような整数の組を調べたところ、 長さが９である組が最も長く、しかも１組しかないことがわかりました。その１組を答えなさい。

解答・その1

（ペンネ−ム：kiyo）

解答

(1)
23,18
46,36
69,54
92,72

(2)
89,55 (フィボナッチ数)

解答・その2

（ペンネ−ム：Mr.X）

(1)の答え
最大公約数をｄとする。
ｄ、２ｄ、１・２ｄ＋ｄ＝３ｄ、１・３ｄ＋２ｄ＝５ｄ、
３・５ｄ＋３ｄ＝１８ｄ、１・１８ｄ＋５ｄ＝２３ｄ
と並べて該当する組は（１８ｄ、２３ｄ）
　　　　答え（１８ｄ、２３ｄ）（ただしｄ＝１，２，３，４）

(２)の答え
１−１−１−１−１−１−１−１−２
最大公約数をｄとする。
ｄ、２ｄ、３ｄ、５ｄ、８ｄ、１３ｄ、２１ｄ、３４ｄ、５５ｄ、８９ｄ
　　　　答え（５５、８９）

解答・その3

（ペンネ−ム：巷の夢）

(1)各段階での計算による商は題意より1,3,1,1及び2である。 因って各段階での余りをa,b,c,及びdとすると、

　　　　n＝m+ a
　　　　m＝3a+ b
　　　　a＝b+ c
　　　　b＝c+ d
　　　　c＝2d　　　が成立する。

これより順次代入を繰り返し、全ての数をｄで表すと、

c＝2d , b＝3d , a＝5d, m＝18d, n＝23d となる。

ここで、ｍ,ｎ が１以上100以下の整数であることに注意すると、 d＝1,2,3,4のみ題意を満たすことが分かる。これより求めるものを以下の一覧表にまとめる。

d	m	n
1	18	23
2	36	46
3	54	69
4	72	92

(2)求める一組をm,nとして前記と同様の考え方をしてみると

　　　　n＝ｘm+ a
　　　　m＝ｙa+ b
　　　　a＝ｚb+ c
　　　　b＝Ac+ d
　　　　c＝Bd+ e
　　　　d＝Ce+ f
　　　　e＝Df+ g
　　　　f＝Eg+ h
　　　　g＝Fh　　　となる。

ところで、m,nは１以上100以下の整数であり、９段階もの計算を繰り返すので、全ての数をｈで表す際、 この条件を満たすには商は出来るだけ小さな１であれば良いことが分かる。 とは云うものの最後のFのみは１ではg＝hとなりこの計算段階が必要なくなるため、 １以外の最小整数である２となる。
因って、ｍ= 55h, n=89hとなり、ｈに１を代入し、求める一組は（55,89）となる。

解答・その4

（ペンネ−ム：yokodon）

とにかく、数値実験して偶然見つけたというだけの代物です。
２数の関係を調べる過程を逆に辿っていけば、与えられた関係からその関係を満た す２数を見つけることが出来そうです。

（1）まず、

　　　　23 ÷ 18 ＝ 1 余り 5
　　　　18 ÷ 5 ＝ 3 余り 3
　　　　5 ÷ 3 ＝ 1 余り 2
　　　　3 ÷ 2 ＝ 1 余り 1
　　　　2 ÷ 1 ＝ 2 余り 0

・・・から、(23, 18) という組は題意を満たします。
また、(23×n, 18×n) (n ＝ 1, 2, 3,...) も題意を満たします。
問題文の要求は 1 から 100 までの整数の中から題意を満たす数字の組を求めよと いうことなので、n ＝ 4 の場合までが適します。以上から、求める数字の組は、(23 , 18), (46, 36), (69, 54), (92, 72) の４つです。

（2）条件を満たす「関係の長さが９となる２数の関係」は

　　　　“1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 2”

・・・です。（1）の場合と同様に実験してみると、1 以上 100 以下の整数の２組で 条件を満たすのは、(89, 55) の１組しかありませんでした。と言うわけで、この組 が答えです。
なお、“1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 3”の場合で、組の２数が最小となる のは (113, 76) でした。

適当なプログラムを書けば、アッという間に解決しそうな問題のような気がします。

解答・その5

（ペンネ−ム：杖のおじさん）

�@１８と２３　　４６と３６　　６９と５４　　９６と７２
�A５５と８９

（１）１３１１２なので次の式が成り立ちます。
あまりをXとすると、最後割り切れて２となりますので

　　　　２X/X=２
　　　　３X/2X=1　　あまり　　　X
　　　　５X/3X=1　　あまり　　　２X
　　　　１８X/5X=3　　あまり　　３X
　　　　２３X/１８X=1　あまり　　５X

となります。
２３X/１８XのXに数字を入れて見ましょう

　　　　１の時　　２３　　と　１８
　　　　２の時　　４６　　と　３６
　　　　３の時　　６９　　と　５４
　　　　４の時　　９２　　と　７２
　　　　５の時　１１６　　と　９０

１００以下の数字なので４の時の組み合わせまでです。

（２）一番多い組み合わせなので１から逆算いたします。
１　２　３　５　８　１３　２１　３４　５５　８９　144 233 377 610…
１００以下なので５５　と　８９　になります、そして９組になります。

解答２については ＣＡＳＩＯ　ＦＸ−８７０Ｐ　のBASICプログラムで作ってみました。

１０　DIM　B(５０)
２０　INPUT“１０ケタマデノスウジ”；A
３０　ＦＯＲ　Ｘ＝１　ＴＯ　５０
４０　ＩＦ　Ｘ＝１　ＴＨＥＮ　Ｂ（１）＝１
５０　ＩＦ　Ｘ＝２　ＴＨＥＮ　Ｂ（２）＝２
６０　ＩＦ　Ｘ＞２　ＴＨＥＮ　Ｂ（Ｘ）＝Ｂ（Ｘ−１）＋Ｂ（Ｘ−２）
７０　ＩＦ　Ｂ（Ｘ）＞Ａ　ＴＨＥＮ　１００
８０　ＰＲＩＮＴ　Ｂ（Ｘ）；
９０　ＮＥＸＴ　Ｘ
１００　ＰＲＩＮＴ　Ｘ−２；“クミ”；
１１０　ＰＲＩＮＴ　Ｂ（Ｘ−２）；“ト”；Ｂ（Ｘ−１）；“デス”
１２０　ＧＯＴＯ　２０

上のプログラムを実行して見てください。１０ケタノスウジ？と聞いてきますので １００と入力してください！次のように表示されます。

　　１　２　３　５　８　１３　２１　３４　５５　８９　９　クミ　５５ト８９　デス

いろいろ数字を入れて見てください！ポケコンなので１０桁までの数字までです。

解答・その6

（ペンネ−ム：jiangmin）

(1)
　2つの1以上の整数m, nについて、nをmで割ったときの商と余は、

　　　　n = 商 * m + 余

と表せる。ここで、余を順にl, k, j, …と置いていって問題のように繰返すと、 商は問題に与えられているので、

　　　　n = 1 * m + l
　　　　m = 3 * l + k
　　　　l = 1 * k + j
　　　　k = 1 * j + i
　　　　j = 2 * i

と表せる。これを順に代入して解くと、

　　　　m = 18 * i
　　　　n = 23 * i

となる。これのiに1以上の整数を順に代入してnが100以下になる組合せは以下のとおり。

　　　　m=18, n=23
　　　　m=36, n=46
　　　　m=54, n=69
　　　　m=72, n=92

perl script
use integer;
@quotlist = (1, 3, 1, 1, 2);
@num = (1);
$cnt = 0;
foreach $quot (reverse @quotlist) {
  $num[$cnt + 1] = $num[$cnt] * $quot + ($cnt ? $num[$cnt - 1] : 0);
  ++$cnt;
}

$m = $num[$#num - 1];
$n = $num[$#num];

while ($n <= 100) {
  printf "m=%d, n=%d\n", $m, $n;
  $m += $num[$#num - 1];
  $n += $num[$#num];
}

(2)
　商の値が不明で9つあるので順にr, s, t, …と置いて(1)と同様に繰返すと、

　　　　n = r * m + l
　　　　m = s * l + k
　　　　l = t * k + j
　　　　k = u * j + i
　　　　j = v * i + h
　　　　i = w * h + g
　　　　h = x * g + f
　　　　g = y * f + e
　　　　f = z * e

と表せる。これをr〜zを左辺に整理して逆順に書くと、

　　　　z = f / e
　　　　y = (g - e) / f
　　　　x = (h - f) / g
　　　　w = (i - g) / h
　　　　v = (j - h) / i
　　　　u = (k - i) / j
　　　　t = (l - j) / k
　　　　s = (m - k) / l
　　　　r = (n - l) / m

となる。1組しかないのだから最小の場合を考えるだけでよい。fは1ではないから、

　　　　e = 1, f = 2 ⇒ z = 2
　　　　r〜yはすべて1

と仮定してみると、

　　　　g - e = f
　　　　h - f = g
　　　　i - g = h
　　　　j - h = i
　　　　k - i = j
　　　　l - j = k
　　　　m - k = l
　　　　n - l = m

となり、順に解くと、

　　　　m = 55
　　　　n = 89

となる。nが100以下なのでOK。

解答・その7

（ペンネ−ム：浜田　明巳）

今月の解答を送ります．いつものようにエクセルのマクロで解きました．

問題１．次の４通り．
　　　　(18,23):1-3-1-1-2
　　　　(36,46):1-3-1-1-2
　　　　(54,69):1-3-1-1-2
　　　　(72,92):1-3-1-1-2

問題２．次の１通り．
　　　　(55,89):1-1-1-1-1-1-1-1-2

Option Explicit
Sub Macro1()
    Sheets("Sheet1").Select
    Cells(1, 1).Value = 0 '問題1の答の数
    Cells(1, 4).Value = 0 '問題2の答の数
    Range("A1").Select
    '
    Dim n As Integer
    Dim m As Integer
    Dim p As Integer
    Dim q As Integer
    Dim r As Integer
    Dim shou(9) As Integer
    For n = 2 To 100
      For m = 1 To n - 1
        p = n
        q = m
        shou(0) = 0 '長さ
        Do
          shou(0) = shou(0) + 1
          shou(shou(0)) = p \ q
          r = p Mod q
          If r > 0 Then
            p = q
            q = r
          End If
        Loop While r > 0
        If shou(0) = 5 And shou(1) = 1 And shou(2) = 3 And shou(3) = 1 And shou(4) = 1 And shou(5) = 2 Then
          Cells(1, 1).Value = Cells(1, 1).Value + 1
          Cells(Cells(1, 1).Value + 1, 1).Value = kotae(m, n, shou())
        ElseIf shou(0) >= 9 Then
          Cells(1, 4).Value = Cells(1, 4).Value + 1
          Cells(Cells(1, 4).Value + 1, 4).Value = kotae(m, n, shou())
        End If
      Next m
    Next n
End Sub
Private Function strr(ByVal n As Integer) As String
    strr = Right(Str(n), Len(Str(n)) - 1)
End Function
Private Function kotae(ByVal m As Integer, ByVal n As Integer, ByRef shou() As Integer) As String
    Dim j As Integer
    kotae = "(" + strr(m) + "," + strr(n) + "):"
    For j = 1 To shou(0)
      If j > 1 Then
        kotae = kotae + "-"
      End If
      kotae = kotae + strr(shou(j))
    Next j
End Function

解答・その8

（ペンネ−ム：teki）

（１）　１８と２３、３６と４６、５４と６９、９２と７２

（２）　５５と８９

解法はいうまでもなく、フィボナッチ数列を利用したものです。
ただし、（１）は単純に足すのではなく、与えられた数字をかけて足していくものです。
つまり、１８と２３の例で言うと、
１、１×２＝２、１+１×２＝３、２+３＝５、３+５×３＝１８、５+１８＝２３
で最後の２数が答えです。
最初の数が１〜４の時が上記の４組となります。
なお、最初の数が５以上は１００を超えてしまうので不適となります。

解答・その9

（ペンネ−ム：三角定規）

(1) 2数をn，mとすると，題意より

　　　n ÷ m ＝1　　　　　　　　あまり　n−m　　……�@
　　　m ÷( n− m)＝3　　　　あまり　4m−3n　……�A
　　( n− m)÷(4m−3n)＝1　あまり　4n−5m　……�B
　　(4m−3n)÷(4n−5m)＝1　あまり　9m−7n　……�C
　　(4n−5m)÷(9m−7n)＝2　あまり　0 ……�D

�Dより 4n−5m＝2(9m−7n)
　　　∴　18n＝23m　……�E
�Eを満たす100以下の自然数n，mは
　　　(n，m)＝(23，18)，(46，36)，(69，48)，(92，72) ……［答］

(2) 関係の長さが長くなるためには割り算の商は大きくない方がよいだろうと予想して， 商を最後以外1，最後は2と仮定してみる。(1)と同様にして n＝89，m＝55　　このとき，

　　　89÷55＝1　あまり 34
　　　55÷34＝1　あまり 21
　　　34÷21＝1　あまり 13
　　　21÷13＝1　あまり 8
　　　13÷ 8＝1　あまり 5
　　　8÷5＝1　　あまり 3
　　　5÷3＝1　　あまり 2
　　　3÷2＝1　　あまり 1
　　　2÷1＝2　　あまり 0

となり一応答は見つかりましたが，これは数学の答案ではないですね。
ところで，あまりの数字を逆から眺めるとフィボナッチ数になっているのですね。

解答・その10

（ペンネ−ム：Toru）

　題意のような計算をくり返せば、余りは自然数の単調減少列であるので、最後には 必ず０になる。そこで最後の式から逆順に数えてk(k≧3)番目の式を

　　　　p(k)=q(k)a(k)+r(k) (0≦r(k)≦q(k)-1)

とすると、（k−１）番目の式は

　　　　q(k)=r(k)a(k-1)+r(k-1)

（k―２）番目の式は

　　　　r(k)=r(k-1)a(k-2)+r(k-2)

より

　　　　q(k) = p(k-1) ,r(k)=p(k-2)

が成り立つ。これをk番目の式に代入すると

　　　　p(k)=a(k)p(k-1)+p(k-2) 、

ここで

　　　　p(-1)=r(1)=0,p(0)=q(1)

とすれば上記式はk≧1で成り立つ。

1) a(1)=2,a(2)=1,a(3)=1,a(4)=3,a(5)=1
上記から順に計算して、

　　　　p(1)=2q(1),p(2)=p(1)+p(0)=3q(1),p(3)=p(2)+p(1)=5q(1),
　　　　p(4)=3p(3)+p(2)=18q(1),p(5)=p(4)+p(3)=18q(1)+5q(1)=23q(1)

p(5) ≦100より q(1)=1,2,3,4が題意を満たし
p(5)=23,46,69,92 それぞれに対応するq(5)=p(4)=18,36,54,72　

　　　　答え(m,n)=(18,23),(36,46),(54,69),(72,92)

2) p(k)=a(k)p(k-1)+p(k-2)はa(k)とp(0)=q(1)で決定するが、
a(1)≧2,a(k)≧1( k≧2) より a(1)=2,a(k)=1(k≧2),p(0)=1時、
最小となり、k=1,2,3----に対して
p(k)=2,3,5,8,13,21,34,55,89,144---- これはp(9)=89で題意を満た し(m,n)=(55,89)、また長さ１０以上は不能であることが分かる。

p(9) ≦100を満たすものが他にないことを示す。
a(k)（k≦9）のいずれかの項、あるいはp(0)を増加させれば、p(9)も増加するので、 a(k)を固定して、p(0)=2とするとp(k)=4,6,10,16,26,42,68,110,178で不適。
次にp(0)=1としてa(k)を変化させてみると
p(0)=1, a(1)=3,a(k)=1 ( k≧2) の時p(k)=3,4,7,11,18,29,47,76,123で不適
p(0)=1,a(1)=2, a(k)=2：k=l,2≦l≦9のどれかひとつのみ、a(k)=1：それ以外
a(l)=2となるl(l=2,3,---9)それぞれに対してp(k)は

　　　　l=2：2,5,7,12,19,31,50,81,131
　　　　l=3：2,3,8,11,19,30,49,79,128
　　　　l=4：2,3,5,13,18,31,49,80,129
　　　　l=5：2,3,5,8,21,29,50,79,129
　　　　l=6：2,3,5,8,13,34,47,81,128
　　　　l=7：2,3,5,8,13,21,55,76,131
　　　　l=8：2,3,5,8,13,21,34,89,123
　　　　l=9：2,3,5,8,13,21,34,55,144

いずれもp(9)>100で不適
と題意を満たす(m,n)が１組しかないことが確認された。

「ユークリッドの互除法」の問題ですね。何となく計算していると答は分かるのです が、解答として分かりやすく書くとなると、なかなか難しい。結局しらみつぶしのよ うなことになってしまいました。あたりまえですが、フィボナッチ数列が出てきたり して、整数の問題はなんとも美しいですね。ところで、これも小学生が解くのですか？ 「ユークリッドの互除法」なんて高校でも習いましたっけ？

解答・その11

（ペンネ−ム：夜ふかしのつらいおじさん）

この方法をユークリッドの互除法といいます。 最大公約数は０でない最後の余りです。この例の場合（ｍ＝７、ｎ＝１０）、１が最大公約数です。

この例、ｍ＝７、ｎ＝１０のときの

１０÷７＝１、余りは３ ７÷３＝２、余りは１ ３÷１＝３、余りが０　→　操作終了

という一連の計算を図１のような形式を繰り返して、図２のように表すことにします。

図１

商 ｎ ： ｍ ：余り

図２

１　　　２　　　３ １０：　７　：　３　：　１　：　０

つまり、上の行の「ｐ−ｑ−ｒ・・・」が、ｂとａの関係です。
下の行は、ａ＞ｂ＞ｃ＞ｄ＞ｅ の大小関係があります。
また、下の行の最後は必ず０になります。

図３

ｐ ｑ ｒ ・・・ ａ ：ｂ ：ｃ ：ｄ ：ｅ ： ・・・ ：０

　　ａ＝ｐｂ＋ｃ　・・・　�@
　　ｂ＝ｑｃ＋ｄ ・・・　�A
　　ｃ＝ｒｄ＋ｅ ・・・　�B
�@に�A・�Bを代入し、�Aに�Bを代入すると、
　　ａ＝ｐ(ｑｃ＋ｄ)＋ｃ＝(ｐｑ＋１)ｃ＋ｐｄ＝(ｐｑ＋１)(ｒｄ＋ｅ)＋ｐｄ
　　　＝(ｐｑｒ＋ｐ＋ｒ)ｄ＋(ｐｑ＋１)ｅ　・・・　�C
　　ｂ＝ｑ(ｒｄ＋ｅ)＋ｄ
　　　＝(ｑｒ＋１)ｄ＋ｑｅ　・・・・・・・・・・　�D
のようになります。ｅを最後の余りとすれば０なので、２数は、
　　ａ＝(ｐｑｒ＋ｐ＋ｒ)ｄ
ｂ＝(ｑｒ＋１)ｄ
のように、関係に現れる数と０でない最後の余り（最大公約数）で表せます。

尚、最後の商は１ではありません。
この例で ｅ＝０ とすると、ｃ＝ｒｄ となります。
最後の商 ｒ＝１ とすると、ｃ＝ｄ となり、ｃ＞ｄ に反します。

（１）の問の関係が「１−３−１−１−２」となる場合、次の関係を満たす２数（ｂ，ａ）を求めればよいわけです。

１ ３ １ １ ２ ａ ：ｂ ：ｃ ：ｄ ：ｅ ：ｆ ：０

ａ＝２３ｆ
ｂ＝１８ｆ

ｆ	１	２	３	４	５	・・・
ｂ	１８	３６	５４	７２	９０	・・・
ａ	２３	４６	６９	９２	１１５	・・・

なので、（１８，２３）、（３６，４６）、（５４，６９）、（７２，９２）の４組です。

（２）この条件で「関係の長さ」を長くするには、関係に出てくる数を小さくします。
具体的には「１−１−１−１−１−１−１−１−２」とします。
すると、

１ １ １ １ １ １ １ １ ２ ａ ：ｂ ：ｃ ：ｄ ：ｅ ：ｆ ：ｇ ：ｈ ：ｉ ：ｊ ：０

ａ＝８９ｊ
ｂ＝５５ｊ

この場合、ｊ＝１ のときが解であるのは、明らかです。
（５５，８９）が答えです。

◎おまけ。
この条件で「関係の長さ」が最も長くなる場合、関係の数は最後以外全部「１」です。
すると、最後以外は、ａ＝ｂ＋ｃ，ｂ＝ｃ＋ｄ のような関係式がなりたちます。
これは、フィボナッチ数列です。
小さい順に並べてみると、
　　｛ｊ，ｉ，ｈ，ｇ，ｆ，　ｅ，　ｄ，　ｃ，　ｂ，　ａ｝
　＝｛１，２，３，５，８，１３，２１，３４，５５，８９｝
となっています。

解答・その12

（ペンネ−ム：kirkland）

先生	「長くなりそうなので、余計なことを一切言わないこと！まず、（１）の関係を整理してみなさい。」
Ａ君	「僕がしゃべらなきゃ始まらないと思うんですけど。」
先生	「余計なことを言わない！！！」
Ａ君	「……。 ｎ÷ｍ＝１．．．ア ｍ÷ア＝３．．．イ ア÷イ＝１．．．ウ イ÷ウ＝１．．．エ ウ÷エ＝２．．．０」
先生	「そのままだと扱いにくいので、　割られる数＝割る数×商＋余り　という感じで整理しなさい。 逆から考えていった方がいいよ。」
Ａ君	「ウ＝エ×２ イ＝ウ×１＋エ ア＝イ×１＋ウ ｍ＝ア×３＋イ ｎ＝ｍ×１＋ア」
先生	「ウはエの２倍だ。イはエの何倍？」
Ａ君	「２×１＋１＝３倍」
先生	「アは？」
Ａ君	「３×１＋２＝５倍」
先生	「ｍは？」
Ａ君	「５×３＋３＝18倍」
先生	「ｎは？」
Ａ君	「18×１＋５＝23倍」
先生	「というわけで、ｍ：ｎ＝18：23だね。」
Ａ君	「(ｍ，ｎ)＝(18，23)、(36，46)、(54，69)、(72，92)」
先生	「その通り。ここで、図を用いてみよう。例えば、ウ＝エ×２を正方形を用いて図示すると、 【図１】のようになる。 これに　イ＝ウ×１＋エも付け加えるとどうなる？」
Ａ君	「【図２】」
先生	「その通り、この調子で残りも描き加えてみなさい。」
Ａ君	「【図３】」
先生	「えらくデカイ図になったねぇ。正方形の中に書いてある数字は、一辺の長さを表してるんだね。 いずれにせよ、ｍ：ｎ＝18：23だね。では、（２）だ。」
Ａ君	「ｎ÷ｍ＝？．．．ア ｍ÷ア＝？．．．イ ア÷イ＝？．．．ウ イ÷ウ＝？．．．エ ウ÷エ＝？．．．オ エ÷オ＝？．．．カ オ÷カ＝？．．．キ カ÷キ＝？．．．ク キ÷ク＝？．．．０」
先生	「商が全く分からないけどね、商を大きくすると、クに対してｍやｎが大きくなってしまうので、なるべく商を小さく する方向で考えてみよう。というわけで、商は１なんだけど、キ÷クの商は１じゃダメだよ。」
Ａ君	「２」
先生	「では、先ほどと同様に図示しなさい。」
Ａ君	「【図４】」

先生	「困った図だねぇ。細かいところが読めないじゃないか！まぁ、ｍ：ｎ＝55：89になるね。」
Ａ君	「(ｍ，ｎ)＝(55，89)」
先生	「そうそう。いやぁ、君がおとなしいと順調にいくね！来月からもこんな感じでいこうではないか！」
Ａ君	「……。」 （来月は、しゃべりまくってやる！と心に誓うＡ君であった。）

正解者

teki	巷の夢	浜田　明巳
Toru	Mr.X	杖のおじさん
kiyo	夜ふかしのつらいおじさん	jiangmin
yokodon	三角定規	kirkland

ここで説明されていることが、「ユークリッドの互除法」だということを知らなくても、 問題文の指示がきちんと理解できればいいということで、中学入試の問題に なっているということでしょうか。
問題の答えは、「ユークリッドの互除法」を逆にたどっていくと答えを求めることができます。 特に(2)では、「関係の長さ」をできるだけ大きくしたいという事情から商を１としていきます。 そうしますと、皆さんお気づきにように「フィボナッチ数列」が現れてきます。 こんなところにも顔を出すのですね！
更に、kirklandさんの指導を素直に受けた A君はこれを長方形で表してくれました。おもしろいですね。 言い換えれば、ユークリッドの互除法というのは、 ２つの整数比を持つ長方形から、できるだけ大きい正方形を 順次切り出していって、 最後に残った一番小さい正方形の１辺が、 （運が悪くても１辺１の正方形で必ず終わる） 最大公約数だということですよね。

E-mail 戻る top