7298／5963 を約分せよ

◯　7298／5963 を約分して、既約分数にしてください。

約分するには分母と分子の公約数で割ればいいんですね。でも、どうでしょうか。7298 と 5963 の公約数を探せるでしょうか。
　なにくわ（7298）ぬ顔でこんな数を出してみましたが、2 で割で割れるか、3 で割れるかと順に探していく方法ではたぶん苦労するでしょう。ごくろうさん（5963）なことです。
　では、どうするか、というと、ユークリッドの互除法の出番です。ユークリッドの互除法とは、

　a を b で割ったときの余りを r とするとき、
「a と b の最大公約数」と「b と r の最大公約数」は一致する

というもの。これを繰り返して使うことで、２つの自然数の最大公約数（GCD）が簡単に求められます。

7298 ÷ 5963 ＝ 1 … 1335　より　gcd（7298 , 5963）＝ gcd（5963 , 1335）
5963 ÷ 1335 ＝ 4 … 623　　　　　　　　　　　　　　 ＝ gcd（1335 , 623）
1335 ÷ 623 ＝ 2 … 89　　　　　　　　　　　　　　　＝ gcd（623 , 89）
623 ÷ 89 ＝ 7 … 0　　　　　　　　　　　　　　　　　＝ 89

要は「a を b で割ったときの余り r を求める作業を、数字をずらしながら、余りが 0 になるまで続ける」わけです。そして余りが 0 になったときの「割られる数」、上の例でいうと「89」が求める最大公約数です。
　約数だから 89（やく）。それはそうと、89 は素数ですから、やみくもに公約数を探そうとしても四苦八苦（89）するでしょう。
　もとい。最大公約数が求まったところで、次に約分ですね。

7298 ÷ 89 ＝ 82
5963 ÷ 89 ＝ 67

というわけで、答えは 7298／5963 ＝ 82／67 です。おぉっとここで、またまた発見。

5963 ＝ 67 × 89

67 も 89 も素数です。つまり 5963 を素因数分解すると 67 × 89 になるんです。まぁなんとも味があると思いませんか。「むな（67）しい、やく（89）ぶん」とか言うなかれ。

7298／5963 を約分せよ　　Ruby・JS で素因数分解する

---

◇　好きな数字（→ https://www.facebook.com/Takeshi.Omori/posts/2279902348962167 ）