コラム

ベズーの方程式:整数の世界をつなぐ鍵

「ベズーの方程式(ベズーの恒等式)」は、整数の割り算で生まれる余りの性質を、驚くほど強い形で結びつける考え方です。その核心は、二つの整数 a と b(少なくとも片方が 0 でないとします)に対して、最大公約数 d=gcd(a,b) が「a と b の線形結合として」必ず表せる、という事実にあります。具体的には、ある整数 x, y が存在して d=ax+by を成り立たせます。これが「ベズーの方程式(あるいはベズーの恒等式)」と呼ばれるもので、単に式として面白いだけでなく、数論の多くの問題に直接つながる“鍵”の役割を果たします。

まず、この事実がどれほど本質的かを理解するために、最も素朴なところから見てみます。たとえば gcd(a,b) は、a と b の共通の割り切りをすべてまとめ上げた数です。しかし「その gcd が、ax+by という形に具体的に落とし込める」という主張は、それまでのイメージを一段深い次元へ引き上げます。つまり、最大公約数は単に“ある数の性質”として存在するのではなく、「a と b を整数倍して足し引きした結果」として“具体的に構成できる”のです。しかも x, y は整数でなければならず、そこが数論ならではの面白さでもあります。

このベズーの恒等式は、ユークリッドの互除法と密接に結びついています。互除法は、大小関係にある数の差や余りを繰り返し計算することで gcd を見つける手続きですが、実はその途中で得られる余りをたどり直せば、最終的な gcd がどのように a と b の線形結合で表されるかまで追跡できます。言い換えると、互除法は「gcd を求めるだけ」ではなく、「ベズー係数 x, y を計算するための機械」でもあります。ここで重要なのは、存在を主張するだけでなく、実際に作れるところです。計算を行うことで、具体的な x, y を得られ、以後の問題解決に利用できます。

ベズーの方程式が強力なのは、その結果が「連立方程式の可解性」と直結するからです。たとえば、ax+by=c という方程式を考えたとき、常に解があるわけではありません。けれどもベズーの恒等式の観点に立てば、どんな c のときに解が存在するかが明確になります。結論としては、ax+by=c が整数解をもつのは c が gcd(a,b) の倍数であるときに限られます。これは一見すると単なる“条件”ですが、その背景には次の論理があります。もし解があるなら c は ax+by により a と b の共通の割り切りを持つので gcd(a,b) を含まざるを得ません。逆に c が gcd の倍数なら、ベズーの恒等式で得た ax0+by0=d を使い、x=x0·(c/d), y=y0·(c/d) のようにスケールすればよいので解が構成できます。存在条件が最大公約数に還元されるという点が、ベズーの方程式の“数論としての統一感”を生み出しています。

さらに興味深いのは、ベズーの方程式が「合同式」や「逆元(モジュラー逆数)」の理論へ橋をかけることです。たとえば、mod m のもとで数 a の逆元が存在するかどうかを考えるとき、条件は gcd(a,m)=1 です。しかも逆元が存在するだけでなく、ベズーの恒等式によってその逆元そのものが求まります。実際、gcd(a,m)=1 なら、ax+my=1 を満たす整数 x が存在し、この x が(mod m における)a の逆元になります。この関係は、暗号の世界でも非常に重要です。RSA などの公開鍵暗号の基礎では、ユークリッドの互除法でベズー係数を計算し、モジュラー逆数を得る工程が現れます。つまりベズーの方程式は、「純粋数学として美しい」だけでなく、「情報処理に必要な計算の中核」としても働いているのです。

また、ベズーの方程式は「解の構造」まで教えてくれます。ax+by=c が解をもつとき、解は一つで終わらず無数に広がります。ベズーの恒等式をベースにすると、特定の一組の解を見つけた後、そこから一般解が書き下せます。たとえば d=gcd(a,b) として c が d の倍数なら解が存在し、ある解(x0,y0)があるとき、あとは x をある整数 t によって x=x0+(b/d)t、y=y0−(a/d)t のように動かすことで、すべての解が得られます。この「解が等間隔に並ぶ」感覚は、一次のディオファントス方程式の幾何学的な見方(格子点や直線の交わり)とも相性が良く、整数の世界が連続的な図形感覚とも結びついていることを実感させます。

このように見てくると、ベズーの方程式の面白さは、単に「最大公約数が作れる」という一点にとどまりません。互除法という手続き、合同式という枠組み、逆元という概念、解の一般形という構造、そして暗号計算という応用まで、一本の糸でつながっているのです。しかもその糸は“整数”という制約の中で太くなっていきます。実数の世界なら線形方程式はいつでも自由に解ける場合が多いのに対して、整数の世界では「解があるかどうか」「どのように増殖するか」が格段に繊細になります。ベズーの方程式は、その繊細さを最大公約数という最小限の情報に圧縮してくれるため、数学的にも計算的にも非常に扱いやすいのです。

もしこのテーマをさらに掘り下げるなら、拡張ユークリッドの互除法(ベズー係数を計算するアルゴリズム)を追ってみると理解が一気に深まります。互除法の余りの列が、いつの間にか x と y の係数へ変換されていく過程は、手続きと理論が一体になっている感覚を与えてくれます。また、ディオファントス方程式全般への展開、ガウス記号やユークリッド互除法の一般化、さらには整数論の大きな定理(たとえば線形合同式の体系)に触れていくと、ベズーの方程式が“入口”ではなく“中心部の道標”であることがわかってきます。

結局のところ、ベズーの方程式は「整数の間に隠れている連携」を表に引き出す道具です。最大公約数という“共通の割り切り”が、具体的に ax+by という形で現れ、さらに c がその倍数かどうかで解の存在が決まり、合同式では逆元が作られ、解の全体像まで記述できる。こうした性質の連鎖は、数論が持つ美しさと実用性を同時に感じさせてくれます。整数の世界を扱う限り、ベズーの方程式は何度でも立ち戻りたくなる、確かな土台になっているのです。