Loading article…
モジュラー算術では、集合からnと互いに素な整数 （互いに素な整数）は、n 個の非負整数は、nを法とする乗法に関して群を形成し、これをnを法とする整数の乗法群と呼びます。同様に、この群の要素は、nと互いに素な合同類、すなわちnを法とする剰余類と考えることができます。したがって、別の名前はnを法とする原始剰余類群です。抽象代数学の一分野である環論では、これはnを法とする整数環の単位群として記述されます。ここで単位とは、乗法逆元を持つ要素を指し、この環では、 nと互いに素な要素と全く同じです。
このグループは通常、は数論において基礎的な群です。暗号、整数因数分解、素数判定などに用いられます。これはアーベル群であり、オイラーのトーシェント関数によって位数が与えられる有限群です。 素数nの場合、この群は巡回群であり、一般にその構造は容易に記述できるが、生成元を見つけるための単純な一般公式は知られていない。
乗法に関して、 nと互いに素な法nの合同類の集合がアーベル群の公理を満たすことを示すのは簡単な演習である。
実際、a がnと互いに素であるのは、gcd ( a , n ) = 1 の場合のみです。同じ合同類a ≡ b (mod n )に属する整数は、 gcd( a , n ) = gcd( b , n )を満たします。したがって、一方が n と互いに素であるのは、他方がnと互いに素である場合のみです。このように、 nを法とする合同類でnと互いに素であるものの概念は、明確に定義されています。
gcd( a , n ) = 1およびgcd( b , n ) = 1からgcd( ab , n ) = 1が導かれるため、 nと互いに素なクラスの集合は乗法に関して閉じている。
整数の乗算は合同類を尊重します。つまり、a ≡ a'およびb ≡ b' (mod n )はab ≡ a'b' (mod n )を意味します。これは、乗算が結合法則と交換法則を満たし、1 というクラスが唯一の乗法単位元であることを意味します。
最後に、aが与えられたとき、aの法nに関する乗法逆元は、 ax ≡ 1 (mod n )を満たす整数 x です。これは、 a がnと互いに素である場合にのみ存在します。なぜなら、その場合gcd( a , n ) = 1 であり、ベズーの補題により、ax + ny = 1を満たす整数xとyが存在するからです。式ax + ny = 1はxがnと互いに素であることを意味するため、乗法逆元は群に属します。x を計算する例は、記事「モジュラー乗法逆元」に記載されています。
nを法とする整数の集合（合同類）と加算および乗算演算の集合は環である。これは次のように表記される。 または （この表記は、整数をイデアルで割った商を取ることを指します）またはnの倍数で構成される）。数論以外では、より単純な表記法はよく使われるが、 nが素数の場合、 p進整数と混同されることがある。
nを法とする整数の乗法群、すなわちこの環の単元群は、（著者によって異なるが）次のように表される。 （ドイツ語のEinheitは「単位」と訳される）、または同様の表記法。この記事では、
表記法は位数nの巡回群を指します。これは、加法に関してnを法とする整数群と同型です。または加算の対象となるグループを指す場合もあります。例えば、乗法グループ素数pの場合、それは巡回群であり、したがって加法群と同型である。しかし、同型性は自明ではない。
nを法とする整数の乗法群の位数は、nと互いに素な数。オイラーのトーシェント関数によって与えられる。（OEISのシーケンスA000010）。素数pの場合、。
グループnが 1、2、4、p kまたは 2 p kの場合に限り、この群は巡回群である。ただし、 pは奇素数で、k > 0 である。n のその他の値については、この群は巡回群ではない。[ 1 ] [ 2 ] [ 3 ]これは最初にガウス によって証明された。[ 4 ]
これは、これらのnに対して次のことを意味します。
定義により、群が巡回群であるのは、生成元gを持つ場合、すなわちべき乗がnを法とするすべての可能な剰余をnと互いに素なものとして与える（最初の力それぞれに正確に1回ずつ与える。nを法とする原始根と呼ばれる。[ 5 ] 生成元が存在する場合、彼らのうちの。
法 1 では任意の 2 つの整数は合同である。つまり、1 と互いに素な合同クラスは [0] のみである。したがって、は、φ(1) = 1 の要素を持つ自明な群です。その自明性のため、1 を法とする合同式の場合は一般的に無視され、一部の著者は定理の記述にn = 1の場合を含めないことを選択しています。
mod 2 では互いに素な合同類は 1 つだけなので、[1]、は自明な群です。
mod 4 では、互いに素な合同類は [1] と [3] の 2 つあるので、2つの要素からなる環状群。
法8では、[1]、[3]、[5]、[7]の4つの互いに素な合同類が存在する。これらのそれぞれの2乗は1なので、クラインの4群。
法16では、互いに素な合同類は[1]、[3]、[5]、[7]、[9]、[11]、[13]、[15]の8つあります。は2-ねじれ部分群（つまり、各要素の2乗は1）なので、循環的ではない。3 のべき乗、は位数4の部分群であり、5のべき乗も同様である。 したがって
8と16で示されるパターンは、より高いべき乗2k 、 k > 2に対して[ 6 ]成り立つ。は2-ねじれ部分群なので、巡回群にはなり得ず、3のべき乗は位数2k - 2の巡回部分群であるため、次のようになる。
有限アーベル群の基本定理により、群素数の冪位数の巡回群の直積と同型である。
より具体的には、中国剰余定理[ 7 ]によれば、 それから指輪これは、それぞれの素因数に対応する環の直接積です。
同様に、ユニットのグループこれは、各主要電力因子に対応するグループの直接積です。
各奇素数のべき乗について対応する係数位数 の巡回群これはさらに素数べき乗の巡回群に分解される可能性がある。2のべき乗の場合、因子はk = 0、1、2 の場合を除き、循環的ではないが、上記のように循環群に分解される。
グループの順序は、直積における巡回群の位数の積である。群の指数、すなわち巡回群の位数の最小公倍数は、カーマイケル関数によって与えられる。（OEISの配列A002322）。言い換えれば、は、nと互いに素な各に対して、保持する。分割するそして、群が巡回群である場合に限り、それと等しくなります。
nが合成数の場合、おそらく真部分群が存在する。「偽証人のグループ」と呼ばれる、方程式の解からなるものn − 1乗するとnを法として 1 と合同になる要素。[ 8 ]フェルマーの小定理によれば、 n = p が素数の場合、この群はすべての要素から構成される。したがって、n が合成数の場合、このような剰余xはnの素数性に対する「偽陽性」または「偽証」となります。この基本的な素数性チェックでは、 x = 2 が最もよく使用され、n = 341 = 11 × 31は注目に値します。 また、n = 341 は、 x = 2 が素数性の偽証者となる最小の合成数です。実際、341 の偽証者部分群は 100 個の要素を含み、300 個の要素からなる群の中で指数 3 です。。
偽証者の非自明な部分群を持つ最小の例は9 = 3 × 3です。9 と互いに素な剰余は 6 つあります: 1、2、4、5、7、8。8 は 9 を法として−1と合同なので、8 8は 9 を法として1 と合同になります。したがって、1 と 8 は 9 の「素数性」に対する偽陽性です (9 は実際には素数ではないため)。これらは実際には唯一の偽陽性なので、部分群 {1,8} が偽証者の部分群です。同じ議論により、n − 1は任意の奇数の合成数nに対する「偽証者」であることが示されます。
n = 91 (= 7 × 13)の場合、91 と互いに素な剰余のうち、その半分 (つまり 36 個) は 91 の偽証者であり、具体的には 1、3、4、9、10、12、16、17、22、23、25、27、29、30、36、38、40、43、48、51、53、55、61、62、64、66、68、69、74、75、79、81、82、87、88、および 90 です。これらの x の値に対して、x 90は91を法として 1 と合同です。
n = 561 (= 3 × 11 × 17) はカーマイケル数であるため、 561と互いに素な任意の整数sに対して、 s 560は 561 を法として 1 と合同です。この場合、偽証者の部分群は真の部分群ではなく、561 を法とする乗法単位の全体群であり、320 個の剰余から構成されます。
この表は、また、n ≤ 128の場合の生成集合も存在します。分解と生成集合は一意ではありません。例えば、
（しかし)。以下の表には、最短の分解がリストされています（その中で、辞書式順序で最初に選択されます。これにより、同型群が同じ分解でリストされることが保証されます）。生成集合も可能な限り短くなるように選択され、原始根を持つnについては、 nを法とする最小の原始根がリストされています。
例えば、。 それからこれは、グループの位数が8であることを意味します（つまり、20より小さく、かつ20と互いに素な数が8個あるということです）。各要素の位数が 4 で割り切れることを意味します。つまり、20 と互いに素な任意の数の 4 乗は 1 (mod 20) と合同です。集合 {3,19} はグループを生成します。これは、これは3 a × 19 bの形をしています(要素 3 の位数は 4 なのでaは 0、1、2、または 3 であり、同様に要素 19 の位数は 2 なのでbは 0 または 1 です)。
nを法とする最小の原始根は(根が存在しない場合は 0) です。
mod nの最小生成集合の要素数は
『算術研究』は、ガウスのキケロ風ラテン語から英語とドイツ語に翻訳されている。ドイツ語版には、数論に関する彼の論文がすべて収録されている。すなわち、二次相互法則のすべての証明、ガウス和の符号の決定、双二次相互法則の研究、そして未発表のノートなどである。
