最小公倍数・最大公約数

Q: 最小公倍数・最大公約数は社会やプログラミングでどのように使われていますか？

RSA暗号の安全性を支える「互いに素」という考え方: 最大公約数の計算（互除法）は、公開鍵暗号方式 RSA の鍵生成において、2つの数が「互いに素」であることを高速に確認するために使われる基礎技術である。素因数分解の困難さと組み合わせて、現代のインターネット通信の暗号化を支えている。

数直線に並ぶ倍数と、ユークリッドの互除法で公約数を探る

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 最小公倍数・最大公約数の本質的な定義と直感的ビジュアルをシミュレーターで体験できる。
2: 公式や証明の背景にある数学的意味と、厳密な導出ステップを解説。
3: 実社会における工学応用（RSA暗号の安全性を支える「互いに素」という考え方）のTypeScript実装コードを収録。

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

最小公倍数・最大公約数の基礎原理を体系化し、抽象的な計算を直感的に扱うために誕生した。

身につく武器・思考力

数直線に並ぶ倍数と、ユークリッドの互除法で公約数を探る。この考え方を身につけることで、複雑な課題を単純化して数理モデルとして解く力が養われる。

実社会・ITでの活躍現場

•RSA暗号の安全性を支える「互いに素」という考え方
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

$a$ と $b$ のスライダーを動かして、2つの数の倍数が数直線上のどこに並ぶか見てみよう。最初に重なる目盛りが最小公倍数（LCM）だ。下の「互除法ステップ」ボタンを押すと、割り算を繰り返して最大公約数（GCD）を求める様子が1ステップずつ表示される。 $a$ 、 $b$ を素数どうしにすると、LCM や GCD はどうなるかな。

周期 A: 4

周期 B: 6

数直線上での倍数ステップの重なり（1〜36）:

A (4刻み):

B (6刻み):

最小公倍数 (LCM)

\text{LCM}(4, 6) = 12

緑色のマスは、周期AとBが同時に重なる共通のタイミングです。

最大公約数 (GCD)

\text{GCD}(4, 6) = 2

両方をぴったり割り切れる最大の正方形・グループの大きさです。

Layer 2 — 定義・受験・証明

定義

最大公約数（GCD）とは、2つ以上の整数に共通する約数のうち最も大きいものである。最小公倍数（LCM）とは、2つ以上の整数に共通する倍数のうち最も小さいものである。 $a$ と $b$ の最大公約数を $\gcd(a, b)$ 、最小公倍数を $\mathrm{lcm}(a, b)$ と書く。

公式・数理モデル

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

証明・導出

最大公約数は「ユークリッドの互除法」で効率よく求められる。これは「 $a$ を $b$ で割った余りを $r$ とすると、 $\gcd(a, b) = \gcd(b, r)$ が成り立つ」という性質を使い、余りが 0 になるまで割り算を繰り返す方法である。

例えば $\gcd(30, 18)$ を求めるとき、

30 = 18 \times 1 + 12,\quad 18 = 12 \times 1 + 6,\quad 12 = 6 \times 2 + 0

余りが 0 になった時点の割る数 $6$ が最大公約数となる。

最小公倍数は、 $a \times b$ の中に共通因数 $\gcd(a,b)$ がちょうど2回分含まれていることから、 $a \times b$ を $\gcd(a,b)$ で1回分だけ割り戻すことで得られる。これが $\mathrm{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$ という関係の理由である。

押さえておきたいポイント

最小公倍数は分数の通分（分母をそろえる）に使われる
最大公約数は分数の約分（もっとも簡単な形にする）に使われる
$\gcd(a,b) \times \mathrm{lcm}(a,b) = a \times b$ が常に成り立つ
$\gcd(a,b) = 1$ のとき、 $a$ と $b$ は「互いに素」であるという

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

RSA暗号の安全性を支える「互いに素」という考え方

最大公約数の計算（互除法）は、公開鍵暗号方式 RSA の鍵生成において、2つの数が「互いに素」であることを高速に確認するために使われる基礎技術である。素因数分解の困難さと組み合わせて、現代のインターネット通信の暗号化を支えている。

1function gcd(a: number, b: number): number {
2  while (b !== 0) {
3    [a, b] = [b, a % b];
4  }
5  return a;
6}
7
8function lcm(a: number, b: number): number {
9  return (a * b) / gcd(a, b);
10}
11
12// RSA鍵生成では、公開指数 e が (p-1)(q-1) と互いに素であることを確認する
13function isCoprime(a: number, b: number): boolean {
14  return gcd(a, b) === 1;
15}
16
17console.log(gcd(30, 18));         // 6
18console.log(lcm(30, 18));         // 90
19console.log(isCoprime(17, 3120)); // true -> e = 17 は鍵の指数として使用可能