整数論の基本定理
整数論の基本定理
\[ ax+by=1\text{が整数解を持つ}\Leftrightarrow a\text{と}b\text{は互いに素} \]
\[ 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ボタン |
2元1次不定方程式の性質
\[
ax+by=c\text{が整数解を持つ}\Leftrightarrow c\text{は}\gcd(a,b)\text{の倍数}
\]
オイラーのトーシェント関数の定義
\[
\phi(n) =\#\left\{ k\in\mathbb{N};1\leq k\leq n,\gcd(k,n)=1\right\}
\]
完全剰余系の基本定理
\[
1a,2a,3a,\cdots\cdots,na
\]
n番目の素数の式
\[
P\left(n\right)=1+\sum_{k=1}^{2^{n}}\left\lfloor \sqrt[n]{\frac{n}{\sum_{j=1}^{k}\left\lfloor \cos^{2}\left(\frac{\left(j-1\right)!+1}{j}\pi\right)\right\rfloor }}\right\rfloor
\]