完全剰余系と既約剰余系 (1)

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

完全剰余系

$m$ を法とする $m$ 個の剰余類からそれぞれ $1$ つずつ代表元をとって作った $m$ 個の整数の組を, $m$ を法とする完全剰余系という. $m$ 個の整数 $x_{1}$, $x_{2}$, $\ldots$, $x_{m}$ が $m$ を法とする完全剰余系であるためには, そのうちどの $2$ つも $m$ を法として合同でないことが必要十分である.

[命題] $m$ を正の整数とし, $x_{1}$, $x_{2}$, $\ldots$, $x_{m}$ を $m$ を法とする完全剰余系とする. また, $a$ を整数とし, $\gcd(a, m)=1$ を満たすとする. このとき, $ax_{1}$, $ax_{2}$, $\ldots$, $ax_{m}$ も $m$ を法とする完全剰余系である.

[証明] $i$, $j\in \{ 1,2,\ldots,m\}$ とし, $i\neq j$ とする. このとき, もし仮に $$ ax_{i}\equiv ax_{j}\pmod{m} $$ であったとすると, $\gcd(a, m)=1$ であるから, $$ x_{i}\equiv x_{j}\pmod{m}. $$ これは $x_{1}$, $x_{2}$, $\ldots$, $x_{m}$ が完全剰余系であることに反する. ゆえに, $ax_{i}\not\equiv ax_{j}\pmod{m}$. したがって, $ax_{1}$, $ax_{2}$, $\ldots$, $ax_{m}$ は $m$ を法とする完全剰余系である. (証明終)

[定理] $m$, $n$ を正の整数とし, $\gcd(m, n)=1$ であるとする. $x_{1}$, $x_{2}$, $\ldots$, $x_{m}$ を $m$ を法とする完全剰余系, $y_{1}$, $y_{2}$, $\ldots$, $y_{n}$ を $n$ を法とする完全剰余系とする. このとき, $y_{j}m+x_{i}n$ ($1\leq i\leq m$, $1\leq j\leq n$) は $mn$ を法とする完全剰余系である.

[証明] $i$, $i'\in \{ 1,2,\ldots,m\}$, $j$, $j'\in \{ 1,2,\ldots,n\}$ とし, $(i, j)\neq (i', j')$ とする. このとき, もし仮に $$ y_{j}m+x_{i}n \equiv y_{j'}m+x_{i'}n \pmod{mn} $$ であったとすると, $i\neq i'$ の場合, $$ x_{i}n \equiv x_{i'}n \pmod{m}. $$ $\gcd(m, n)=1$ であるから, $$ x_{i} \equiv x_{i'} \pmod{m}. $$ これは $x_{1}$, $x_{2}$, $\ldots$, $x_{m}$ が $m$ を法とする完全剰余系であることに反する. 同様に, $j\neq j'$ の場合, $$ y_{j} \equiv y_{j'} \pmod{n} $$ となり, $y_{1}$, $y_{2}$, $\ldots$, $y_{n}$ が $n$ を法とする完全剰余系であることに反する. ゆえに, $$ y_{j}m+x_{i}n \not\equiv y_{j'}m+x_{i'}n \pmod{mn}. $$ したがって, $y_{j}m+x_{i}n$ ($1\leq i\leq m$, $1\leq j\leq n$) は $mn$ を法とする完全剰余系である. (証明終)

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示