整数の合同 – 定義

導入

整数合同とは、2 つの整数を結合できる関係です。これは、 18^世紀後半にドイツの数学者カール フリードリッヒ ガウスによって構造として初めて研究され、1801 年に彼のDiquisitiones arithmeticaeで一般に発表されました。今日では、整数論、代数一般、および暗号化で一般的に使用されています。これは、モジュラー算術と呼ばれる数学の一分野の基礎を表します。

これは、数値について直接推論するのではなく、特定の整数によるユークリッド除算によってそれぞれの剰余を計算する算術です。モジュロ(この記事全体で言及します)。次に、合同性について話します。

モジュラー算術の歴史、モジュラー算術用に開発されたツール、およびアプリケーションについては、モジュラー算術の記事で説明されています。より徹底的で教訓的ではない分析が、記事「Z/nZ Ring」で提供されています。

直感的な発想「時計算」

モジュラー演算は修正された整数演算システムであり、数値が特定の値に達すると「減少」します。

時計の小針が示す時間を「足し算」する「時計算」を例に挙げます。具体的には、9時にスタートして4時間を足すと、9時に終わるのではなく、午後 1 時 (通常の加算と同じように)、私たちは 1時にいます。同様に、真夜中に開始して午前 7 時まで 3 回連続で待つと、最終的には (午前 9 時ではなく) 午前 9 時になります。

基本的に、12 歳になるとゼロから始まります。前の例に戻ると、 9 と 21 は12 を法として合同であると言います。数字の9。 21; 33; 45;等モジュロ 12 を使用する場合、これらは等しいとみなされます。

一般化すると、任意の時間を含む時計を簡単に想像し、新しいモジュロを使用して計算を行うことができます。

Z/nZ残留リング

工事

前述のプロパティは、n を法として互いに合同な 2 つの数が、n を法として合同している間、加算または乗算で交換可能であることを示しています。次に、n を法として一致するすべての数値を、同値クラスと呼ばれる同じクラスにグループ化し、このクラスの特定の代表のみを使用するというアイデアが生まれます。同じクラスのすべての数値は、n による除算の余りが同じであるため、n による除算の余りを優先し、次のセットで作業します。

または n個の要素で構成されていますより単純に、n を法とする剰余の集合 {0, 1, 2, …, n – 1}。これを n を法とする剰余リングまたは商リングと呼びます。

このセットでは、相対整数で定義されたものと同様の加算と乗算を定義できます。

• 追加: 2 つの剰余aとbに、n を法とするa + bの剰余を関連付けます。理論的には、合計の別の表記法を見つける必要があります。たとえば、
  $$ {\oplus} $$
  ただし、簡単にするために、同じ表記をそのまま使用すると、別の意味になることがよくあります。

  したがって、6 を法とする合同環では 3 + 2 = 5 と書きますが、4 と 2 の和は 6 を法とする余り 0 になるため、4 + 2 = 0 となります。

• 乗算: 2 つの剰余aとbに、n を法とするa × bの剰余を関連付けます。前と同じ理由で、積には相対整数のセットと同じ記号を使用します。

  したがって、6 を法とする合同環では 2 × 2 = 4 と書きますが、2 × 5 = 4 (2 × 5 の積は 6 で割った余りが 4 になるため)、さらには 2 × 3 = 0 となります。

次に、次の演算テーブルを構築できます。

の加算テーブル $$ {\mathbb Z/6\mathbb Z} $$ + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4

の九九 $$ {\mathbb Z/6\mathbb Z} $$ × 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1

これらの演算は、加算や乗算とほぼ同じ性質を持っています。

。

• 加算は可換的 (項は並べ替えることができます)、結合的 (3 つの項を追加するとき、最初の 2 つの項の合計を無差別に作成して最後の値を加算するか、最後の 2 つの項の合計を最初の項に加算できます)、中立要素を持ちます。 (0 を追加しても何も変わりません)、各要素には反対のがあります。

  の追加と比較して重要なニュアンス

  $$ { \mathbb Z} $$

  、あれ、で

  $$ {\mathbb Z} $$

  、 a + (- a) = 0 であるため、 aの反対は– aです。 さて、n を法とする合同環では、 a + (n – a) = 0 であるため、 aの反対はn – aです ( aとn – a はn で割った余りが 0 になります)。ただし、 -aとn -a はn を法として交換可能であり、 -aではなくn – aを選択するのは、0 と n – 1 の間の数値を表すものとして選択するためです。

• 乗算も可換性、結合性があり、中立要素 (1 を乗算しても何も変化しません) を持ち、加算に対しては分配的です。

このような性質を持つ 2 つの演算の集合をリングと呼びます。

簡略化と方程式

私たちが通常行う唯一の操作

そしてリング上では常にフェアであるとは限らない簡略化です。

確かに 2 a = 4 インチの場合

$$ {\mathbb Z} $$

では、 a = 2 であることがわかります。

$$ {\mathbb Z/6\mathbb Z} $$

、2 a = 4 の場合、2 a は6 で割った余りが 4 になることだけがわかります。したがって、 a は3 で割った余りが 2 になります。したがって、 a は6 で割った余りが 2 または 5 になる可能性があります。もっと簡単に言えば、2 = 5 ではなく、2 × 2 = 2 × 5 になります。

同様に、古典的な数の集合で常に使用される特性「2 つの項の積がゼロになるためには、項の 1 つがゼロであることが必要かつ十分である」という性質は、常に実現されるわけではありません。

で

$$ {\mathbb Z/6\mathbb Z} $$

、2 × 3 = 0 ですが、2 も 3 もゼロではありません

指輪と言われているのは、

正直ではありません。

したがって、乗算が含まれる場合、方程式を解くのが少し問題になる可能性があります。

• 方程式x + 2 = 1
  $$ {\mathbb Z/6\mathbb Z} $$
  は、各辺 x = 5 に同じ数量 (4) を加算することで解決されます (2 + 4 = 0 であるため)。
• 方程式 3x = 2
  $$ {\mathbb Z/10\mathbb Z} $$
  この問題は、3 × 7 = 1 と、方程式 3x = 2 および x = 7 × 2 が同等であることに注意することで解決されます (一方から他方へは、各要素に 7 または 3 を乗算することで進みます)。この場合、解は 4 になります (2 × 7 の剰余は 4 の 10 であるため)。
• 方程式 2x = 3 で
  $$ {\mathbb Z/10\mathbb Z} $$
  には解がなく、方程式 2x = 6 には 2 つ (3 と 8) があります。

未知の x を使用して方程式 ax = b を解くことを示します。

aとnが互いに素である場合にのみ、固有の解が得られます。

方程式の解を見つける

n とaの値に応じて、解が存在しない、1 つ、2 つ、またはそれ以上の解が存在する可能性があり、二次剰余の研究と二次相反性の法則の記述が生じます。

の建設

イデアルによる環商として、および Z/nZ 環の代数的性質は、Z/nZ 環の記事で扱われます。

パワーズと フェルマーの小定理

乗算の

, 歴代の勢力に興味が湧くのは当然です。可能な剰余は n – 1 個だけであるため、 k^に対して可能な値は n – 1 個あり、したがって必然的に同じ値を複数回取得することになります。したがって、 k^とm^{が n を}法として同じ剰余を持つようなkとm が存在します。 k^の構築は回帰に基づいているため、すでに遭遇した剰余に遭遇するとすぐに、このべき乗から一連のべき乗が循環的になることがわかり、探索を停止できるようになります。

歴代の権力 $$ {\mathbb Z/7\mathbb Z} $$ 1 2 3 4 5 6 k = 0 1 1 1 1 1 1 k = 1 1 2 3 4 5 6 k = 2 … 4 2 2 4 1 k = 3 … 1 6 1 6 … k = 4 … … 4 … 2 … k = 5 … … 5 … 3 … k = 6 1 1 1 1 1 1

歴代の権力 $$ {\mathbb Z/15\mathbb Z} $$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 k = 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 k = 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 k = 2 … 4 9 1 10 6 4 4 6 10 1 9 4 1 k = 3 … 8 12 … 5 … 13 2 9 … … 3 7 … k = 4 … 1 6 … … … 1 1 … … … 6 1 … k = 5 … … 3 … … … … … … … … 12 … … … … … … … … … … … … … … … … … k = 8 1 1 … 1 … … 1 1 … … 1 … 1 1

における権力に関する観察

そして最初のケースでは、7 を含むすべての素数(つまり、7 を法とする 0 に合同ではない) について、7 を法とする 1 に合同な6^があり、2 番目のケースでは、1 を通過するシーケンスのみが に対応することを示しています。 15 の素数整数の場合、15 の素数整数が 8 つあり、15 の素数の場合、 ⁸は15 を法とする 1 と合同であることがわかります。

これら 2 つの観測結果は 2 つの定理に対応します。

• フェルマーの小さな定理は、すべての整数 n が素数であり、すべての整数が n を持つ素数であることを示します。
  $$ {a^{n-1} \equiv 1 \pmod n} $$
• オイラーの定理。前述の定理を一般化したもので、 n が 2 以上で、任意の整数がnと素数を持つことを指定します。
  $$ {a^{\varphi(n)}\equiv 1 \pmod n} $$
  、 または
  $$ {\varphi(n)} $$
  、オイラー指標は、1 から n – 1 までの整数の数であり、n でプライムされます。