2元1次不定方程式の性質

2元1次不定方程式の性質
\[ ax+by=c\text{が整数解を持つ}\Leftrightarrow c\text{は}\gcd(a,b)\text{の倍数} \]

\(\Rightarrow\)

\(a=a'\gcd(a,b)\)、\(b=b'\gcd(a,b)\)と表されるので左辺は\(\gcd(a,b)(a'x+b'y)\)となり左辺\(c\)も\(\gcd(a,b)\)の倍数となる。

\(\Leftarrow\)

\(c=c'\gcd(a,b)\)と表されるので、\(a=a'\gcd(a,b)\)、\(b=b'\gcd(a,b)\)とおくと\(a'\)と\(b'\)は互いに素となり、与式は\(a'x+b'y=c'\)となる。
両辺を\(c'\)で割ると\(a'(x/c')+b'(y/c')=1\)となり、\(a'X+b'Y=1\)の不定方程式の解\((X,Y)\)を\(c'\)倍すればそれが解となる。

ページ情報
タイトル
2元1次不定方程式の性質
URL
https://www.nomuramath.com/l27il0dz/
SNSボタン