乗法群
$ (\Z/n\Z)^\timesや$ (\Z/n\Z)^*と書く
$ a\times b\quad{\rm mod}\,nのような計算は$ (\Z/n\Z)^\times上で行われる
乗法群$ (\Z/n\Z)^\timesの演算$ \timesを積として、剰余群$ \Z/n\Zの演算$ +を和として持つ環は剰余環$ \Z/n\Zである。 https://scrapbox.io/files/6506eb0f4fb23c001c111088.svg
$ M_{35}
https://gyazo.com/dd2b2584575de8a6f9a4f39567d15601
https://gyazo.com/b00e1e1cf733c05599105863253f5a5f https://gyazo.com/39bf6534c6a62edaf942a7df9bf3a7ef https://gyazo.com/a325cd19562231f3329feca595a6f8f7 https://gyazo.com/f7469cb31a861a755bda89077f5ea683
$ M_{60}
https://gyazo.com/83e321d2feba54631d502e9d3ce04b41
構造
$ n=\prod_{p\in\mathbb P|n}\hat p\quad(\hat p=p^{w_p})と素因数分解できるとき $ (\Z/n\Z)^\times\simeq\prod_{p\in\mathbb P|n}(\Z/\hat p\Z)^\times
$ (\Z/\hat p\Z)^\times=\lang\omega_{\phi(\hat p)}\rang\quad(p\in\mathbb P_{\ge3})
$ \simeq C(\phi(\hat p))
$ =C\left(\frac{\hat p}p(p-1)\right)
$ (\Z/\hat2\Z)^\times=\lang-1\rang\times\lang\omega_{\phi(\hat2/2)}\rang\quad(\hat2\ge4)
$ \simeq C(2)\times C(\phi(\hat 2/2))
$ =C(2)\times C(\hat2/4)
$ (\Z/2\Z)^\times\simeq\{1\}
準備
$ n=\prod_{p\in\mathbb P|n}p^{w_p}=\prod_{p\in\mathbb P|n}\hat p
$ \hat2や$ \hat3等の具体的な素数にハットがついたものも複数の値を取りうる変数である。例えば、
$ 12=2^2\cdot3=\hat2\cdot\hat3
$ 18=2\cdot3^2=\hat2\cdot\hat3
$ 24=2^3\cdot3=\hat2\cdot\hat3
これにより$ x^{p^{w_p-1}-1}を$ x^{\hat p/p-1}で表せる。
乗法性：
$ \phi(ab)=\phi(a)\phi(b)
$ \phi(n)=\phi\left(\prod_{p\in\mathbb P|n}\hat p\right)=\prod_{p\in\mathbb P|n}\phi(\hat p)
具体的な計算
$ \hat p以下の自然数$ \N_{\le \hat p}において$ \hat pと互いに素ではない数は$ pの倍数である。 $ pの倍数は$ \frac{\hat p}{p}個ある。 従って$ \N_{\le \hat p}において$ \hat pと互いに素であるものの個数$ \phi(\hat p)は以下のように表せる。 $ \phi(\hat p)=\hat p-\frac{\hat p}p
$ =\frac{\hat p}pp-\frac{\hat p}p
$ =\frac{\hat p}p(p-1)
また、乗法性により一般の$ n\in\Nにおいて$ \phi(n)は以下のように表せる。 $ \phi(n)=\prod_{p\in\mathbb P|n}\frac{\hat p}p(p-1)
準備
まず、乗法群の要素$ a\in(\Z/n\Z)^\timesは全て$ nと互いに素である。 $ \phi(n)=\#{\rm\mathcal Cop}(n)
$ \#(\Z/n\Z)^\times=\phi(n)
群$ Gにおいて以下の条件を満たす元$ \omega_nを原始根や生成元という $ \omega_n^n=1
$ \omega_n^k\ne1\quad(k\in\N_{<n}^+)
多項式$ x^n=1は$ n個の解$ x=1,\omega_n^kを持つ
$ 0=x^n-1
$ (x-1)\left(\sum_{i=0}^{n-1}x^i\right)
特に、
$ 0=\sum_{i=0}^{n-1}x^iの解は$ \omega_n^kである
$ (\Z/n\Z)\simeq\prod_{p\in\mathbb P|n}(\Z/\hat p\Z)
任意の$ x\in(\Z/\hat p\Z)^\timesは$ \hat pと互いに素であるため、オイラーの定理により以下の式を満たす。 $ x^{\phi(\hat p)}\overset{\hat p}\equiv1
任意の$ x\in(\Z/\hat p\Z)がこの式を満たすため、この方程式は$ \#(\Z/\hat p\Z)個以上の相異なる解を持つ。
また、方程式の次数が$ \phi(\hat p)であるため、重解を含めて$ \phi(\hat p)個以下の解を持つ。
ここで、$ \#(\Z/\hat p\Z)=\phi(\hat p)なので、この式は丁度$ \phi(\hat p)個の相異なる解を持つ。
この式を解くと以下の解を得る
$ 0\overset{\hat p}\equiv x^{\phi(\hat p)}-1
$ =(x-1)\left(\sum_{k=0}^{\phi(\hat p)-1}x^k\right)\quad(p\ge3)
この式の解は$ x=1,\omega_{\phi(\hat p)}^i\quad\left(i\in\N_{<\phi(\hat p)}^+\right)
これらは$ \phi(\hat p)個の相異なる数であるため、
$ {\rm order}(\omega_{\phi(\hat p)})=\phi(\hat p)
$ 0\overset{\hat 2}\equiv x^{\phi(\hat 2)}-1
$ =(x^2)^{\phi(\hat 2)/2}-1
$ =(x^2-1)\left(\sum_{k-0}^{\phi(\hat 2)/2-1}(x^2)^k\right)\quad(\hat 2\ge4)
この式の解は$ x=\pm1,\pm\omega_{\phi(\hat 2/2)}^i\quad\left(i\in\N_{<\phi(\hat 2/2)}^+\right)
これらは$ \phi(\hat 2)個の相異なる数が2個の符号$ \pmで分けられたものであるため、
$ {\rm order}(\omega_{\phi(\hat 2/2)})=\phi(\hat 2)/2=\phi(\hat 2/2)
$ 0\overset 2\equiv x^{\phi(2)}-1
$ =x-1
この式の解は$ x=1
位数を比較することで、これらが乗法群の全ての元を生成することを示す。 $ \#(\Z/n\Z)=\prod_{p\in\mathbb P|n}\#(\Z/\hat p\Z)
$ \#(\Z/\hat p\Z)=\phi(\hat p)={\rm order}\left(\omega_{\phi(\hat p)}\right)\quad(p\in\mathbb P_{\ge3})
$ \#(\Z/\hat2\Z)=\phi(\hat2)=2\times\phi(\hat2/2)=2\times{\rm order}\left(\omega_{\phi(\hat p/2)}\right)\quad\hat2\ge4
$ ={\rm order}(-1)\times{\rm order}\left(\omega_{\phi(\hat p/2)}\right)
よって
$ (\Z/\hat p\Z)=\lang\omega_{\phi(\hat p)}\rang\simeq C(\phi(\hat p))\quad p\in\mathbb P_{\ge3}
$ (\Z/2\Z)=\lang-1\rang\times\left\lang\omega_{\phi(\hat2/2)}\right\rang\simeq C(2)\times C\left(\phi(\hat2/2)\right)\quad\hat2\ge4
$ (\Z/2\Z)=\{1\}