ちりもつもればミルキーウェイ

好奇心に可処分時間が奪われる

ベズーの等式

数学

はじめに

これは RSA完全理解 Advent Calendar の7日目の記事です

RSAにおける秘密鍵の生成である $ed \equiv 1\pmod {(p-1)(q-1)}$ を理解するための一環として、前回はユークリッド互除法について説明しました。

今回はベズーの等式と、関連する定理について説明しようと思います。
次回はユークリッド互除法をつかったベズーの等式の解の探索について解説するので、次回まで読めばユークリッド互除法との関連などもわかるわかるので合わせて読むと理解の助けになるかもです。

それではやっていきます

ベズーの等式とは

$a, b$ を0でない整数としたとき、 $ax + by = d$ が解を持つ
$\iff$ $d$ は $gcd(a, b)$ の倍数

という定理。ベズーの補題とも言ったりします

$\iff$ はどちらかが成立するとどちらか一方の必要十分条件をみたす！(つまりもう片一方もなりたつ)という意味です。

なのでこれは

$ax + by = d$ が整数解をもつ $\implies$ $d$ は $gcd(a, b)$ の倍数
$d$ が $gcd(a, b)$ の倍数 $\implies$ $ax + by = d$ が整数解をもつ

という2つのことを言っています

必要な定理の証明

さっそくベズーの等式の証明入っていきたいところなんですが、実はベズーの等式の証明に使いたい定理があるので、そっちを先に証明します

$ax + by = 1$ が整数解をもつ $\iff$ $a, b$ は互いに素

方針としては $\implies$ と $\impliedby$ のどっちも成立することを確認して証明とします

$ax + by = 1$ が整数解をもつ $\implies$ $a, b$ は互いに素

対偶をとって $a, b$ は互いに素でない $\implies$ $ax + by = 1$ が整数解をもたないについて考えます

$a, b$ が素ではないので $gcd(a, b) \geq 2$ $a, b$ はそれぞれ

$a=m(gcd(a, b))$
$b=n(gcd(a, b))$

とかけるから、少なくとも2以上の数の倍数としてあらわせる。
そうしたときに

$ax + by$

の式を考えると、 $ax$ も $by$ もともに $d$ の倍数なので、その解は $d$ の倍数となるはず。したがって $gcd(a, b) \geq 2$ から $ax, by$ はすくなくとも2以上の数の倍数なので、

$ax + by = 1$ となる整数解 $x, y$ は存在しない

$a, b$ は互いに素 $\implies$ $ax + by = 1$ が整数解をもつ

$a, b$ が互いに素なとき $a,2a,3a,...(b−1)a$ に対して $b$ で剰余を取るとすべて異なるという性質を利用して成り立つことを確認します。
(詳細はこちらで証明してるので興味あるかたは合わせてご確認ください)

$b$ の0以外の剰余がすべて登場するため、どこかに余りが1となるような $ia \div b = j \ ... \ 1$ を満たす $i, j$ が存在します。これを $a$ について整理すると

$ia = bj + 1$ さらに整理して $ia - bj = 1$

となるため $i, -j$ が $ax + by = 1$ の整数解となっています

どちらについても成り立つことが確認できたので $ax + by = 1$ が整数解をもつ $\iff$ $a, b$ は互いに素が証明できました

証明

さて、必要な定理が理解できたのでベズーの等式の証明にもどります。
さきほどの定理の証明と同じく

$ax + by = d$ が整数解をもつ $\implies$ $d$ は $gcd(a, b)$ の倍数
$d$ が $gcd(a, b)$ の倍数 $\implies$ $ax + by = d$ が整数解をもつ

の2つの内容についてそれぞれ成り立つことを確認して証明とします。

$ax + by = d$ が整数解をもつ $\implies$ $d$ は $gcd(a, b)$ の倍数

$a, b$ は $gcd(a, b)$ を用いて

$a = m(gcd(a, b))$
$b = n(gcd(a, b))$

と書けるのでそれぞれ $gcd(a, b)$ の倍数
$ax + by = d$ についても同様に $gcd(a, b)$ をつかってあらわすと

$m(gcd(a, b))\cdot x + n(gcd(a, b))\cdot y = d$

となるので $d$ は $gcd(a, b)$ の倍数である

$d$ が $gcd(a, b)$ の倍数 $\implies$ $ax + by = d$ が整数解をもつ

$a, b$ について、最大公約数が $gcd(a, b)$ だから、これ以上の公約数は存在しない。
よって

$a = gcd(a, b)\cdot p$
$b = gcd(a, b)\cdot q$

となる互いに素な $p, q$ がある。
ここでさきほど証明した定理 $ax + by = 1$ が整数解をもつ $\iff$ $a, b$ は互いに素から、

$pi+qj=1$

は整数解を持つことがわかる。 $a, b$ の関係性を表すために両辺を $gcd(a, b)$ でかけると

$gcd(a, b)\cdot pi + gcd(a, b)\cdot qj = gcd(a, b)$

$a = gcd(a, b)\cdot p$ , $b = gcd(a, b)\cdot q$ より整理すると

$ai + bj = gcd(a, b)$

が得られる。このとき $i, j$ が $ax + by = gcd(a, b)$ を満たす解であり、また右辺が $gcd(a,b)$ の倍数であれば $i, j$ を同じだけかければ解がえられる

よって $ax + by = d$ がなりたつ

どちらも成り立つことが確認できたので証明終了