最大公約数とユークリッド互除法

最大公約数（GCD）

「12 人と 8 人のグループを、同じサイズの班に均等に分けたい」——12 人も 8 人も余りなく分けられる最大の班のサイズが「12 と 8 の最大公約数（GCD）」です。

2つの正の整数 $a, b$ に共通する約数のうち最大のものを最大公約数（Greatest Common Divisor）といい、 $\gcd(a, b)$ と書きます。

例： $\gcd(12, 8) = 4$

共通の約数（公約数）：1, 2, 4 → 最大は 4——「12 人も 8 人も 4 班に余りなく分けられる」。

ユークリッド互除法

「1200 と 840 の最大公約数を求めるのに、1 から 840 まで全部試すのは大変」—— $\gcd(a, b)$ を求める最も有名なアルゴリズムがユークリッド互除法です。紀元前300年頃の発見で、世界最古のアルゴリズムの一つとされています。

鍵となる等式： $\gcd(a, b) = \gcd(b,\ a \bmod b)$ ——「2 数の GCD は、大きい方を小さい方で割った余りとの GCD に等しい」

証明： $a = bq + r$ （ $r = a \bmod b$ ）とする。

$a$ と $b$ の共通約数は $r = a - bq$ の約数でもある。
$b$ と $r$ の共通約数は $a = bq + r$ の約数でもある。
よって $a,b$ の公約数全体 $=$ $b,r$ の公約数全体。

これを繰り返すとやがて余りが $0$ になり、そのときの割る数が GCD です——「余りがゼロになったら完了」：

gcd(48, 36)
= gcd(36, 48 mod 36) = gcd(36, 12)
= gcd(12, 36 mod 12) = gcd(12, 0)
= 12

長方形の分割で見る

「縦 $a$ 、横 $b$ の長方形を、辺の長さが整数の正方形で隙間なく敷き詰めるときの、最大の正方形の一辺」——これが GCD の幾何学的な意味です。互除法の各ステップは「長方形から正方形を切り取る操作」に対応します。

マウスを左右に動かして $a$ を変えながら、互除法の分割過程を観察してください。

ユークリッド互除法の長方形分割可視化：マウスで a の値を変えよう。長方形を次々と正方形に切り取っていくと、最後に残る正方形の一辺が GCD になる。

var a, b, steps, i, g;
var colors = ['#3b82f6','#8b5cf6','#22c55e','#f97316','#ec4899','#14b8a6','#fbbf24'];

function gcd(x, y) {
while (y !== 0) { var t = y; y = x % y; x = t; }
return x;
}

function getSteps(x, y) {
var res = [];
while (y !== 0) {
  res.push([x, y]);
  var t = y;
  y = x % y;
  x = t;
}
res.push([x, 0]);
return res;
}

function loop() {
ctx.clearRect(0, 0, W, H);

b = 36;
a = 36 + Math.round((mx / W) * 60);
steps = getSteps(a, b);
g = gcd(a, b);

var scale = Math.min((W - 80) / a, 200 / b);
var ox = 40, oy = 50;
var rw = a * scale, rh = b * scale;

// outer rectangle
ctx.strokeStyle = '#475569';
ctx.lineWidth = 2;
ctx.strokeRect(ox, oy, rw, rh);

// draw squares by Euclidean steps
var cx = ox, cy = oy, remA = a, remB = b;
var colorIdx = 0;
var horiz = true; // alternate direction

for (i = 0; i < steps.length - 1 && i < 8; i++) {
  var big = steps[i][0], small = steps[i][1];
  var q = Math.floor(big / small);
  var sqSize = small * scale;

  for (var qi = 0; qi < q && qi < 6; qi++) {
    ctx.fillStyle = colors[colorIdx % colors.length] + '66';
    ctx.fillRect(cx, cy, sqSize, sqSize);
    ctx.strokeStyle = colors[colorIdx % colors.length];
    ctx.lineWidth = 1.5;
    ctx.strokeRect(cx, cy, sqSize, sqSize);
    ctx.fillStyle = '#fff';
    ctx.font = Math.max(9, sqSize/3) + 'px monospace';
    ctx.textAlign = 'center';
    if (sqSize > 18) ctx.fillText(small, cx + sqSize/2, cy + sqSize/2 + 4);
    cx += sqSize;
  }
  // after placing q squares horizontally, move down
  cx = ox;
  cy = oy + (a - (big - q * small)) * scale;
  // simplification: just show the division process in text
  colorIdx++;
}

// Step-by-step text
ctx.fillStyle = '#e2e8f0';
ctx.font = '14px monospace';
ctx.textAlign = 'left';
ctx.fillText('gcd(' + a + ', ' + b + ') の計算:', 20, 18);

var ty = 230;
var ax = a, bx = b;
ctx.font = '13px monospace';
while (bx !== 0) {
  var r = ax % bx;
  ctx.fillStyle = r === 0 ? '#22c55e' : '#94a3b8';
  ctx.fillText(ax + ' = ' + bx + ' × ' + Math.floor(ax/bx) + ' + ' + r, 20, ty);
  ty += 20;
  ax = bx; bx = r;
  if (ty > 320) break;
}
ctx.fillStyle = '#fbbf24';
ctx.font = 'bold 15px monospace';
ctx.fillText('gcd(' + a + ', ' + b + ') = ' + g, 20, ty + 10);

requestAnimationFrame(loop);
}
loop();

ユークリッド互除法の計算量

ユークリッド互除法は非常に高速なアルゴリズムです——「1200 と 840 の GCD を求めるのに、全部試せば 840 回かかるが、互除法なら数回で終わる」。

定理（ラメの定理）： $\gcd(a, b)$ を計算するとき、余りが $0$ になるまでのステップ数は $\log_\phi b$ を超えない（ $\phi = (1+\sqrt5)/2 \approx 1.618$ ）。

言い換えると、ステップ数は $b$ の桁数に比例する $O(\log b)$ ——「数が大きくなっても、桁数が増えるだけなので実用的に速い」。

$a, b$	愚直な全探索	ユークリッド
48, 36	36回試す	2ステップ
1000, 999	999回	3ステップ
$10^6, 10^6-1$	100万回	~20ステップ

拡張ユークリッド互除法

「GCD を求めるだけでなく、 $sa + tb = \gcd(a,b)$ となる整数 $s, t$ も同時に求められる」—— $\gcd(a, b) = d$ のとき、ベズーの等式（Bézout’s identity）が成立します：

$\exists\ s, t \in \mathbb{Z}:\ sa + tb = d$

これを満たす整数 $s, t$ を求めるのが拡張ユークリッド互除法です。

例： $\gcd(48, 36) = 12$

12 = 48 - 1 × 36
   = 48 - 1 × 36
→ s = 1, t = -1  ✓  (1×48 + (-1)×36 = 12)

これは暗号理論（RSA）でモジュラー逆数を求めるときに使われます——「インターネットの安全な通信の根底に、ユークリッドのアルゴリズムがある」。

最大公約数の性質まとめ

性質	式
対称性	$\gcd(a,b) = \gcd(b,a)$
互除法	$\gcd(a,b) = \gcd(b, a \bmod b)$
倍数との関係	$a \mid b \Rightarrow \gcd(a,b) = a$
lcm との関係	$\text{lcm}(a,b) \cdot \gcd(a,b) = a \cdot b$
整数線形結合	$\gcd(a,b) = sa + tb$ （ベズー）

まとめ

GCD：2数の共通約数の最大値。 $\gcd(a,b) = \gcd(b, a \bmod b)$ ——「割った余りと割る数の GCD に等しい」
ユークリッド互除法：余りを繰り返し求める、世界最古のアルゴリズムの1つ——「紀元前から使われている」
計算量は $O(\log \min(a,b))$ ——非常に高速——「桁数が増えても少しのステップで済む」
拡張ユークリッド互除法： $sa + tb = \gcd(a,b)$ の整数解を求められる
暗号・コンピュータサイエンスで頻繁に使用される

次回は素数と素因数分解——整数論の核心に踏み込みます。