ユークリッドの互除法
ユークリッドの互除法
2つの自然数\(a,b(b\leq a)\)について、\(a\)を\(b\)で割った余りを\(r\)とすると、
\[ \gcd(a,b)=\gcd(b,r) \] となる。
2つの自然数\(a,b(b\leq a)\)について、\(a\)を\(b\)で割った余りを\(r\)とすると、
\[ \gcd(a,b)=\gcd(b,r) \] となる。
\(a\)を\(b\)で割った商を\(q\)とすると、
\(a=qb+r\)
と表される。
\(a=qb+r\)
と表される。
\(\gcd(a,b)\leq\gcd(b,r)\)の証明
\(a\)と\(b\)の公約数を\(g\)とすると\(a=ga'\)、\(b=gb'\)となるので、\(r=a-qb=g(a'-qb')\)となり、\(g\)は\(r\)の約数になる。これより、\(a\)と\(b\)の公約数ならば\(b\)と\(r\)の公約数であるので\(\gcd(a,b)\leq\gcd(b,r)\)となる。\(\gcd(a,b)\geq\gcd(b,r)\)の証明
\(b\)と\(r\)の公約数を\(h\)とすると\(b=hb'\)、\(r=hr'\)となるので、\(a=qb+r=h(qb'+r')\)となり、\(h\)は\(r\)の約数になる。これより、\(b\)と\(r\)の公約数ならば\(a\)と\(b\)の公約数であるので\(\gcd(a,b)\geq\gcd(b,r)\)となる。-
これより、\(\gcd(a,b)=\gcd(b,r)\)となる。ページ情報
| タイトル | ユークリッドの互除法 |
| URL | https://www.nomuramath.com/ydzsipsx/ |
| SNSボタン |
整数論の基本定理
\[
ax+by=1\text{が整数解を持つ}\Leftrightarrow a\text{と}b\text{は互いに素}
\]
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
\]
二元不定方程式が整数解を持つ
\[
ax+by=c\text{が整数解を持つ}\Leftrightarrow c\text{は}\gcd(a,b)\text{の倍数}
\]
位数と原始根の定義
\[
a^{n}\overset{p}{\equiv}1
\]