ユークリッド互除法

一次不定方程式

\( ax + by = 1\)

整数 \( a, b, n \) に次の一次不定方程式を満たす整数 \( x, y \) を求めます。

\[ ax + by = 1\]

ここで、\( a., b \) の最大公約数を \( g \) とします。このとき、上式は、互いに素な整数 \( p, q \) を用いて

\[ g(px + qy) = 1\]

となるので、\( g = 1 \) である必要があります。ここで \( g = 1 \) のとき、つまり、\( a, b\) が互いに素であるとき、 \( x, y \) が存在するかを考えます。ここで、自然数 \( k \) を用いて、\( ka \) が \( b \) と互いに素であるような \( k \) の最大値は、\( k = b – 1 \) であり、

\[ ka \bmod b \ (1 \leq k \leq b – 1) \]

の値は、 \( 1, 2, \cdots , b – 1 \) の \( b – 1 \) 通りあります。もし、\( b – 1 \) 通りないとすると、

\[ ka \bmod b = ta \bmod b\]

を満たす自然数 \( k, t \ (k < t \wedge 1 \leq k, t \leq b – 1) \) が存在するので、\( (t – k) a \) は \( b \) の倍数となりますが、\( a, b \) は互いに素であり、\( 1 \leq t – k < b – 1 \) なので矛盾します。したがって、\( ka \bmod b = 1 \) となるような自然数 \( k \) が存在し、

\[ ka = bt + 1\]

を満たす整数 \( t \) が存在します。したがって、

\[ ka – bt = 1\]

より、\( (x, y) = (k, -t) \) という解が存在します。

\( ax + by = n \)

整数 \( a, b, n \) に次の一次不定方程式を満たす整数 \( x, y \) を求めます。

\[ ax + by = n\]

\( a, b \) の最大公約数を \( g \) とします。このとき、上式は、互いに素な整数 \( p, q \) を用いて、

\[ g(px + qy) = n\]

となるので、\( n \) は \( g \) の倍数である必要があります。したがって、整数 \( r \ (n = gr)\) を用いて、

\[ px + qy = r\]

という一次不定方程式を考えれば良いです。\( ax + by = 1 \) の議論から、\( px + qy = 1 \) は整数解 \( x, y\) が存在するので、その解を \( (x, y) = (x_0, y_0) \) とすると、

\begin{eqnarray}
px_0 + qy_0 &=& 1\\
p(rx_0) + q(ry_0)&=& r
\end{eqnarray}

より、\( ax + by = n \) の解は、\( (x, y) = (rx_0, ry_0) \) となります。

一次合同方程式

解の存在

自然数 \( a, b, n \) として、次の一次合同方程式を満たす整数 \( x \) を求めます。

\[ ax \bmod b = n\]

\( (ax – n) \bmod b = 0 \) より、\( ax -n \) は \( b \) の倍数となります。したがって、

\begin{eqnarray}
ax – n &=& by\\
ax – by &=& n
\end{eqnarray}

を満たす整数 \( x, y \) を求めます。\( ax + by = n \) の議論から、\( n \bmod \gcd(a, b) = 0 \) であるとき、\( ax – by = n\) を満たす \( x, y \) が存在します。

性質

\[ ax \bmod b = n\]

\( g = \gcd(a, n) \) とし、\( b \bmod g = 0 \) であり、\( g \neq 1 \) のときを考えます。\( ax – n = by \) から

\begin{eqnarray}
ax – n &=& by\\
gpx – gr &=& gqy \\
px – r &=& qy
\end{eqnarray}

となるので、

\[ \dfrac{a}{g} \bmod \dfrac{b}{g} = \dfrac{n}{g}\]

を考えれば良いです。

参考

数学

Posted by ヤマカサ