互いに素と既約分数

方針

解答

⓪ 発想 — どう考え始めるか。 「これ以上約分できない」とは、分子と分母の最大公約数が $1$($=$ 互いに素)ということ。

だから最大公約数で一気に割るのが最短ルートだ。

$$84=2^2\times 3\times 7,126=2\times 3^2\times 7$$

共通するのは $2$($1$ 個ずつ)、$3$($1$ 個ずつ)、$7$($1$ 個ずつ)。

$$\gcd (84,126)=2\times 3\times 7=42$$

$$\frac{84}{126}=\frac{84÷42}{126÷42}=\frac{2}{3}$$

$2$ で割って $\frac{42}{63}$、$3$ で割って $\frac{14}{21}$、$7$ で割って $\frac{2}{3}$ と少しずつ進めてもよいが、途中で「もう終わり」と勘違いしやすい。最大公約数で $1$ 回で割り切るほうが安全である。

分母と分子の最大公約数で割ると、一度で既約分数になる。

$84=2^2\times 3\times 7$、$126=2\times 3^2\times 7$。共通の素因数は $2$ が $1$ 個、$3$ が $1$ 個、$7$ が $1$ 個だから、最大公約数は

$$2\times 3\times 7=42$$

分母・分子を $42$ で割って

$$\frac{84}{126}=\frac{84÷42}{126÷42}=\frac{2}{3}$$

$2$ と $3$ には $1$ 以外の共通の約数がない(互いに素)ので、これ以上は約分できない。これが既約分数だ。

発展 — 一歩先へ。 「互いに素」という関係は、整数論のいたるところで鍵になる。

$1$ から $n$ までのうち、$n$ と互いに素な数の個数を $\phi (n)$(オイラー関数)と書く。たとえば $\phi (12)=4$($1,5,7,11$ の $4$ 個)。

この関数が、現代の暗号(RSA暗号)の心臓部にある。インターネットで買い物ができるのは、「互いに素」という概念のおかげなのだ。

もう $1$ つ、美しい事実を紹介したい。 $2$ つの自然数をランダムに選んだとき、それらが互いに素である確率はいくつだろうか。

答えは

$$\frac{6}{{\pi }^2}\approx 0.608$$

$\pi$ が出てくる。 円周率が、なぜ整数の話に顔を出すのか — この驚きが、数学の醍醐味だろう(証明は大学の解析学と整数論の交差点にある)。

約分という小学校以来の作業の裏に、$\pi$ が潜んでいた。 $\frac{84}{126}$ を $\frac{2}{3}$ に直すたび、私たちはその世界のふちに触れている。

別解

素因数分解をせずに、互除法で最大公約数を求めるルートを見ておこう。大きな数になったとき、この差は決定的になる。

互除法(割り算を繰り返す)。

$$126÷84=1\text{余り}42$$

$$84÷42=2\text{余り}0$$

余りが $0$ になった。そのときの「割る数」$42$ が最大公約数である。

$$\frac{84}{126}=\frac{2}{3}$$

素因数分解をまったくしていない。 割り算 $2$ 回で終わった。

なぜこれで gcd が出るのか。 カギは次の事実だ。

$$126\text{と}84\text{の公約数}=84\text{と}42(\text{余り})\text{の公約数}$$

$126=84+42$ だから、$84$ と $42$ を割り切る数は $126$ も割り切る。逆も同じ。つまり「元の $2$ 数の公約数」と「割る数と余りの公約数」は、まったく同じ集合なのだ。

だから数をどんどん小さくしながら gcd を保てる。大きい数の問題を、小さい数の問題にすり替えていく — これが互除法の心臓部だ。

どちらのルートを選ぶべきか。

• 小さい数($100$ 以下くらい)→ 素因数分解が直感的で速い
• 大きい数($3$ 桁以上、素因数が見えにくい)→ 互除法が圧倒的

たとえば $\frac{319}{377}$ を約分せよ、と言われたら。素因数分解は苦しい($319=11\times 29$ に気づけるだろうか)。しかし互除法なら

$$377÷319=1\text{余り}58,319÷58=5\text{余り}29,58÷29=2\text{余り}0$$

$3$ 回の割り算で $\gcd =29$。約分すると $\frac{11}{13}$ だ。

素因数分解は「難しい」が、最大公約数は「易しい」。 この非対称性は驚くべきことだ。$2$ つの $300$ 桁の数の素因数分解には数万年かかるが、その最大公約数は $1$ 秒未満で求まる。

紀元前 $300$ 年ごろのユークリッドが書き残したこの手続きは、$2300$ 年後の今もコンピュータの中で毎秒動き続けている — 人類最古にして、今なお現役のアルゴリズムである。