実数に拡張した最大公約数 - RPGツクールと数学のブログ

過去ブログの転載です。

最大公約数は、ユークリッドの互除法を定式化することで、以下の式により求めることが可能です。

$\displaystyle \gcd (a, b)=\begin{cases}\gcd(b,\mod(a,b)) (b \ne 0)\\ a (b = 0)\end{cases}$

正の整数 $\displaystyle a$ と $\displaystyle b$ の最大公約数を $\displaystyle \gcd(a, b)$ とします。 $\displaystyle \mod(a, b)$ は、 $\displaystyle a$ を $\displaystyle b$ で割ったあまりを意味します。

この式で例えば138と60との最大公約数を求めてみると

$\displaystyle \gcd(138, 60)$
$\displaystyle = \gcd(60, \mod(138, 60))$
$\displaystyle = \gcd(60, 18)$
$\displaystyle = \gcd(18, \mod(60, 18))$
$\displaystyle = \gcd(18, 6)$
$\displaystyle = \gcd(6, \mod(18, 6))$
$\displaystyle = \gcd(6, 0)$
$\displaystyle = 6$

となりますから、6が最大公約数ということになります。

そもそも最大公約数って何を意味しているのかというと、公約数の中で最大のものといえばそうなのですが、↓こういう風に捉えても良いですよね。

$\displaystyle ax=138$
$\displaystyle ay=60$
を満たす整数 $\displaystyle x, y$ が存在するときの最大の数 $\displaystyle a$ が、138の60の最大公約数である。

この場合は $\displaystyle a=6$ なわけですが、 $\displaystyle a \ge 7$ になると
これらを同時に満たす整数 $\displaystyle x, y$ は存在しないということが言えます。

そりゃあそうですよね。138と60の最大公約数は6なので、それ以上の数では共通する約数を持たないことから、両方で割り切れるような整数はありません。

では、最大公約数の定義を上のようにした場合どうなるでしょう。すると、 $\displaystyle a$ とか138とか60の部分は、別に整数じゃなくてもいいことが分かります。
例えば次のような問題を考えてみましょう。

$\displaystyle ax=45.5$
$\displaystyle ay=70.8$
を満たす整数 $\displaystyle x, y$ が存在するための最大の実数 $\displaystyle a$ は何か？

この問題を解決するのが、実数に拡張した最大公約数となりましょう。

イメージとしては、何か実数を何回か足して（整数倍して）45.5と70.8を作れるようなもののうち最大の数が $\displaystyle a$ 、という感じです。

最大公約数を求める式は以下のものでした。

$\displaystyle \gcd (a, b)=\begin{cases}\gcd(b,\mod(a,b)) (b \ne 0)\\ a (b \ne 0)\end{cases}$

ここで、 $\displaystyle a, b$ が実数であっても使えるように拡張したいわけですが、問題となるのはmodの部分だけですね。その他は別に実数でも無問題です。modが実数に拡張できれば $\displaystyle \gcd$ も拡張できます。

modの定式化は以下のようにできます：

$\displaystyle \mod(x, y)=x-y \left\lfloor \frac{x}{y} \right\rfloor$

あまりの意味を拡大解釈することで、この式だけで実数の余りに対応させることが可能となります。実数のmodはこの式を使って計算するようにすればいいわけですね。

modの拡張ができたので、 $\displaystyle \gcd$ の拡張もできました。これでOKです。

さっきの問題を解くためには、以下の式を計算すればいいことになります。

$\displaystyle a=\gcd(45.5, 70.8)$

それでは、定義した式にのっとってやってみましょう。

$\displaystyle \gcd(45.5, 70.8)$
$\displaystyle = \gcd(70.8, \mod(45.5, 70.8))$
$\displaystyle = \gcd(70.8, 45.5)\left(45.5-70.8 \left\lfloor \frac{45.5}{70.8} \right\rfloor =45.5\right)$
$\displaystyle = \gcd(45.5, \mod(70.8, 45.5))$
$\displaystyle = \gcd(45.5, 25.3)\left(70.8-45.5 \left\lfloor \frac{70.8}{45.5} \right\rfloor = 70.8-45.5 \times 1=25.3\right)$
$\displaystyle = \gcd(25.3, \mod(45.5, 25.3))$
$\displaystyle = \gcd(25.3, 20.2)\left(45.5-25.3\left\lfloor \frac{45.5}{25.3} \right\rfloor=45.5-25.3 \times 1=20.2\right)$
$\displaystyle = \gcd(20.2, \mod(25.3, 20.2))$
$\displaystyle = \gcd(20.2, 5.1)\left(25.3-20.2\left\lfloor \frac{25.3}{20.2}\right\rfloor=25.3-20.2\times1=5.1\right)$
$\displaystyle = \gcd(5.1, \mod(20.2, 5.1))$
$\displaystyle = \gcd(5.1, 4.9)\left(20.2-5.1\left\lfloor \frac{20.2}{5.1}\right\rfloor=20.2-5.1\times3=4.9\right)$
$\displaystyle = \gcd(4.9, \mod(5.1, 4.9))$
$\displaystyle = \gcd(4.9, 0.2)\left(5.1-4.9\left\lfloor \frac{5.1}{4.9}\right\rfloor =5.1-4.9\times1=0.2\right)$
$\displaystyle = \gcd(0.2, \mod(4.9, 0.2))$
$\displaystyle = \gcd(0.2, 0.1)\left(4.9-0.2\left\lfloor \frac{4.9}{0.2}\right\rfloor=4.9-0.2\times24=0.1\right)$
$\displaystyle = \gcd(0.1, \mod(0.2, 0.1))$
$\displaystyle = \gcd(0.1, 0)\left(0.2-0.1\left\lfloor \frac{0.2}{0.1}\right\rfloor=0.2-0.1\times2=0\right)$
$\displaystyle = 0.1$

これにより、45.5と70.8の最大公約数は0.1であることが分かりました。

$\displaystyle \gcd(45.5, 70.8)=\gcd(70.8, 45.5)$ の部分ですが、 $\displaystyle \gcd$ は交換則（もちろん結合則も）が成り立つので右が大きかったら入れ替えればOKです。（ただしマイナスの数の場合はこの定義だと交換則は成り立ちません）

こうしてさっきの問題

$\displaystyle ax=45.5$
$\displaystyle ay=70.8$
を満たす整数 $\displaystyle x, y$ が存在するための最大の実数 $\displaystyle a$ は何か？

のこたえは $\displaystyle a=0.1$ ということになりました。

このとき $\displaystyle x=455, y=708$ となるわけですが、何だかこの場合はつまらない結果ですね。45.6と70.8にしてみると、これは1.2になります。

これが本当に最大の数 $\displaystyle a$ になってるのかどうかの証明はどこかで必要なのでしょうけれど、何やらめんどくさそうなのでやめておきます。

有理数と有理数との間には必ず正の有理数としての最大公約数が存在しますが、有理数と無理数の場合は最大公約数が0になります。また、無理数同士でも $\displaystyle \sqrt{2}$ と $\displaystyle \sqrt{3}$ の最大公約数は0です。
直感的にも明らかですね。 $\displaystyle a\sqrt{2}$ を整数倍して $\displaystyle b\sqrt{3}$ にできるとは思えません。

ちなみに、最小公倍数もこの最大公約数を用いて表現することができます。

$\displaystyle a, b$ の最小公倍数 $\displaystyle {\rm lcm}(a, b)$ は、次式で表わされます。
$\displaystyle {\rm lcm}(a, b)=\frac{ab}{\gcd(a, b)}$

ただし、3つ以上の数の場合は成り立ちません。すなわち、 $\displaystyle {\rm lcm}(a, b, c)=\frac{abc}{\gcd(a, b, c)}$ とはなりません。3つ以上の場合は次のように変換する必要があります。

$\displaystyle {\rm lcm}(a, b, c)$
$\displaystyle ={\rm lcm}({\rm lcm}(a, b), c)$
$\displaystyle ={\rm lcm}\left(\frac{ab}{\gcd(a, b)}, c\right)$
$\displaystyle =\frac{abc}{\gcd(a, b)\gcd\left(\frac{ab}{\gcd(a, b)}, c\right)}$

割と汚い形になりますね。

最小公倍数といっても、この場合は実数になります。

例えば45.6と70.8との最小公倍数が意味するのは、
$\displaystyle 45.6x＝a$
$\displaystyle 70.8y＝a$
を満たす整数 $\displaystyle x, y$ が存在するための最小の実数 $\displaystyle a$ という意味になり、

$\displaystyle a={\rm lcm}(45.6, 70.8)=\frac{45.6\times 70.8}{\gcd(45.6, 70.8)}=\frac{3228.48}{1.2}=2690.4$
となります。この場合、最小公倍数は整数になりませんね。

このとき $\displaystyle x=59, y=38$ となり、ともに整数になっているもののなかで2690.4が最小です。

すなわち、 $\displaystyle \frac{a}{45.6}+\frac{b}{70.8}=\frac{59a+38b}{2690.4}$ と通分されます。

さらに分母を整数にしたい場合は、1との最小公倍数をとると、その数を整数倍して整数になったときの最小値を得ることができます。

$\displaystyle {\rm lcm}(2690.4, 1)=13452$ となるので、分母分子を $\displaystyle \frac{13452}{2690.4}=5$ 倍すれば、 $\displaystyle \frac{59a+38b}{2690.4}=\frac{295a+190b}{13452}$ となって全部整数になります。

何で1との最小公倍数をとるとそういうことが出来るのかについてですが、以下のように考えるとよいでしょう。

$\displaystyle {\rm lcm}(2690.4, 1)$ とは、
$\displaystyle 2690.4x=a$ … ①
$\displaystyle 1y=a$ … ②
を満たす最小の実数 $\displaystyle a$ のことを意味しますが、②より、 $\displaystyle a$ は $\displaystyle y$ そのものとなります。 $\displaystyle y$ は整数でしたから、 $\displaystyle a$ は2690.4を整数倍して最小の整数になる値と言うことが出来ます。

なので、 $\displaystyle a={\rm lcm}(2690.4, 1)$ が最小の整数となり、そのときの $\displaystyle x=\frac{{\rm lcm}(2690.4, 1)}{2690.4}=5$ が整数倍する値ということになります。

$\displaystyle \gcd$ を用いても同様の結果が得られます。

$\displaystyle \gcd(2690.4, 1)$ とは
$\displaystyle ax=2690.4$ … ①
$\displaystyle ay=1$ … ②
を満たす最大の $\displaystyle a$ のことで、②より $\displaystyle y=\frac{1}{a}$ となりますから、 $\displaystyle y$ は整数だったので、 $\displaystyle \frac{1}{a}$ はこれを満たす最小（最大の逆数だから）の整数になります。