ユークリッド互除法
一次不定方程式
\( 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}\]
を考えれば良いです。
ディスカッション
コメント一覧
まだ、コメントがありません