ykm11.hatenablog.com に関係する話。
前提として、\(\frac{a}{b}, \frac{c}{d} \)は既約分数である。 つまり\(GCD(a, b) = GCD(c, d) = 1 \)。(GCD(X,Y)はXとYの最大公約数)
prop.
上の前提の元、\(GCD(b, d) = 1\) ならば\(GCD(ad + bc, bd) = 1\)である。
proof.
\(GCD(ad + bc, bd) =:t \neq 1\)と仮定する。 公約数の定義より、
\(t|(bd)かつt|(ad + bc)\)である。
また、bとdが互いに素であるため、\(t|b, t|d \)のどちらかが成立する。
\(t|b\)のとき
\(t|(ad + bc) \Rightarrow t|(ad)\)である。
しかし、\(GCD(a, b) = GCD(b, d) = 1 \Rightarrow t =1\)となり、仮定と矛盾する。よって、\(GCD(ad + bc, bd) = 1\)\(t|d\)のとき
\(t|b\)と同様に、\(GCD(ad + bc, bd) = 1\)が示せる。
証明終了。
この証明は、既約分数(ここが重要)を足し算するとき、分母同士が互いに素であれば計算結果は既約分数になるということを示すものである。60%どころではない。
なお、mpq_tは値をセットする際に約分してくれないので、既約分数になっているかどうか、プログラマが気をつける必要がある。
ex) こういうのは良くない
#include <iostream> #include <gmpxx.h> int main() { mpq_class x("2/4", 10); // ちゃんと既約分数で初期化しろ!! std::cout << &x.get_mpq_t()->_mp_num << std::endl; std::cout << &x.get_mpq_t()->_mp_den << std::endl; }
実行結果
2 4