完全剰余系の基本定理

完全剰余系の基本定理
\(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で割った余りは全て異なる。


ページ情報

タイトル

完全剰余系の基本定理

URL

https://www.nomuramath.com/z62udfm7/

SNSボタン