Euclidの互除法                       戻る

 数学セミナー(2002年6月号)で、「因数分解のひろがり」を主テーマに特集が組まれた。
いろいろな話題が取り上げられ、楽しく拝読することができた。その中で、ユークリッドの互
除法について、特に関心をもったので、ここで整理しておきたい。

 ユークリッドは、古代アレキサンドリアの数学者である。ユークリッドの互除法は、共通因
数を求める最速のアルゴリズムとして、現代において暗号理論(公開鍵方式)などに多用さ
れており、ユークリッドの偉大さに、ただ敬服するばかりである。

 ここで、少しばかり予備知識を確認しておきたい。以下で数はすべて0以上の整数とする。

 数 a、b(bは0でない)に対して、

           a=bQ+R  (0≦R<b)

となる数Q、Rがただ一つ存在する。

 特に、R=0 のとき、即ち、

 数 a、b(bは0でない)に対して、a=bQ となる数 Q が存在するとき、

       a は bで割り切れる、a はbの倍数、b はaの約数、...
という。

 a、b、...に共通な倍数を公倍数といい、その中で最小なものを最小公倍数(L.C.M.)

 a、b、...に共通な約数を公約数といい、その中で最大なものを最大公約数(G.C.M.)

という。

 このとき、公倍数は、最小公倍数の倍数、公約数は、最大公約数の約数 である。

 特に、a、bの最大公約数を、(a,b) という記号で表す。

数 a、bに対して、最大公約数を G、最小公倍数を L とする。次の事実は基本的である。

定理  (A,B)=1である数A、Bを用いて、a=AG、b=BG と書ける。

    また、ab=GL が成り立つ。

定理  (a,b)=1で、bc が a で割り切れるならば、c は a で割り切れる。

(証明) (a,b)=1より、ab=L が成り立つ。bc が a の倍数なので、bc は a、b の公倍

    数となる。よって、bc はL(=ab)の倍数となり、bc は ab で割り切れる。

     従って、c は a で割り切れる。  (証終)

次の定理は、ユークリッドの互除法の理論的根拠を与える。

定理  (a,b)=(a−bQ,b) 

(証明) G=(a,b)より、G は a、b の約数なので、a−bQ の約数でもある。

    よって、G は、a−bQ、b の公約数となり、G は、(a−bQ,b) の約数となる。

    逆に、a−bQ=X とおくと、a=X+bQ なので、(X,b) は a の約数となる。

    よって、(X,b) は a、b の公約数となり、(a−bQ,b) は、G の約数となる。

    従って、(a,b)=(a−bQ,b) が成り立つ。  (証終)

ユークリッドの互除法

     (a,b)=(b,c)=(c,d)=・・・=(e,f)=f
              cはaをbで割った余り
                     dはbをcで割った余り
                         ・・・・・・・
                             eをfで割った余りが0

例 2952 と 1368 の最大公約数を、ユークリッドの互除法を用いて求めてみよう。

         2952=1368×2+216
         1368216×6+72
          216=72×3+0       従って、最大公約数は、72 となる。

 私が中学生の頃、次のような筆算形式で最大公約数を求めたことを覚えている。
この計算も、ユークリッドの互除法の一変化である。

 左の計算から、求める最大公約数は、72 である。

 もちろん、左の計算とは別に、2つの数を割り切る素数を使って、どんどん
 割っていき、割れなくなるまでの素数の積を求めれば、それが、最大公約
 数となる。(多くの方は、多分こちらの計算方法のほうをご存知でしょう。)

 上記の互除法の計算は、教科書的であるが、次のように計算する方法もある。

              


 互除法の原理を説明するとき、昔だったら上記のような計算で示したが、最近の高校の
教科書では、視覚的に訴える意味で図を用いる場合が多いようだ。

例 32と14の最大公約数を求めよ。

 下図のように、横の長さが32、縦の長さが14の長方形を考え、1辺の長さが同一の正
方形で埋め尽くす。そのときの正方形の最大辺の長さが最大公約数を与える。

    

 上図をにらめっこしていると、

   32=14×2+4

   14=4×3+2

    4=2×2+0    よって、 最大公約数は、2

という計算の意味づけが目に浮かんでくるようだ。


 最大公約数を求めることで、他にもいろいろな応用例が考えられる。

(応用例1)・・・分数 の約分(分子・分母を割り切る数が不明なときに有効!)

   ユークリッドの互除法により、2952=41×72、1368=19×72 とかけるので

  求める既約分数は、

 上記の分数の約分では、ユークリッドの互除法のご利益を余り感じないかもしれない。

次の分数 の約分はどうであろうか?一見すると、既約分数のような気がするが、
実は約分されて、 となる。この場合、分子・分母の共通因数を見つけること自体難
しいし、もしかしたら、約分しようと考えないかもしれない。ユークリッドの互除法を知って
いれば、簡単に共通因数を見つけることができる。

(応用例2)・・・不定方程式の解法(解の一つが簡単に求められます!)

  2952と1368の最大公約数を求める式を上手く式変形すると、不定方程式の解を得
 ることができる。
         72=1368−216×6
           =1368−(2952−1368×2)×6
           =1368×13+2952×(−6)

 以上から、不定方程式 1368X+2952Y=72の解の一つとして、X=13、Y=−6を
得る。不定方程式は、解が一つ見つかれば、全ての解は簡単に求められる。

 また、不定方程式の特殊解を筆算形式で求める方法が知られている。
                    (→ 参考:特別講義 2次体の整数論の「不定方程式」)


 不定方程式というと、「解は無数!」という雰囲気があるが、平成20年度の灘中学の入
試問題は、奇跡の1題で、神のなせる技のような趣である。

 1個66円の柿と1個35円のミカンを合わせて3890円分買った。このとき、柿と
ミカンはそれぞれ何個ずつ買ったのか?


(解) 柿を x 個、ミカンを y 個買ったものとすると、 66x+35y=3890

   66=35×1+31 より、 31=66−35

   35=31×1+4 より、 4=35−31=35×2−66

   31=4×7+3 より、 3=66−35−(35×2−66)×7=66×8−35×15

   4=3×1+1 より、 35×2−66−66×8+35×15=1

     すなわち、 66×(−9)+35×17=1

   よって、 66×(−35010)+35×66130=3890 より、

       66(x+35010)+35(y−66130)=0

   このとき、 整数 t に対して、 x=35t−35010 、 y=66130−66t

   x 、 y は0以上の整数なので、 35t−35010≧0 、 66130−66t≧0

   これを解いて、 1000.2<t<1001.97 より、 t=1001

   このとき、 x=25 、 y=64 である。  (終)

(コメント) 解答を書いていて、疑問に思ったことがある。「この問題は、小学生が解くんだ
      よな〜?」 でも、灘中を受験する小学生なら、「まっ、いいか!」という感じかな?

 純粋な小学生対象に、どのように解答すべきなのか、悩むところだ。上記の計算を省みて
次のように考えることもできるが、これが小学生向きかな?

(別解) 66x+35y=3890 において、x は5の倍数、y は2の倍数である。
    (当HP読者のHN「yuki」さんからも、このような視点のアドバイスをメールでいただいた。
                                                (平成26年6月13日付け)


    よって、 x=5a 、 y=2b とおいて代入すると、 33a+7b=389

    7b=389−33a≧0 より、 0≦a≦11

    a=0 のとき、 7b=389 (不適)

    a=1 のとき、 7b=389−33=356 (不適)

    a=2 のとき、 7b=389−66=323 (不適)

    a=3 のとき、 7b=389−99=290 (不適)

    a=4 のとき、 7b=389−132=257 (不適)

    a=5 のとき、 7b=389−165=224  より、 b=32

    a=6 のとき、 7b=389−198=191 (不適)

    a=7 のとき、 7b=389−231=158 (不適)

    a=8 のとき、 7b=389−264=125 (不適)

    a=9 のとき、 7b=389−297=92 (不適)

    a=10 のとき、 7b=389−330=59 (不適)

    a=11 のとき、 7b=389−363=26 (不適)

   以上から、求める解は、

     a=5 、 b=32 より、 x=25 、 b=64  (終)


 当HPがいつもお世話になっているHN「攻略法」さんから小学生向けの解答を始めいろい
ろな解答をお寄せいただいた。(平成22年10月19日付け)

鶴亀算として考える

 (解) すべて柿とすると、 3890÷66=58・・・62 なので、いくつかはミカンである。

 3890=66×58+62=66×57+128=66×57+35×2+58

1個の柿を2個のミカンと交換すると、余りが 62−58=4 だけ減る。

 ここで、128は4の倍数なので、上記の計算を、次のように変形する。

 3890=66×57+128=66×57+(35×2−66×1)×32=66×25+35×64

 よって、 柿を 25個 と ミカンを 64個 買えばよい。 (終)

 (別解) すべてミカンとすると、 3890=35×111+5 なので、いくつかは柿である。

 3890=35×111+5=35×114−100=35×114−(35×2−66×1)×25

 より、 3890=35×64+66×25

  よって、 柿を 25個 と ミカンを 64個 買えばよい。 (終)

合同式で考える

(解) 柿を x 個、ミカンを y 個買うとすると、

  「不定方程式 66x+35y=3890 の非負の整数解( x ,y )」を求めればよい。

  66x≡3890 (mod 35) または 35y≡3890 (mod 66)を考えればよい。

66x≡3890 (mod 35) の場合

66≡31 (mod 35) 、3890≡5 (mod 35) となるので、

   31x≡5 (mod 35)

   35x≡35 (mod 35) を辺々引いて、 4x≡30 (mod 35)

 両辺を8倍して、 32x≡240 (mod 35) より、 32x≡30 (mod 35)

   31x≡5 (mod 35) を辺々引いて、 x≡25 (mod 35)

 よって、 x=35n+25 (n は整数)と書ける。

 このとき、 35y=3890−66x=3890−66(35n+25)=2240−2310n より、

   y=64−66n≧0 より、 n≦32/33

 また、 x=35n+25≧0 より、 n≧−5/7 より、 −5/7≦n≦32/33

 n は整数なので、 n=0 となる。よって、 x=25 、y=64

  したがって、 柿を 25個 と ミカンを 64個 買えばよい。 (終)

剰余類の表を作成する(計算機向き) (→ 参考:「線形結合の問題」)

(解) 3890=66×58+62 より、66を法とする剰余類は、

 62
 62+1×66=128
 62+2×66=194
 62+3×66=260
  ・・・・・・・・・・・・
 62+33×66=2240=64×35  ← 35の倍数
  ・・・・・・・・・・・・
 62+58×66=3890

よって、ミカンは、64個、柿は、(3890−64×35)/66=25個 (終)

一般的に記述すると、a を法とする剰余類は、

 (c mod a)
 (c mod a)+1×a
 (c mod a)+2×a
 (c mod a)+3×a
   ・・・・・・・・・・・・
 (c mod a)+k×a=Y×b ← b の倍数なら、(x,y)=((c−Y×b)/a,Y)
                               ※複数個の場合もある
   ・・・・・・・・・・・・
 (c mod a)+INT(c/a)×a

である。

(コメント) 攻略法さんに感謝します。


 読者のために練習問題を作成してみました。(平成29年6月25日付け)

練習問題  1個71円の柿と1個32円のミカンを合わせて2017円分買った。このと
       き、柿とミカンはそれぞれ何個ずつ買ったのか?



 この問題を不定方程式として解くと次のようになるだろう。

(解) 71x+32y=2017 の一般解は、

   x=32k−18153 、y=40340−71k (kは整数)

 x>0 、y>0 より、 567.2・・・<k<568.1・・・・ なので、 k=568

  よって、 x=23 、y=12  (終)

 上記の解答を見て造作ないように感じられるかもしれないが、相当途中の計算を省略して
いるので、結構大変である。

 これに対して、攻略法さんの鶴亀算的解法をとれば、計算はぐっと楽になる。

(別解) 2017=71×28+29=71×27+100=71×27+4×25 で、

     25=32×3−71 なので、 2017=71×23+32×12

   よって、柿は、23個、ミカンは、12個ずつ買える。  (終)


 ユークリッドの互除法を用いて、最大公約数を求める場合、いったい何回ぐらい割り算を
実行すればよいのかが気にかかる。これについては、次の書籍に詳しい記述がある。

   和田秀男 著 数の世界 整数論への道(岩波書店)

 上記書籍によれば、割り算の回数 n を固定したときの、最初に割られる数 a の最小値
を求めることは、フィボナッチ数列 1,1,2,3,5,8,13,21,34,・・・と関係していて、
n=19 のとき、a=10946 だという。つまり、10000より小さい数と、さらにそれより小
さい何がしかの数との最大公約数を求める場合、最大18回の割り算が必要とのことであ
る。

 また、回数の計算について、次の定理が知られている。

ラメの定理   n≦4.79×(aの桁数)−0.37

 aが4桁の数とすると、n≦18.79 で上記結果と同じである。

 このラメの定理のおかげで、ユークリッドの互除法を用いて最大公約数を求める場合、
ある程度の計算に対する心構えを持つことができるのではないだろうか。

(参考文献:数学セミナー(2002年6月号)特集「因数分解のひろがり」
       高木貞治 著 初等整数論講義(岩波書店)
       和田秀男 著 数の世界 整数論への道(岩波書店)
       小島寛之 著 数学の遺伝子(日本実業出版社))