Skip to content

拡張ユークリッドの互除法

概要

下記のような 1 次不定方程式の整数解を求めるためにユークリッドの互除法を活用する方法

\[ ax + by = c \]

上記のような方程式が解を持つのは下記のような条件のときになる。

\(a, b, c\) を 0 以外の整数とする。一次不定方程式 \(ax+by=c\) が整数解をもつ必要十分条件は \(c\) が \(\textrm{gcd}(a, b)\) で割り切れることである。

証明 (略証)

まず \(d=\textrm{gcd}(a, b)\) とする。この時 \(ax+by\) も \(d\) で割り切れることから \(c\) も \(d=gcd(a, b)\) で割り切ることができる。
逆に \(c\) が \(\textrm{gcd}(a, b)\) で割り切れるとき、\(c=c\prime \times \textrm{gcd}(a, b)\) と置くことができるため、\(ax+by=c\prime\times gcd(a, b)\) となる。
実は \(ax+by=\textrm{gcd}(a, b)\) となる整数対して \(x\prime, y\prime\) が存在するため、そのような \(x\prime, y\prime\) に対して両辺に \(c\prime\) をかけてやれば、\(a(c\prime x\prime) + b(c\prime y\prime)=c\prime \times \textrm{gcd}(a, b) = c\) になり、\((c\prime x\prime, c\prime y\prime)\) が整数解となる。

具体例

具体例として下記の方程式の解を求める。

\[ 111x+30y=12 \]

\(\textrm{gcd}(111, 30)=3\) なので、まずは \(111x+30y=3\) となる \(x, y\) を求める。\(\textrm{gcd}(111, 30)\) では以下のように計算される。

  1. \(111 \div 30 = 3 余り 21 \quad (21=111-3\times 30)\)
  2. \(30\div 21=1余り9 \quad (9=30-1\times 21)\)
  3. \(21\div 9=2余り3 \quad (3=21-2\times 9)\)
  4. \(9\div 3=3\)

これを逆に辿ると

\[\begin{split} 3 &=21 - 2 \times 9 \\ &=21 - 2 \times (30 - 1\times 21) \\ &=-2\times 30 + 3 \times 21 \\ &=-2 \times 30 + 3 \times (111 - 3 \times 30) \\ &=3\times111 + (-11) \times 30 \end{split}\]

\((x, y)=(3, -11)\) が \(111x+30y=3\) の解となるのでこれを4倍した \((x, y)=(12, -44)\) が求める解となる。

一般解

\[\begin{split} 111x + 30y &= 12 \\ 12 \times 111 + (-44)\times 30 &= 12 \end{split}\]

上記を辺々引くと

\[\begin{split} 111(x-12) + 30(y+44) &= 12 \\ 37(x-12) &= -10(y+44) \end{split}\]

37, 10は互いに素であるため\((x-12)\)は10の倍数となる。そのため\(t\)を任意の整数として \(x-12=10t\) のようにあらわすことができる。これを代入すれば\(y\)も\(t\)を使って表すことができる。
そのため一般解は \((x, y) = (10t + 12, -37t - 44)\) となる。

アルゴリズム

\(ax+by=\textrm{gcd}(a, b)=d\) を求めるアルゴリズム

まず普通のアルゴリズムと同様に\(a\)を\(b\)で表して

\[a=qb+r\]

とする。これをもとの方程式に代入すると

\[(qb+r)x+by=d \Leftrightarrow b(qx+y)+rx=d\]

となる。これによって \(a, b\) に関する問題が、より値の小さい \((b, r)\) に関する問題に帰着できた。
これを再帰的に解くのが拡張ユークリッドの互除法になる。 

# ax + by = gcd(a, b) = d となる d, x, yを返す
def extGCD(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return (a, 1, 0)

    # a = qb + r => rx + b(qx + y) = d
    q, r = a // b, a % b
    d, y, x = extGCD(b, r)
    y -= q * x

    return (d, x, y)

参考