二元不定方程式が整数解を持つ

\[ ax+by=c\text{が整数解を持つ}\Leftrightarrow c\text{は}\gcd(a,b)\text{の倍数} \]

\(\Rightarrow\)

\(a=\gcd(a,b)a',b=\gcd(a,b)b'\)とおけるので\(\gcd(a,b)(a'x+b'y)=c\)となり、\(c\)は\(\gcd(a,b)\)の倍数。

\(\Leftarrow\)

\(a=\gcd(a,b)a',b=\gcd(a,b)b',c=\gcd(a,b)c'\)とおくと\(a',b'\)は互いに素なので\(a'x+b'y=1\)は整数解を持つ。
両辺を\(c\)倍すると、\(a(c'x)+b(c'y)=c\)となるがこれも整数解を持つ。

ページ情報
タイトル
二元不定方程式が整数解を持つ
URL
https://www.nomuramath.com/kqw5c78n/
SNSボタン