tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

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

数学 整数論 日曜数学 自由研究・独自研究

最近、頭の中が「分数の足し算」でいっぱいなtsujimotterです。こんにちは。

前回・前々回の記事から引き続き、分数の足し算の話題です。過去記事はこちらをご覧ください：
tsujimotter.hatenablog.com
tsujimotter.hatenablog.com


さて、これまで分数の足し算 \frac{a}{b} + \frac{c}{d} において、素数 p で約分できる条件について考えてきました。前回はp進展開を用いた見方を与えました。

今回はより簡潔に判定できる考え方を教えていただきましたので、それを紹介したいと思います。といっても、原理はp進展開の場合と同じです。

さらに考えを推し進めると「 p で割れるか」だけでなく「 p^k で割れるか」についても議論できることに気づきましたので、それについて紹介します！

pで約分できる条件

この方法は、@toku51n さんに教えていただきました。


例によって \displaystyle \frac{4}{15} + \frac{9}{35} で考えてみましょう。両方とも分母が 5 でちょうど1回割れる（ v_5(15) = v_5(35) = 1）ので、 \displaystyle \frac{1}{5} を「分母」に残し、それ以外を「分子」に持っていきます。

\displaystyle \frac{4}{15} + \frac{9}{35} = \frac{\frac{4}{3} + \frac{9}{7}}{5}

ここで、もし「分子」の部分が \bmod{5} で 0 に合同であれば、分子と分母が 5 で約分できるという寸法です。「 \bmod{5} で」といっていますが、実際「分子」は「5を分母の素因数に持たない既約分数」ですので、実際は \mathbb{Z}_{(5)} の元として \bmod{5} をとっていることに注意します。

すると「分子」は

\displaystyle \frac{4}{3} + \frac{9}{7} \equiv \frac{9}{3} + \frac{14}{7} = 3 + 2 \equiv 0 \pmod{5\mathbb{Z}_{(5)}}

となり、たしかに 5 で約分できるということがわかります。


このことは、 v_5(15) = v_5(35) = 1 より 5^1 を \displaystyle \frac{4}{15} + \frac{9}{35} にかけて

\displaystyle \left( \frac{4}{15} + \frac{9}{35} \right)\cdot 5^1 \pmod{5\mathbb{Z}_{(5)}}

を考えると思うことができます。


一般に、次の命題が成り立ちますので、まとめておきましょう：

命題３（ p 進展開を用いた約分判定法）
a/b, \; c/d を既約分数とし、 p を任意の素数とする。

このとき、正の整数 n について次が成り立つ：

\displaystyle \frac{a}{b} + \frac{c}{d} が p で約分される
\;\; \Longleftrightarrow \;\; v_p(b) = v_p(d) = n > 0 かつ \displaystyle \left(\frac{a}{b} + \frac{c}{d}\right) \cdot p^n \equiv 0 \pmod{p\mathbb{Z}_{(p)}}

これは前回の命題２（p進展開を用いたもの）を単純に言い換えただけですので、同様に証明できます。

pべきで約分できる条件

実は、上の命題３はさらに一般化することができます。

先ほどは、分母・分子を素数 p で約分できる条件を考えていましたが、素数 p のべき乗で約分できる条件を与えることができます。

命題４（ p 進展開を用いた約分判定法）
a/b, \; c/d を既約分数とし、 p を任意の素数とする。

1 \leq k \leq n なる正の整数 k, n について次が成り立つ：

\displaystyle \frac{a}{b} + \frac{c}{d} が p^k で約分される
\;\; \Longleftrightarrow \;\; v_p(b) = v_p(d) = n > 0 かつ \displaystyle \left(\frac{a}{b} + \frac{c}{d}\right) \cdot p^n \equiv 0 \pmod{p^k\mathbb{Z}_{(p)}}

\bmod{p} をとるのではなく、 \bmod{p^k} をとればよいということですね。証明は、同じく p 進展開を考えればよいかと思います。


以下では具体例の計算をしてみたいと思います。

例： \frac{16}{25} + \frac{2}{75}

まず、 \frac{16}{25}, \frac{2}{75} のどちらの分母も 5^2 で割り切れることに注意しましょう。すなわち、 v_p(b) = v_p(d) = 2 です。よって、 5 で最大 2 回約分できることになります。

5^2 をかけて \bmod{5^2} をとると

\displaystyle \left(\frac{16}{25} + \frac{2}{75}\right)\cdot 5^2 = 16 + \frac{2}{3} \equiv 16 + \frac{27}{3} = \frac{75}{3} \equiv 0 \pmod{5^2}

となりますので、命題４の \Longleftarrow を用いることで 5^2 で約分できることがわかります。

面白いですね！


実はこの例自体、 \frac{X}{25} + \frac{Y}{75} が 5^2 で約分できる条件から逆算して作っています。やってみましょう。

5^2 をかけると

\displaystyle \left(\frac{X}{25} + \frac{Y}{75}\right)\cdot 5^2 = X + \frac{Y}{3}

となりますので、 \bmod{5^2} で 0 になるような X, Y を探せば良いことになります。

適当に X = 16 として

\displaystyle 16 + \frac{Y}{3} \equiv 0 \pmod{5^2}

となるような Y を考えると、 27 があります。 27 \equiv 2\pmod{5^2} として Y = 2 としたわけですね。


こんな風に、 p で約分できる回数をコントロールしつつ、所望の分母を持つ分数の足し算を計算することができるというわけです。面白いでしょう！


関連記事の紹介

ありがたいことに、本シリーズの記事を公開しTwitterで紹介したことで、さまざまコメントをいただきました。

特に、以下に挙げるお二方は、なんと関連するブログを書いてくれました！
せっかくなので、このブログでも紹介させてください。

id:agajo さんの記事

agajo.hatenablog.com

こちらの記事では、通分した後の分子 aD + cB \equiv 0 \pmod{p}（私の第１回の記事の表記だと aL_b + cL_d \equiv 0 \pmod{p}）を満たす変数を具体的に列挙する方法について述べられています。
これによって、私の元々のモチベーションであった「約分が発生する分数の足し算を列挙する」が実現できるわけですね。面白いです！

id:jurupapa さんの記事

maxima.hatenablog.jp

「Maximaで綴る数学の旅」のタイトル通り、Maximaを使って数学の紹介をされているブログです。これまでも度々お互いに関連する記事を書いたりするなど、交流させていただいています。
最近Maximaの「padicsパッケージ」が開発されたそうで、その機能を用いたp進数関連の計算についての記事をたくさん紹介されています。
今回の記事でも、実際にpadicsパッケージを用いてp進展開を計算し、約分できる条件を確認していただいています。たしかに、p進展開が容易に計算できるのであれば、今回の方法は約分の判定に実用的に使えるというわけですね。素晴らしい！
また、pべきで約分できる条件についても、jurupapaさんのブログでご紹介いただいています。


自分の考えた問題をきっかけに行動に移してくださる方が現れて、tsujimotterはとても嬉しいです！
それでは今日はこの辺で！