スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

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

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

既約剰余系

[命題] $m$ を正の整数とするとき, $m$ を法とする $1$ つの剰余類に属する整数は, すべて $m$ と互いに素であるか, すべて互いに素でないかのどちらかである.

[証明] $x$, $y$ を同一の剰余類に属する任意の整数とする. すなわち, $x\equiv y\pmod{m}$ であるとする. このとき, ある整数 $t$ が存在して, $x=y+mt$ と表せる. すると, $$ \gcd(x, m) = \gcd(y+mt, m) = \gcd(y, m) $$ であるから, $$ \gcd(x, m) = 1 \Longleftrightarrow \gcd(y, m) = 1 $$ が成り立つ. (証明終)

正の整数 $m$ に対して, $1$ から $m$ までの整数のうち $n$ と互いに素なものの個数を $\varphi(m)$ で表す. こうして定まる関数 $\varphi(m)$ を Euler 関数という.

$m$ を法とする剰余類の中で $m$ と互いに素な整数のみを含むものを, $m$ を法とする既約剰余類という. $m$ を法とする既約剰余類は $\varphi(m)$ 個ある. $m$ を法とする完全剰余系をなす $m$ 個の整数の中から既約剰余類を代表する $\varphi(m)$ 個だけをとったものを, $m$ を法とする既約剰余系という.

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

[証明] 任意の $i$, $j\in \{ 1,2,\ldots,s\}$ に対して, $i\neq j$ ならば $ax_{i}\not\equiv ax_{j}\pmod{m}$ が成り立つことは, 完全剰余系のときと同様にして示せる. また, $\gcd(a, m)=1$ であるから, 各 $i$ に対して, $\gcd(x_{i}, m)=1$ ならば $\gcd(ax_{i}, m)=1$. したがって, $ax_{1}$, $ax_{2}$, $\ldots$, $ax_{m}$ は $m$ を法とする既約剰余系である. (証明終)

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

[証明] 任意の $i$, $i'\in \{ 1,2,\ldots,m\}$, $j$, $j'\in \{ 1,2,\ldots,n\}$ に対して, $$ (i, j)\neq (i', j') \Longrightarrow y_{j}m+x_{i}n \not\equiv y_{j'}m+x_{i'}n\;(\mathop{\mathrm{mod}}mn) $$ が成り立つことは完全剰余系のときと同様にして示せる. $\gcd(m, n)=1$ であるから, 各 $(i, j)$ に対して, \begin{align*} &\gcd(x_{i}, m)=\gcd(y_{j}, n)=1 \\ &\quad\Longrightarrow \gcd(x_{i}n, m) = \gcd(y_{j}m, n) = 1 \\ &\quad\Longrightarrow \gcd(x_{i}n+y_{j}m, m) = \gcd(x_{i}n+y_{j}m, n) = 1 \\ &\quad\Longrightarrow \gcd(x_{i}n+y_{j}m, mn) = 1. \end{align*} したがって, $y_{j}m+x_{i}n$ ($1\leq i\leq s$, $1\leq j\leq t$) は $mn$ を法とする既約剰余系である. (証明終)

[系] $m$, $n$ を正の整数とし, $\gcd(m, n)=1$ であるとする. このとき, $\varphi(mn)=\varphi(m)\varphi(n)$ が成り立つ.

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

プロフィール

よしいず

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

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

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

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

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

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。