分数の足し算で「約分」が発生する条件

こんにちは！　日曜数学者のtsujimotterです！
今日は分数の足し算について考えたいと思います。

f:id:tsujimotter:20200618194220p:plain:w200

きっかけは学生のプログラミング課題でした。

tsujimotterは大学でPythonとC言語を教えているのですが、ある日の課題で「分数の足し算を計算する関数を作れ」というものがありました。時間差はありましたが、PythonとC言語の両方で似たような課題が出たのです。

実際、分数の足し算を一般に計算してみると

$\displaystyle \frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd} \tag{1}$

なので、あとは結果として得られた分数を約分してあげればよいわけです。

無事、関数を作ることはできたのですが、問題なのはその関数のテストです。関数がうまく動作することをテストするためには、分数の結果が約分されるような例を作らなければなりません。

ところがです。適当なテストケースを考えたのですが、どのケースもなぜか約分されない。。。tsujimotterはこの手の計算が大の苦手で、約分が発生するケースを作ることができませんでした。

頭が働いていないので、約分が必要な分数の足し算の例が思いつきません。何かいい例ないですか？
— tsujimotter (@tsujimotter) 2020年6月1日

良い方法がないかと考えているうちに、「約分が発生する必要十分条件を数学的に与えればよい」ということに気づきました。

そこで、今日は分数の足し算の計算において約分が発生する条件について考えてみたいと思います。

今回の知識は、小学校の先生の作問にも役に立つかもしれません。

「約分が発生する」必要十分条件？

それでは問題のセッティングを考えましょう。

今回はの目的は

$\displaystyle \frac{a}{b} + \frac{c}{d} \tag{2}$

の計算です。ここで、 $a/b, \; c/d$ は既約分数としておいても一般性は失いません。すなわち

$\operatorname{GCD}(a, b) = \operatorname{GCD}(c, d) = 1$

ということです。

ここで、式 $(2)$ で「約分が発生する」ということを、

$ad + bc$ と $bd$ が共通の約数を持つ

として定義しましょう。すなわち

$\operatorname{GCD}(ad + bc, bd) > 1$

ということですね。

早速結論ですが、整数論的な議論によって、以下の命題を示すことができました：

命題１（「約分」が発生する必要十分条件）

$a/b, c/d$ を既約分数（ $\operatorname{GCD}(a, b) = \operatorname{GCD}(c, d) = 1$ ）とする．

このとき，次が成り立つ：

$\operatorname{GCD}(ad + bc, bd) > 1 \;\; \Longleftrightarrow \;\; \operatorname{GCD}(b, d) > 1$

左の条件は $a/b + c/d$ で約分が発生することを意味しており、右の条件は分母同士が1より大きい公倍数を持つということを意味しています。つまり、分母同士が1より大きい公倍数を持つならば約分は発生するというわけですね。しかも、約分が発生するのはそのときに限るということです。

実際、具体例で確認してみましょう。

$\require{cancel}\displaystyle \frac{3}{10} + \frac{4}{15} = \frac{45 + 40}{150} = \frac{\cancel{85}}{\cancel{150}} = \frac{17}{30}$

元々の分数の分母は $10, 15$ であり、公約数 $5$ を持っています。よって、約分が発生するというわけですね。実際、計算途中で分母分子のキャンセルが発生しています。

それでは、命題１を証明しましょう。

（証明）
$(\Leftarrow)$ $p$ を $\operatorname{GCD}(b, d)$ の 1 より大きな約数とする。

このとき定義より、 $p \mid b$ かつ $p \mid d$ であるから

$p \mid ad + bc$ かつ $p\mid bd$

が言える。すなわち、 $p \mid \operatorname{GCD}(ad+bc, bd)$ である。特に

$\operatorname{GCD}(ad+bc, bd) > 1$

が言える。

$(\Rightarrow)$ $p$ を $\operatorname{GCD}(ad+bc, bd)$ を割り切る素数とする。

定義より、① $p \mid ad + bc$ かつ ② $p \mid bd$ である。

②から $p$ は素数より、 $p\mid b$ または $p\mid d$ であるので、それぞれ場合分けする。

(i) $p\mid b$ のとき：
①より、 $p\mid ad$ すなわち、 $p\mid a$ または $p\mid d$ であるが、 $p\mid a$ の場合 $\operatorname{GCD}(a, b) = 1$ に反する。よって $p \mid d$ である。

(ii) $p\mid d$ のとき：
①より、 $p\mid bc$ すなわち、 $p\mid b$ または $p\mid c$ であるが、 $p\mid c$ の場合 $\operatorname{GCD}(c, d) = 1$ に反する。よって $p \mid b$ である。

(i) (ii) のいずれも $p\mid b$ かつ $p \mid d$ を結論付ける。すなわち、 $\operatorname{GCD}(b, d) > 1$ である。

（証明終わり）

というわけで、無事、命題１が証明されました！

みなさん、いくらでも例題を作ることができてしまいますね！（ぐふふ）

「通分」を考慮する

おいおいちょっと待てよ、と思った方もいるかもしれません。

なんだその足し算は？　「通分」しないのか？

落ち着いてください。ちゃんと「通分」も考慮しますので。

先ほどの例では

$\displaystyle \frac{3}{10} + \frac{4}{15} = \frac{45 + 40}{150} = \frac{\cancel{85}}{\cancel{150}} = \frac{17}{30}$

と計算していました。

小学校のときを思い出すと、分母を $10 \times 15$ とするのでなく、実際は最小公倍数の $\operatorname{LCM}(10, 15) = 30$ としていましたよね。これを「通分」というのでした。

通分を考慮した場合、

$\displaystyle \frac{3}{10} + \frac{4}{15} = \frac{3 \times 3 + 4 \times 2}{30} = \frac{17}{30}$

となりますが、このケースでは約分が発生しません。

もちろん、通分を考慮すると、すべてのケースで約分が発生しなくなるわけではありません。

たとえば、次の例では

$\displaystyle \frac{4}{15} + \frac{9}{35} = \frac{4 \times 7 + 9 \times 3}{105} = \frac{\cancel{55}}{\cancel{105}} = \frac{11}{21}$

となりますが、この例では適切な通分をしているにも関わらず、約分も発生しています。

むしろこのようなケースの方が本質的な問題ではないかというご指摘を、@toku51n さんという方から頂きました。

その条件下でも
4/15+9/35=28/105+27/105=55/105=11/21
このような約分が発生する分数の足し算は存在し、そっちが本質だと思います。
分母に冪の同じ素数が含まれる事は必要条件ですが十分条件ではありません。実はこの問題はp進数が関係しています。
— TokusiN (@toku51n) 2020年6月18日

もっともなご指摘かと思います。前節の結果をツイートしたところ、たくさんの方から同様のご指摘をいただいたのでした。

というわけで、ここから先は通分を考慮した上で、約分できる条件について考えてみましょう。

約分の定義を改めて見直してみましょう。通分を考慮して分数の足し算を計算すると

$\displaystyle \frac{a}{b} + \frac{c}{d} = \frac{a\frac{\operatorname{LCM}(b, d)}{b} + c\frac{\operatorname{LCM}(b, d)}{d}}{\operatorname{LCM}(b, d)}$

となります。ごつい形をしていますが、

$\displaystyle \frac{\operatorname{LCM}(b, d)}{b}, \; \frac{\operatorname{LCM}(b, d)}{d}$

は、それぞれ整数になりますから

$\displaystyle L_b = \frac{\operatorname{LCM}(b, d)}{b}, \; L_d = \frac{\operatorname{LCM}(b, d)}{d}$

と置くことにすると

$\displaystyle \frac{a}{b} + \frac{c}{d} = \frac{a L_b + c L_d}{\operatorname{LCM}(b, d)}$

となります。

この右辺が約分できるということは

$\displaystyle \operatorname{GCD}(a L_b + c L_d, \operatorname{LCM}(b, d) ) > 1$

ということになります。

あとは、これが成り立つ $a, b, c, d$ の条件を考えればよいことになります。

ここだけの用語として、特に $\operatorname{GCD}(a L_b + c L_d, \operatorname{LCM}(b, d) )$ が素数 $p$ で割り切れるとき、「 $a/b + c/d$ は $p$ で約分できる」ということにしましょう。

また、今回の問題では「ある整数が素数 $p$ でちょうど何回割り切れるか」が重要になります。そこで、任意の 0 ではない整数 $x$ について、 $v_p(x)$ で「 $x$ が $p$ でちょうど割り切れる回数」を表すことにしましょう。すなわち、正の整数 $i$ に対して

$p^i \mid x$ かつ $p^{i+1} \nmid x$

が成り立つとき、 $v_p(x) = i$ と定義することにします。

これは $p$ 進付値と呼ばれるものですが、今回は深く追及するのはやめておきましょう。

$p$ 進付値を使うというアイデアは、@toku51n さんに教えていただいたものです。ありがとうございます。

このようなセッティングのもとで、次の命題２を証明したいと思います。

命題２（通分を考慮した「約分」が発生する条件）

$a/b, c/d$ を既約分数（ $\operatorname{GCD}(a, b) = \operatorname{GCD}(c, d) = 1$ ）とする．

このとき，任意の素数 $p$ に対して次が成り立つ：

$\displaystyle \frac{a}{b} + \frac{c}{d}$ は $p$ で約分できる $\;\; \Longrightarrow \;\; v_p(b) = v_p(d) > 0$

これは、 $p$ で約分できるための「必要十分条件ではない」ことに注意しましょう。すなわち、 $v_p(b) = v_p(d)$ が成り立つからといって、必ず $p$ で約分できるというわけではありません。

一方、対偶をとると、任意の素数 $p$ に対して

$v_p(b) \neq v_p(d)$ $\;\; \Longrightarrow \;\;$ $\displaystyle \frac{a}{b} + \frac{c}{d}$ は $p$ で約分できない

となりますので、約分できないことの判定には使えます。これについては、あとで具体例を用いて確認してみましょう。

それでは、命題２の証明にいきましょう。

（証明）
まず、最小公倍数は、 $p$ 進付値を用いて

$\displaystyle \operatorname{LCM}(b, d) = \prod_{p} p^{\max\{v_p(b), v_p(d)\} }$

と表せることに注意する（ここで総積記号 $\prod_p$ は、すべての素数 $p$ に対して積をとることを表す）。

これにより $L_b, L_d$ は次のように表せる：

$\displaystyle L_b = \frac{\operatorname{LCM}(b, d)}{b} = \prod_{p} p^{\max\{0, v_p(d) - v_p(b)\} }$

$\displaystyle L_d = \frac{\operatorname{LCM}(b, d)}{d} = \prod_{p} p^{\max\{v_p(b) - v_p(d), 0\} }$

特に、それぞれの $p$ 進付値は

$v_p(L_b) = \max\{0, v_p(d) - v_p(b)\}$

$v_p(L_d) = \max\{v_p(b) - v_p(d), 0\}$

となる。

$\frac{a}{b} + \frac{c}{d}$ が $p$ で割り切れるという仮定より、

$p \mid \operatorname{GCD}(aL_b + cL_d, \operatorname{LCM}(b, d) )$

である。すなわち、① $p\mid aL_b + cL_d$ かつ ② $p\mid b$ または $p\mid d$ である。

ここで、②を考慮すると、 $v_p(b), v_p(d)$ は次の (i) ～ (iii) のいずれかの条件を満たす：

(i) $v_p(b) > v_p(d)$

(ii) $v_p(b) < v_p(d)$

(iii) $v_p(b) = v_p(d) > 0$

ここで、(i) $v_p(b) > v_p(d)$ であると仮定すると

$v_p(L_b) = \max\{0, v_p(d) - v_p(b)\} = 0$

$v_p(L_d) = \max\{v_p(b) - v_p(d), 0\} > 0$

である。よって、 $p\nmid L_b$ かつ $p \mid L_d$ である。

①と合わせて、 $p \mid a$ であることがわかる。

一方、 $\operatorname{GCD}(a, b) = 1$ より $p\nmid b$ であるが、これは $v_p(d) > 0$ であることに矛盾する。よって、(i) は成立しない。

また、(ii) $v_p(b) < v_p(d)$ であると仮定しても、同様に矛盾が生じる。

よって、(iii) $v_p(b) = v_p(d) > 0$ であると結論付けてよい。

（証明終わり）

具体例の確認

最後に、命題２について、具体例を通して確認して終わりにしましょう。

例１：

$\displaystyle \frac{1}{2} + \frac{1}{4}$

は、

$v_2(2) \neq v_2(4)$

なので、約分されません。

実際、

$\displaystyle \frac{1}{2} + \frac{1}{4} = \frac{2 + 1}{4} = \frac{3}{4}$

となり、たしかに約分されていません。

例２：

$\displaystyle \frac{1}{105} + \frac{4}{225}$

は、

$v_3(105) \neq v_3(225)$

$v_5(105) \neq v_3(225)$

$v_7(105) \neq v_3(225)$

なので、約分されません。

実際、

$\displaystyle \frac{1}{105} + \frac{4}{225} = \frac{1\times 7 + 4\times 15}{1575} = \frac{67}{1575}$

となり、たしかに約分されていません。

こんな風に、命題２は約分されないことの判定には使えるわけですね。

例３：

$\displaystyle \frac{4}{15} + \frac{9}{35}$

は、

$v_3(15) \neq v_3(35)$

$v_5(15) = v_5(35) > 0$

$v_7(15) \neq v_7(35)$

なので、もし約分されるとしたら、その素因数は $5$ でなくてはなりません。

実際、

$\displaystyle \frac{4}{15} + \frac{9}{35} = \frac{4\times 7 + 9\times 3}{105} = \frac{\cancelto{\div 5}{55}}{\cancelto{\div 5}{105}} = \frac{11}{21}$