整数論を考えるのに基本的な概念だと思う。

群の言葉を使う。
群とは、いくつかの法則をみたす元同士の演算が定義されている集合である。
「群論」とは群について一般的な性質を詳しく学ぶものであるが
ここでは群の基本的な言葉が使えれば良い
必要になるのは可換な群（アーベル群）だけを扱うので
必要な知識は一般的な群論より限られたものである

もっとも単純で基本的なアーベル群は、巡回群である。
まずはそれに馴染んでおく必要がある。
------------
*巡回群

巡回群C[n]はn個の元からなり、いくつかの描写が可能である。

・元をa[0],a[1],...,a[n-1]と名付けて
a[j]とa[k] の演算を、a[(j+k)をnで割った余り]と定義した群

・単位元eと生成元sとよばれる元があって
s,s+s, s+s+s, は異なる元であり、n個のsを演算させた結果がeに戻る群
群の演算は、文脈によって加法的に書く時と乗法的に書く時があるので注意が必要である。

・集合 {exp(2kπ/n)|k=0,1,2,...,n-1} に乗法による演算を入れた群

2つの群が「同じ」かどうか比べるには正確には同型という言葉を使う
たぶん、上記の3つの群が同じ群だと思えることには同感できるだろう。
どうして同じ群だと思えるかを突き詰めてみれば自然に同型の概念に達すると思う：
「演算を保つような全単射が存在する」

・巡回群を記述するもう１つの代表的な方法は、剰余群として捉える方法である。

-------------
*剰余群

可換群に限れば、群Gと部分群Hがあれば剰余群G/Hが定義できる。
部分群とは、もとの群の部分集合で、かつもとの群に定義された演算と同じ演算で群をなす集合である。

G = C[6] = {e,s,s+s,s+s+s,s+s+s+s,s+s+s+s+s} を考える。H = {e,s+s,s+s+s+s} はGの部分群である。

剰余群G/Hはいくつかの視点での描写が可能であるが
ここでは、「剰余類」を集合として定義できて、
それにGから誘導される自然な演算により群をなす　という視点とする。

G/H は (Gの部分集合) の集合 である。（「集合の集合」）
具体的には G/H = { {e,s+s,s+s+s+s}, {s,s+s+s,s+s+s+s+s} }
この2つの元を e+H, s+H というふうに表記するのが便利である。
g+H とは Gの部分集合 {g+h|h∈H} のことである。
この表記を使って、G/H は { g+H | g∈G } で定義される。
G/H = {e+H, s+H, s+s+H, s+s+s+H, s+s+s+s+H, s+s+s+s+s+H} となるが
例えば e+H と s+s+H は同じものであるから、結局 G/H = {e+H,s+H} となる。

次に、自然な演算を入れる。x+H と y+H の演算結果 (x+H)+(y+H) は
x+y ∈ z+H となるような z+H と定める。

正確な議論をするならwell-definedであることを確認する必要がある。
（何を確認する必要があるか。それを確認せよ。を問いとしておく。）

・この剰余群という言葉をつかって、巡回群を特徴づけることができる。
巡回群C[n]は、整数全体がなす群Z と nの倍数からなる部分群 nZ による剰余群 Z/nZ である。

上記の定義に文字通り従って Z/3Z は (Zの部分集合)の集合 というふうに書くなら
Z/3Z = { {..-6,-3,0,3,6,9,..} , {..-5,-2,1,4,7,...} , {..,-4,-1,2,5,8,..} }
あるいは Z/3Z = {0+3Z, 1+3Z, 2+3Z} というわけである。
この Z/nZ が巡回群の一番よくある描写でもある。
この表記をしたいために剰余群の話をする必要があった。

※ 1+3Z のような書き方は煩雑であり 1 (mod 3) と書いたり文脈によっては断りなく単に1と書いたりすることもあるかもしれないが
剰余類の定義に基づくなら {1+h|hは3の倍数} という集合が由来である。

----------
*既約剰余類がなす乗法群

今回のノートの主役である。

剰余類Z/nZに加法で演算を入れた群は、巡回群であって分かりやすい。
剰余類Z/nZに乗法で演算を入れた場合はどうなるか。
そのままでは群をなさないが、
法nと互いに素な剰余類（既約剰余類）だけに限ると、群をなす。
（そのことの証明は省略する。練習問題にでも。）
その群は (Z/nZ)* と書かれることが多い（実際には*は上付き）

 (Z/nZ)* の「構造」を知ることが、このノートの目的である。
【結果】を先に紹介する。

【pが素数のとき (Z/pZ)* は p-1個の元からなる巡回群である】
【p,qが互いに素のとき (Z/pqZ)* は (Z/pZ)* と (Z/qZ)* の直積である】
直積という言葉は後で説明する。
nがpの冪であるような場合については結果としては
【(Z/p^nZ)* は(p-1)*p^(n-1)個の元からなり、pが奇素数のときは巡回群である。
 p=2 のときは 2^(n-2)個の元からなる巡回群と Z/2Z の直積となる】

・x^kをNで割った余りの表を出力するスクリプト
・(Z/nZ)* の別の重要性としては、n次円分体のガロア群として現れる。
実際このノートを書いた動機の１つである下記質問がそれ関連であった：
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11154912161
・円分体のガロア群について紹介を試みたノート：
garoa.htmlの最初のほうの部分

----------
直積が必要になるものは後回しにするとして、
【pを素数とする。(Z/pZ)* は巡回群である】
という事実から何が言えるかを紹介しよう。（軽い証明は一応あとに書いた）

・原始根の存在（(Z/pZ)* は巡回群であることとほとんど同じ意味ですが）
あるrが存在して、集合 {r^k+pZ | 0≦k≦p-1} が
(Z/pZ)の0+pZ 以外の(p-1)種類の剰余類を網羅的に与える
（念のため：そのようなrは一意的ではない。）

・(p-1)の約数dに対してd個の元からなる(Z/pZ)*の部分群はちょうど1つだけある
それは {x∈(Z/pZ)* | x^d = 1+pZ (mod p)} という集合でもあるし
{x∈(Z/pZ)* | x=y^(n/d) となる y∈(Z/pZ)* が存在する} という集合でもある。
原始根を使えば、{x=r^{(n/d)k} | k∈Z } という集合と認識することもできる。

・特にpを奇素数とする。
0以外のp-1個の剰余類には平方剰余と平方非剰余が(p-1)/2個ずつあり
オイラーの規準 (n/p) ≡ n^{(p-1)/2} (mod p)　が成り立つ
（左辺はルジャンドル記号）
また、平方剰余の第1補充法則がここから得られる

※巡回群じゃない場合には同様のことが成り立たないということを紹介する
(Z/15Z)* を考える。既約剰余類は{1,2,4,7,8,11,13,14} (+15Z) である。
（後で使う直積という言葉によってこの乗法群は Z/2Z×Z/4Zの構造である）
4個の元からなる部分群は {1,2,4,8}, {1,4,7,13}, {1,4,11,14} の3種類存在する。
一方、集合 {x|x^4≡1} は {1,2,4,7,8,11,13,14} 全体であり
集合 {x|x=y^2となるyが存在する} つまり平方剰余は {1,4}のみである。

---------
(Z/pZ)* と Z/(p-1)Z が同型であることという視点で
加法群 Z/(p-1)Z の言葉を使った表現も書いておく。p-1=qとおいておく。

・r^k+pZ∈(Z/pZ)* と  k+qZ ∈ Z/qZ の対応が全単射である。
・qの約数dに対してd個の元からなる Z/qZ の部分群とは(n/d)の倍数の集合であり
 {x∈Z/qZ | dx=1} と書けるし {x∈Z/qZ | x=(n/d)y となるyが存在する}とも書ける
・qが偶数の時
x∈Z/qZ の偶奇は (q/2)xがqを法として 0とq/2のどちらに合同かで分かる。

----------------
n=5 の場合と n=8 の場合を具体的に紹介する。

n=5 では、既約剰余類は {1+5Z,2+5Z,3+5Z,4+5Z} の4つである。
これは巡回群である：
e=1+5Z, s=2+5Z , ss=4+5Z, sss=3+5Z, ssss=e

n=8 では、既約剰余類は {1+8Z,3+8Z,5+8Z,7+8Z} の4つである。
これは巡回群ではない
e=1+8Z, s=3+8Z とすると ss=e 
5+8Z, 7+8Z も2乗するだけで1+8Zに至ってしまう。
先に書いた結果の通り、これは直積 Z/2Z×Z/2Z の構造をしている。
----------
*直積

群G1と群G2の直積とは G1×G2 と書かれるが
集合としては {(x,y) | x∈G1, y∈G2} であって
演算は単に (x1,y1)+(x2,y2) = (x1+x2,y1+y2) で定まる。
2次元ベクトルのようなものである

重要な結果がある。（中国の剰余定理）
【p,qが互いに素のとき (Z/pqZ) は (Z/pZ)×(Z/qZ) と同型である】

p=2,q=3などで具体的に見てみるのが良いだろう：
Z/6Z = {0+6Z, 1+6Z, 2+6Z, 3+6Z, 4+6Z, 5+6Z}
Z/2Z×Z/3Z = {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)}
正確には (0+2Z,0+3Z)等と書かれるものだが煩雑なので略記した。

視覚的に、これと Z/6Zを対応させた：
 23_6.png
一般に縦と横が互いに素のとき、すべての点を通ってくるのが主張の内容である。
(1,1)をk個足した結果は、(kをp=2で割った余り, kをq=3で割った余り) に相当する。

初等整数論的な解釈としては
「pq で割った余りがzとなるような集合」はpq種類あって
「pで割った余りがxとなり、qで割った余りがyとなる集合」もpq種類あって
それらは1:1に対応する　ということである。

系：p,q が互いに素ならば (Z/pZ)×(Z/qZ) は巡回群である。
一方、p,qが互いに素でない場合は Z/pZ × Z/qZ は巡回群ではない。
（証明するには次の巡回群の性質を使えば良い：
Gをn個の元からなる巡回群で、dをnの約数とする。
このときdx=eとなるx∈Gはちょうどd個しかない。）

有限アーベル群の構造定理は紹介すべき価値があるが
今回の結果には差し当たりいらないので省略する。

[練習問題として相当する内容をちらっと紹介だけ]
・Z/6Z×Z/8Z = Z/2Z×Z/24Z を示せ
・互いに素でない自然数p,qを与えられた時
　Z/pZ×Z/qZ = Z/sZ×Z/rZ , rはsの倍数 となるr,sをとれることを示せ

・有限なアーベル群は、常にいくつかの巡回群の直積で表される。

==========================================
ここからは【結果】たちを示す。

後で使いたくなる補題を先に提示する。

[補題：群が巡回群であるためのある必要十分条件]
「Gを位数n群として単位元をeとおく。
任意のnの約数dに対してdx=e となるx∈G がちょうどd個存在するならば
Gは巡回群である。」(乗法的演算による群なら dxの代わりに x^d)
（逆は巡回群の性質よりすぐわかる）

位数という言葉は群の言葉として2種類の意味で使われる。
群の位数とは群が持つ元の個数である。
一方、群の元の位数とは、自身のk個の演算が単位元になる最小のkである。
この位数という言葉を使うと補題の主張は次のように書ける。
「Gを位数nの群として単位元をeとおく。
任意のnの約数dに対して位数がdの約数となるxがちょうどd個存在するならば
位数がちょうどnであるような元が存在する。」

[略証]
φ(n)をオイラーのトーシェント関数とする。
群Gにおける位数がdである元の個数を A(G,d), 位数がdの約数である元の個数をB(G,d)とおく。
B(G,d)=ΣA(G,d') (d'はdの約数) の関係がある。
この関係を逆に解くことで、A(d)は、B(d)によって一意的に決定される。
つまり、2つのアーベル群GとG'があって、ともに位数がnであり、
任意のnの約数dに対して B(G,d) と B(G',d) が等しければ A(G,d)とA(G',d)も等しい。
特にG'として位数nの巡回群をとれば、補題の主張が従う。

[補題2]
任意のnの約数dに対して B(G,d)≧d である。

[略証]
nの素因数pに対してp倍写像G→Gを考えた時に、
少なくともp個の元が単位元に移ることを示せば十分である。
それには、単位元以外に単位元に写る元が1でもあることを示せば十分である。
（それをaとおけば2a,3a,...(p-1)aもp倍で単位元にうつる。）
そのことはコーシーの定理として知られている。

補題1,2を組み合わせて次を得る
[命題]
「Gを位数n群として単位元をeとおく。
任意のnの約数dに対してdx=e となるx∈G が高々d個しか存在しないならば
Gは巡回群である。」

[補題3]
n,mを互いに素とする。Gが位数nmのアーベル群で、Hを位数mの巡回群とする。
GからHへの全射準同型fが存在して、その核 K={x∈G|f(x)はHの単位元} が位数nの巡回群ならば、
Gは位数nmの巡回群である。

[証明]
Kの生成元をa、Hの生成元をbとおく。
fは全射なので f(y)=bとなるy∈Gが存在する。
my∈K となるから my=ka となる自然数kが存在する。
m,nが互いに素なので k+mj≡1 (mod n) となるjをとれる。
y'=y+ja とおくと my' = m(y+ja) = (k+mj)a = a より my'の位数はnである
また f(ny') = f(n(y+ja)) = nf(y)+njf(a) = nb において
m,nが互いに素なのでny'の位数はmの倍数である。
これらより y'の位数がmnであることが言える。

※アーベル群という仮定は外せない。3次対称群が反例を与える。
m(y+ja)=my+mja の変形で可換性を使っている。

------------
・1つめの結果：
【pが素数のとき (Z/pZ)* は p-1個の元からなる巡回群である】

合同方程式の性質：d次の合同式は高々d個の解しか持たない
特に x^d≡1 (mod p) は(Z/pZ)内に高々d個の解しか持たない。
と上記の[命題]を組み合わせれば良い。

[高々d個の解しか持たないことの略証]
d個以上の解を持つと仮定する。合同式における因数定理から
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13156085748
x^d-1 ≡ (x-x1)(x-x2)...(x-xd) (mod p) とおける。
素数の性質により 右辺≡0 となるのは、
xがx1,x2,...,xdのどれかに合同なときだけである。

・2つめの結果：
【p,qが互いに素のとき (Z/pqZ)* は (Z/pZ)* と (Z/qZ)* の直積である】
(Z/pqZ) と (Z/pZ)×(Z/qZ) が同型であるときと同じ対応
x+pqZ → ((xをpで割った余り)+pZ , (yをqで割った余り)+qZ) 
が乗法に関しても演算を保つ全単射となる

・3つめの結果(1)
【(Z/p^nZ)* は(p-1)*p^(n-1)個の元からなり、pが奇素数のときは巡回群である。】
pで割った余りをとることで (Z/p^nZ)* から (Z/pZ)* への全射準同型を得られる。
[補題3]よりその核である (pZ+1)/p^nZ がなす部分群が巡回群であることを示せば良い。
そこで再度先の[命題]を使うことを見こんでも
やはり　http://searial.web.fc2.com/sorafune/1_2.html　でも紹介している定理
pを奇素数としq≧1とすると　x≡1 (mod p^q)　⇔　x^p≡1 (mod p^(q+1))　が成り立つ。
が鍵となるだと思う。
これにより、x^p≡1 (mod p^n) は p^nを法として p個の解しか持たないことが言えるし
繰り返すことにより x^(p^i)≡1 (mod p^n) は p^i 個の解しか持たないことが言える。

・3つめの結果(2)
【(Z/p^nZ)* は p=2 のときは 2^(n-2)個の元からなる巡回群と Z/2Z の直積となる】
4で割った余りをとった部分群H= (4N+1)Z/p^nZ の乗法群が巡回群であることを示す。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10121826000
(Z/p^nZ)*の元は {ah|a=±1,h∈H} の形で書けて
g=ah, g'=a'h' に対して gg'=aa'hh' が成り立つから直積構造 Z/2Z×H である。

例えば32で割った剰余類は、
{f(a,b) = (5^a*(-1)^b) +32Z | a=0,1,2,3,4,5,6,7, b=0,1} で一意的に表せて
Z/8Z×Z/2Z = {(a,b)| a∈Z/8Z, b∈Z/2Z} と演算を保つ全単射の関係
という構造である。

・系：(Z/nZ)* が巡回群となる整数nは、次ですべてである
n=2,4,(奇素数の冪),n=2*(奇素数の冪) のどれか (冪は1乗を含む)
===============
nが素数の冪のときの(Z/nZ)*の構造については
より一般的な局所体の乗法群が背景にあると考えるのが自然に思う。

<ここから難しい話>
https://www.maths.nottingham.ac.uk/personal/ibf/lf/lf.pdf
5〜6ページの式
(1) (1+απ^i)^p ≡ 1+α^p*π^pi (mod π^(pi+1)) (ie/(p-1))
が本質的であると思う。今回はπ=p,θ=1,e=1 である。
(3)だけが必要になる。p=2のときだけ(2)が起こり得る。
このように2の冪のときだけ乗法群の状況が異なるという現象は、
「一般に分岐指数(eの値)に応じて起こる現象が、
p=2のときは分岐指数1のときに現れてしまう」と捉えれば良いと思う。

(3)によりi>e/(p-1)のときi次主単数群と呼ばれる集合は(完備局所体で)巡回群をなす
n次剰余環を取って (Z/p^nZ)* の部分群  {(1+ap^i)+p^nZ |a∈N} は巡回群をなす。
<ここまで>

[追記]
"指数対数準同型" を使って具体的に説明を試みたものをここにも紹介する：
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11158473256
そこらへんではなかなか見かけない視点だと思います　おすすめです

==============
より一般的な環に対する剰余類の乗法群を考察することもできる。
特にQの代数拡大体の整数環の場合が、自然な拡張である。

例えば Z[i] = {a+bi|a,b∈Z} の場合
まずどのような部分群があるのかを明らかにする。
nZ[i] = {na+nbi|a,b∈Z} は部分群であるがもっと細かい部分群がある。
(1+i)Z[i] とか (1+2i)Z[i] とかである。

・pが4N+1型素数のとき 
a^2+b^2=pとなるa,bがあって
Z[i]/(a+bi)Z[i] がp個の剰余類を持つ。
0+(a+bi)Z[i] を除いたp-1個の既約剰余類は巡回群をなす。

一方、Z[i]/pZ[i] は p^2個の剰余類を持つ。
a±biの「倍数」がp個ずつあって1個重複している。
既約剰余類の個数はp^2-2p+1個となる。
この既約剰余類の構造は Z/(p-1)Z × Z/(p-1)Z の構造となる。
現象としてはa+bi,a-biは互いに素であることによる分解である：
 Z[i]/pZ[i] = Z[i]/(a+bi)Z[i] × Z[i]/(a-bi)Z[i]

・pが4N+3型素数のときは
Z[i]/pZ[i] は p^2-1個の既約剰余類を持ち、巡回群をなす。

戻る