互いに素な整数と合同式：ax + by = 1の意味と解法

整数aとbが互いに素である場合、ax + by = 1という式は、拡張ユークリッドの互除法により整数解(x, y)が存在することを保証します。この考え方は合同算や暗号理論でも重要な基礎となります。

互いに素とベズーの等式

もしgcd(a, b) = 1であれば、整数xとyが存在してax + by = 1を満たします。この等式はベズーの等式と呼ばれ、aの逆元をmod bで求める際の基本です。

ax + by = 1をmod bで考えると、ax ≡ 1 (mod b) となります。ここでxはaのbに対する逆元であり、整数解の一つを選ぶだけで十分です。

xは1/aのように分数で表すわけではありません。整数解は拡張ユークリッド法で求められ、任意の整数kに対してx = x0 + k*b の形で全ての解を表せます。ここでx0は一つの特定解です。

よって、あなたの式「x ≡ 1/a」や「x = bk + 1/a」という考え方は整数の世界では正しくありません。正しくは、ax ≡ 1 (mod b) の整数解xは、拡張ユークリッド法で求められる整数で、すべての解は x = x0 + k*b (kは整数) の形で表されます。