ユークリッドの互除法

本日のお題

  1. ユークリッドの互除法を用いて,コンピュータで2つの整数の最大公約数を求めましょう。
  2. 不定方程式 \(131x + 91y = 1\) を満たす整数 \(x\)\(y\) を求めるアルゴリズムを作りましょう。

前回は,不定方程式の整数解を求めることを考えました

その中でも,やはり

\begin{equation} ax + by = c \end{equation}

の形の不定方程式が一番面白い(と私は思うのです)
これを見ると,数列の漸化式 や 線形の微分方程式 など様々な問題が関連して想起されます

まぁ,それはさておき・・・
昨日の練習問題にあった \begin{equation} 131x + 91y = 1 \end{equation} はおできになりましたでしょうか? 解を1つ見つけさえすれば良い・・・と言っても,これはなかなか面倒です

解答には,ユークリッドを互除法を使って,などといい加減な書き方をしてしまいましたので,ここで,整数解の1つである \(x = -25\)\(y = 36\) の見つけ方を復習しておきたいと思います

ユークリッドの互除法

まずは,ユークリッドの互除法を保証する,大事な命題の説明から・・・

2つの整数 \(a\)\(b\)\(a > b\))について,\(a\)\(b\) で割った商と余りをそれぞれ \(q\)\(r\) とおきます・・・すなわち \begin{equation} a = bq + r\ (0 \leqq r < b) \end{equation} であるとき,\(a\)\(b\) の最大公約数 と \(b\)\(r\) の最大公約数 とは等しくなります

\(a\)\(b\) の最大公約数,\(b\)\(r\) の最大公約数を,それぞれ \(m\)\(m'\),したがって \begin{equation} a = mk,\quad b = ml \end{equation}

\(k\)\(l\) は 互いに素 です)

とします \begin{equation} r = a - bq = mk - mlq = m(k - lq) \end{equation} となって,\(r\)\(m\) で割り切れることが分かります

\(b\)\(m\) で割り切れるので,\(m\)\(b\)\(r\) の公約数となり,したがって \(m' \geqq m\) です

今度は逆に,\(m \geqq m'\) を示します

\(m'\)\(b\)\(r\) の最大公約数ですから \begin{equation} b = m'k', \quad r = m'l'\end{equation}

\(k'\)\(l'\) は 互いに素 です)

とします \begin{equation} a = bq + r = m'k'q + m'l' = m'(k'q + l') \end{equation} となって,\(a\)\(m'\) で割り切れることが分かります

\(b\)\(m'\) で割り切れるので,\(m'\)\(a\)\(b\) の公約数となり,したがって \(m \geqq m'\) となります

以上から,\(m = m'\) です

このことにより,除数を余りで次々に割っていって,余りが \(0\) になったときの除数が,2つの整数の最大公約数であると言えることが分かります

2元1次の不定方式の整数解を1つ見つける

それでは \(131x + 91y = 1\) について,整数解の1つを探し出しましょう

まず,\(131\)\(91\) について,互いに素な数同士だから,余りが \(1\) になるまで割り算を繰り返します \begin{equation} \label{euclid} \begin{array}{lcc} 131 = 91\cdot 1 + 40 & \cdots & (8.1) \\ 91 = 40\cdot 2 + 11 & \cdots & (8.2) \\ 40 = 11\cdot 3 + 7 & \cdots & (8.3) \\ 11 = 7\cdot 1 + 4 & \cdots & (8.4) \\ 7 = 4\cdot 1 + 3 & \cdots & (8.5) \\ 4 = 3\cdot 1 + 1 & \cdots & (8.6) \\ \end{array}\end{equation} ここまで来たら,\((\ref{euclid}.6)\) の式をホンの少し変形して \begin{equation} 4 + 3\cdot(-1) = 1 \end{equation} とします
ここに \((\ref{euclid}.5)\) の式をホンの少し変形した \(3 = 7 - 4\cdot 1\) を代入すると \begin{equation} \begin{array}{l} 4 + (7 - 4\cdot 1)\cdot(-1) = 1 \\ \mbox{∴}\quad 7\cdot(-1) + 4\cdot 2 = 1 \end{array}\end{equation} 以下この操作を繰り返します \begin{equation} \begin{array}{l} 7\cdot(-1) + (11 - 7\cdot 1)\cdot 2 = 1 \\ \mbox{∴}\quad 11\cdot 2 + 7\cdot (-3) = 1 \\ 11\cdot 2 + (40 - 11\cdot 3)\cdot (-3) = 1 \\ \mbox{∴}\quad 40\cdot (-3) + 11\cdot 11 = 1 \\ 40\cdot (-3) + (91 - 40\cdot 2)\cdot 11 = 1 \\ \mbox{∴}\quad 91\cdot 11 + 40\cdot (-25) = 1 \\ 91\cdot 11 + (131 - 91\cdot 1)\cdot (-25) = 1 \\ \mbox{∴}\quad 131\cdot(-25) + 91\cdot 36 = 1 \end{array} \end{equation} となって,最後の式は \((x,\ y) = (-25,\ 36)\)\(131x + 91y = 1\) を満たしていることを表しています
ところが,できたことはできたのですが,なかなか疲れます

自動化の試み

怠け者は,楽をしようと工夫します!!

こういうとき,結構役に立つのが Excel などの表計算ソフトです
スマホでも表計算ソフトが使えるので,どんどん使ったらイイと思います。

上の図は,Excel で A1 に 131 を,B1 に 91 をそれぞれ入力して,8列目に

\(131\cdot (-25) + 91\cdot 36 = 1\)

に相当する数値を表示させたています
各セルに入力されている式は,下のとおりです

A1 131
B1 91
C1 =QUOTIENT(A1,B1)
D1 =MOD(A1,B1)
A2 =B1
B2 =D1
C2 =QUOTIENT(A2,B2)
D2 =MOD(A2,B2)
3列目~6列目は2列目をコピー
QUOTIENT(セル1,セル2) はセル1をセル2で割った商
MOD(セル1,セル2) はセル1をセル2で割った余り

これで,余りが1になるまでの割り算ができました
問題は,その下の表です・・・どのような式を書けば宜しいのでしょうか?

上の割り算の式 (1)~(6) を上から順に \begin{equation}a_n = b_n\cdot q_n + r_n\ (n = 1,\ 2,\ \cdots ,\ 6)\end{equation} とおくと \begin{equation} a_{n + 1} = b_n, \quad b_{n + 1} = r_n \end{equation} が成り立っており,さらに, \begin{equation} \alpha_n\cdot a_n + \beta_n\cdot b_n = 1\end{equation} として,\(\alpha_6\cdot a_6 + \beta_6\cdot b_n = 1\) すなわち \(4\cdot 1 + 3\cdot(-1) = 1\) から順に \(\alpha_1\cdot a_1 + \beta_1\cdot b_1 = 1\) を求める操作を考えましょう \begin{equation} \alpha_n\cdot a_n + \beta_n\cdot b_n = 1\end{equation} に \begin{equation} a_n = b_{n - 1},\quad b_n = r_{n - 1} = a_{n - 1} - q_{n - 1}\cdot b_{n - 1} \end{equation} を代入して整理をすると \begin{equation} \beta_n\cdot a_{n - 1} + (\alpha_n - \beta_n\cdot q_{n - 1})\cdot b_{n - 1} = 1\end{equation} Excel の 第13列 と 第12列 に入る 数値・式 は次のとおりになります

A13 =A6
B13 1
C13 =B6
D13 =-C6
A12 =A5
B12 =D13
C12 =B5
D12 =B13-D13*C5

第12列を第11列から第8列までコピーすると,表が完成します

この表では自動で計算できるという状況にはなっていませんが,中心となるアルゴリズムについては,このように考えて宜しいというものになっています

\(a\)\(b\) の値を入力すれば,1つの整数解が求められるという表にするためには,条件文を多少追加しなければなりません
興味のある人は作ってみてください
上のことが分かっていれば,それほど難しいことではありません


プログラミング

小学校でプログラミング教育が始まっています
折角,解を求めるアルゴリズムが理解できたのであれば,それをプログラミングとして実現してみたくなります

私自身は,本当に若いころ,多少カジッタ程度ですが,このサイトでは Javascript を用いたアプレットを利用するので,何十年ぶりに簡単なプログラミンを再経験することになっています

Scratch は小学生が利用していますし,高等学校の教科「情報」では Python を扱う学校もあるようです

算数・数学や理科などで学んだ内容を利用して,プログラミングすることは,各科目の学習内容の深化や定着に貢献します

一例として,不定方程式の整数解を求める簡単なアプレットを作成しましたので,載せておきます

ただし,いつもの言い訳です・・・数式の表示が上手くできません
これは,moodle 内で Javascript を使ったとき,Javascript の中で type set ができないという不都合があり,この問題で悩むことがあります
元々静的な web ページにあったものを,moodle に移植しておりまして,ある意味このサイトでのページ表示後の type set を諦めています
どなたか,解決方法をご存じでしたら,ご教授願います


\(x +\,\) \(y = 1\) 

解 答


Last modified: Saturday, 17 July 2021, 6:36 AM