整数論の基本定理

整数論の基本定理

\[ ax+by=1\text{が整数解を持つ}\Leftrightarrow a\text{と}b\text{は互いに素} \]

\(\Rightarrow\)

待遇をとる。
\(a\)と\(b\)が互いに素でないなら\(a=a'd,b=b'd\)と表される。このとき不定方程式は\(d(a'x+b'x)=1\)となり左辺は\(d\)の倍数になるので解が存在しない。

\(\Leftarrow\)

\(1a,2a,3a,\cdots\cdots,ba\)を\(b\)で割った値は全て異なるので、\(b\)で割ったとき、余りが\(1\)となるものが存在するのでそれを\(ka\)とし、商を\(q\)とする。
このとき、\(ka=qb+1\)と表される。これを変形すると\(ak+b(-q)=1\)となるので\((k,-q)\)が一つの解となる。

ページ情報

タイトル

整数論の基本定理

URL

https://www.nomuramath.com/bupa3p8x/

SNSボタン