完全剰余系の基本定理
完全剰余系の基本定理
\(a,n\in\mathbb{Z}\)が互いに素であるとき、\(1a,2a,3a,\cdots\cdots,na\)をnで割った余りは全て異なる。
\(a,n\in\mathbb{Z}\)が互いに素であるとき、\(1a,2a,3a,\cdots\cdots,na\)をnで割った余りは全て異なる。
\(1a,2a,3a,\cdots\cdots,na\)から任意の2数\(ia,ja(1\leq i<j\leq n)\)を選ぶ。
このとき\(ia,ja\)を\(n\)で割った値が等しいと仮定する。
\(ja-ia=(j-i)a\)は\(n\)で割りきれるはずだが、\(1\leq j-i\leq n\)であり、\(j-i\)と\(a\)は互いに素なので\((j-i)a\)は\(n\)で割りきれない。
故に矛盾となり、nで割った余りは全て異なる。
このとき\(ia,ja\)を\(n\)で割った値が等しいと仮定する。
\(ja-ia=(j-i)a\)は\(n\)で割りきれるはずだが、\(1\leq j-i\leq n\)であり、\(j-i\)と\(a\)は互いに素なので\((j-i)a\)は\(n\)で割りきれない。
故に矛盾となり、nで割った余りは全て異なる。
ページ情報
| タイトル | 完全剰余系の基本定理 |
| URL | https://www.nomuramath.com/z62udfm7/ |
| SNSボタン |
二元不定方程式
\[
ax+by=c
\]
二元不定方程式が整数解を持つ
\[
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\}
\]
(*)平方剰余の相互法則と補充法則
\[
QR(p,q)QR(q,p)=\left(-1\right)^{\frac{p-1}{2}\frac{q-1}{2}}
\]