大きい数でも約分したい【ユークリッドの互除法】

今回の内容の動画版(数値は異なります)→10033/12877は約分できるか【数学検定1級過去問】

次は、私がかなり気に入っている問題の一つです。

[box class="blue_box" title="問"]

次の分数を約分せよ。

\( \displaystyle \frac{12533}{15853} \)
[/box]

シンプルな上に、なんといっても予備知識がほぼいらない点が良いです。ほとんどの方にとって分数の約分というのがなんであるかは説明の必要がなく、問題文の意味はすぐ共有できるのです。しかし、実際に約分をしようとすると簡単にはいかない。思いつく素数\( 2,3,5,7,11,\cdots \)で割ってみても割れない。相当な大きさの数で割らないと無理そうだ…ということでかなり困難を強いられます。2数の共通の約数(すなわち公約数)はどのように求められるのでしょうか。

実はこのような場合にはユークリッドの互除法という計算が有効です。

ユーグリッドの互除法を使うと、2数の最大公約数が次のように計算できます。理由は後回しにして、まず方法を紹介します。次の図は計算が終わったところの様子です。

:20180815213831j:plain

計算は右から左へ進んでいます。まず最初に15853を12533で割って、その余りを今度は割る数として12533の右に持っていきます。あとはこれを繰り返すのです。余りは0以上でステップを重ねるごとにどんどん小さくなりますから、いつかは0になります。

:20180815215013j:plain

余りが0になったとき一番左にある数 83 が15853と12533の最大公約数(G.C.DやG.C.M.ともいう)となっています。

ではなぜ上の手順でなぜ15853と12533の最大公約数が求められるのでしょうか。タイルの敷き詰めなど図的な説明もありますが、次の集合の考えを使う説明もあります(初等整数論の教科書ではこちらが普通)。

15853と12533の割り算の結果は

\( 15853=12533\cdot 1+3320\) ……①

と表されます(\( \cdot \)は掛け算記号\( \times\)の意味です)。ここで、2つの集合

\( A=\{d|d\mbox{は}15853\mbox{と}12533\mbox{を割り切る}\} \)

\( B=\{d'|d'\mbox{は}12533\mbox{と}3320\mbox{を割り切る}\} \)

を考えると、\( A=B \)が成り立ちます。実際、任意の\( d\in A\)を持ってくると、

\( 15853=ad \), \( 12533=bd \)

となる自然数\( a,b \)が存在しますが、式の形①より

\( 3320=ad-bd\cdot 1=(a-b\cdot 1)d \)

となり、\( d \)は\( 3320 \)も割ることになります。つまり\( d \)は12533と3320の公約数でもあるので\( d\in B \)、よって\( A\subset B \)となります。また逆に任意の\( d'\in B \)に対してやはり式の形①より\( d' \)は15853も割るため、\( d' \)は15853と12533の公約数となり\( d'\in A \)、すなわち\( A\supset B \)です。

\( A=B \)ですから、特にそれぞれの集合に属する最大値も一致しますから、

「(15853と12533の最大公約数)は(12533と3320の最大公約数)と等しい」

のです。以下議論を繰り返すと以下のことがわかります。

「(12533と3320の最大公約数)は(3320と2573の最大公約数)と等しい」

「(3320と2573の最大公約数)は(2573と747の最大公約数)と等しい」

「(2573と747の最大公約数)は(3320と2573の最大公約数)と等しい」

「(747と332の最大公約数)は(332と83の最大公約数)と等しい」

:20180815224923j:plain