最大公約数・最小公倍数

方針

解答

⓪ 発想 — どう考え始めるか。 最大公約数(gcd)と最小公倍数(lcm)は、素因数分解して指数を見比べると一発だ。

$$48=2^4\times 3,60=2^2\times 3\times 5$$

• 最大公約数: 両方が持っている素因数を、少ないほうの個数だけとる
• 最小公倍数: どちらかが持っている素因数を、多いほうの個数だけとる

$2$ は $4$ 個と $2$ 個 → gcd では $2^2$、lcm では $2^4$。$3$ は $1$ 個ずつ → どちらも $3^1$。$5$ は $60$ だけ → gcd には入らない、lcm には $5^1$。

$$\gcd =2^2\times 3=12,\mathrm{lcm}=2^4\times 3\times 5=240$$

「共通のものだけ・少ないほう」が gcd、「全部・多いほう」が lcm。 迷ったら指数を並べて書く。

$48=2^4\times 3$、$60=2^2\times 3\times 5$ と素因数分解する。

(1) 各素因数の指数を見比べる。

最大公約数(共通して持てる分=指数の小さいほう):$2$ は $2$ 個、$3$ は $1$ 個、$5$ は片方にしかないので $0$ 個。よって

$$2^2\times 3=12$$

最小公倍数(どちらも割り切る最小の数=指数の大きいほう):$2$ は $4$ 個、$3$ は $1$ 個、$5$ は $1$ 個。よって

$$2^4\times 3\times 5=240$$

(2)

$$12\times 240=2880,48\times 60=2880$$

まとめ:確かに等しい。これは偶然ではない。どの素因数も『小さいほうの指数 $+$ 大きいほうの指数 $=$ 元の2数の指数の和』になるから、$(\text{最大公約数})\times (\text{最小公倍数})=(2\text{数の積})$ はいつでも成り立つ。

発展 — 一歩先へ。 最小公倍数は、身のまわりで意外なほど活躍する。

歯車。 歯数 $48$ と $60$ の $2$ つの歯車がかみ合って回るとき、最初と同じ歯どうしが再び出会うのは、$\mathrm{lcm}(48,60)=240$ 個の歯が噛み合ったとき。小さい歯車は $240÷48=5$ 回転、大きいほうは $240÷60=4$ 回転している。

うるう年・カレンダー。 「同じ曜日・同じ日付」が戻ってくる周期も、$7$ と $365$(や $366$)の絡んだ公倍数の問題だ。

セミ。 北アメリカには $13$ 年ゼミと $17$ 年ゼミがいる。どちらも素数年なのは偶然だろうか。もし周期が $12$ 年なら、$2,3,4,6$ 年周期の天敵と頻繁に鉢合わせしてしまう。素数なら、天敵との出会いの周期(最小公倍数)が最大になる — $13$ と $17$ が同時に地上に出るのは、$\mathrm{lcm}(13,17)=221$ 年に $1$ 度だけだ。

進化が、最小公倍数を計算していたという説である(異説もあるが、魅力的な見方だ)。

歯車の噛み合い、暦の巡り、生物の生存戦略 — 「いつ再び出会うか」という問いのあるところ、必ず最小公倍数がいる。数学は、世界の周期を記述する言語なのだ。

別解

(2)で確かめた $\gcd \times \mathrm{lcm}=48\times 60$ という関係は、偶然ではない。 なぜ必ず成り立つのかを見抜けば、この式は「暗記する公式」から「当たり前の事実」に変わる。

指数を表にして並べる。

ここで、いちばん右の $2$ 列に注目してほしい。

$2$ の行: gcd の指数 $2$ と lcm の指数 $4$。足すと $2+4=6$。 一方、元の $2$ つの数の指数は $4$ と $2$。足すと $4+2=6$。

同じだ。

$5$ の行: gcd が $0$、lcm が $1$ → 和は $1$。元は $0$ と $1$ → 和は $1$。やはり同じ。

当たり前である。 $2$ つの数 $a$、$b$ について、小さいほう(min)と大きいほう(max)を足せば、必ず元の $2$ つの和になるからだ。

$$\min (a,b)+\max (a,b)=a+b$$

($a\leqq b$ なら $\min =a$、$\max =b$ で、和は $a+b$ — 当然。)

だから、すべての素因数について指数の和が保たれる。 指数の和が同じということは、掛け算の結果が同じということ。

$$\gcd (48,60)\times \mathrm{lcm}(48,60)=48\times 60$$

$\min$ と $\max$ を足せば元に戻る — たったこれだけの事実が、この美しい公式の正体だった。

実用上、この関係は非常に強力である。

$$\mathrm{lcm}(a,b)=\frac{a\times b}{\gcd (a,b)}$$

lcm は、gcd さえ分かれば割り算 $1$ 回で出る。 そして gcd は、素因数分解しなくても互除法で高速に求められる(後で学ぶ)。

大きな数ほど、この道が効く。 たとえば $\mathrm{lcm}(319,377)$ を素因数分解で求めるのは骨が折れるが、互除法で $\gcd =29$ と分かれば

$$\mathrm{lcm}=\frac{319\times 377}{29}=\frac{120263}{29}=4147$$

素因数分解を一切せずに、最小公倍数が出た。 「gcd を先に、lcm は割り算で」— これが実戦の手順である。

なお、$3$ つ以上の数ではこの公式は成り立たない($\gcd (a,b,c)\times \mathrm{lcm}(a,b,c)\ne abc$ が普通)。$2$ 数限定の関係だと覚えておきたい。