二元不定方程式が整数解を持つ
\[
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ボタン |
オイラーの規準
\[
QR(a,p)\overset{p}{\equiv}a^{\frac{p-1}{2}}
\]
オイラーのトーシェント関数の定義
\[
\phi(n) =\#\left\{ k\in\mathbb{N};1\leq k\leq n,\gcd(k,n)=1\right\}
\]
オイラーのトーシェント関数の性質
\[
\phi(p^{n})=p^{n}-p^{n-1}
\]
2元1次不定方程式の整数解とユークリッドの互除法
\[
ax+by=c
\]