乗法群
$ n を法とする整数の乗法群
modulo 計算の乗法と同じ挙動をする群
$ (\Z/n\Z)^\timesや$ (\Z/n\Z)^*と書く
剰余群$ \Z/n\Zは modulo の加算に対する群 $ a\times b\,{\rm mod}\,nのような計算は$ (\Z/n\Z)^\times上で行われる
https://scrapbox.io/files/6506eb0f4fb23c001c111088.svg
構造
$ n=\prod_{p|n}p^{e_p}と素因数分解できるとき$ (\Z/n\Z)^\times\simeq\prod_{p|n}(\Z/p^{e_p}\Z)^\times $ \Z/n\Z\simeq\prod_{p|n}\Z/p^{e_p}\Z
後は$ (\Z/p^{e_p}\Z)^\timesのみ調べれば良い
$ p\ge3,\ e\in\Nとすると$ (\Z/p^e\Z)^\times\simeq(\Z/p^{e-1}(p-1)\Z)
$ p\ge3,\ e\in\Nとすると$ (\Z/p^e\Z)^\timesは位数$ \varphi(p^e)=p^{e-1}(p-1)の巡回群
証明
$ (\Z/2^e\Z)^\timesの群の同型は以下の通り
$ (\Z/2^e\Z)^\times\begin{cases}\{1\}&(e=1)\\\Z/2\Z&(e=2)\\\Z/2\Z\times\Z/2^{e-2}\Z&(e\ge3)\end{cases}
全部$ \Z/2\Z\times\Z/2^{e-2}\Zで表せるのでは？
$ \Z/1\Z=\{1\}、$ \Z/n\Z\times\{1\}=\Z/n\Zと考えると
$ \Z/2\Z=\Z/2\Z\times\{1\}=\Z/2\Z\times\Z/1\Z
$ \{1\}=\Z/2\Z\times\Z/2^{-1}\Zとも考えられる
これは形式的な置き方
構造
1. $ n=\prod_{p|n}p^{e_p}と素因数分解できるとき$ (\Z/n\Z)^\times\simeq\prod_{p|n}(\Z/p^{e_p}\Z)^\times $ \Z/n\Z\simeq\prod_{p|n}\Z/p^{e_p}\Z
後は$ (\Z/p^{e_p}\Z)^\timesのみ調べれば良い
2. $ (\Z/p\Z)^\times
補題
$ d|p-1なら$ x^d\overset p\equiv1は丁度$ d個の解を持つ
$ p-1=d\,e とする
$ x^{p-1}\overset p\equiv1 は$ [1,p-1]\subset\N の$ p-1個の解を持つ
$ x^{p-1}-1=(x^d)^e-1=(x^d-1)(\sum_{i=0}^{e-1}(x^d)^i)\overset p\equiv0
解を$ (x^d-1)\overset p\equiv0の$ d個と$ \sum_{i=0}^{e-1}(x^d)^i\overset p\equiv0の$ d(e-1)個に分けられる
ほんと？.iconSummer498.icon
ここ because じゃなくない？
本題
$ ^{\forall p\in\mathbb P}(\Z/p\Z)^\timesは巡回群になる $ (\Z/p\Z)^\timesの位数は$ p-1なので、位数$ p-1の元の存在を示せば良い $ p-1=\prod_{i=1}^tq_i^{e_i}と因数分解する
$ \begin{cases}x^{q_i^{e_i-1}}\overset p{\not\equiv}1\\x^{q_i^{e_i}}\overset p\equiv1\end{cases}を満たす$ x=g_iが存在
補題より
$ g=\prod_{i=1}^tg_i\quad\left({\rm ord}(g_i)\overset{{\rm mod}\,p}{=}q_i^{e_i}\right)とすると$ {\rm ord}(g)\overset{{\rm mod}\,p}=p-1
3. $ (\Z/p^{e_p}\Z)^\times
1. $ {\rm mod}\,pの原始根でも$ {\rm mod}\,p^2の原始根でもある$ gを取る
$ {\rm mod}\,pに置ける原始根$ g_pまたは$ g_p+pは$ g^{p-1}\overset{p^2}{\not\equiv}1を満たす$ gになる
$ \left[g^{p-1}\overset p\equiv1\right]\Rightarrow\left[(g+p)^{p-1}\overset{p^2}\equiv g^{p-1}+(p-1)g^{p-2}p\not\equiv1\right]
2. $ g^{\varphi(p^n)}=g^{p^{n-1}(p-1)}=a_np^n+1\quad(a_n\not|p)と書けることを示す
$ n=1のときの成立を示す
$ gは$ {\rm mod}\,pの原始根でも$ {\rm mod}\,p^2の原始根でもあるため、
$ g^{\varphi(p)}=g^{(p-1)}=a_1p+1\quad(a_1\not|p)と書ける
条件が$ {\rm mod}\,pの原始根だけでも成立するのかが気になるSummer498.icon
$ n=kのときの成立を仮定
$ g^{\varphi(p^k)}=g^{p^{k-1}(p-1)}=a_kp^k+1\quad(a_k\not|p)
$ g^{\varphi(p^{k+1})}=g^{p^k(p-1)}=\left\{g^{p^{k-1}(p-1)}\right\}^p
$ =\{a_kp^k+1\}^p
$ =\sum_{i=0}^p\,_pC_i(a_kp^k)^i
$ =1+a_kp^{k+1}p^{kp-(k+1)}+\sum_{i=1}^{p-1}\frac{(p-1)!}{(p-i)!i!}a_kp^{k+1}
$ =1+a_{k+1}p^{k+1}\quad\left(a_{k+1}=\left(p^{kp-(k+1)}+\sum_{i=1}^{p-1}\frac{(p-1)!}{(p-1)!i!}\right)\!\!a_k\right)
3. 2より$ gは$ {\rm mod}\,p^nの原始根になる
$ \because
1. $ g^{\varphi(p^n)}=g^{p^{n-1}(p-1)}=a_np^n+1\overset{p^n}\equiv1
2. $ g^{p^{n-2}(p-1)}=a_{n-1}p^{n-1}+1\overset{p^n}{\not\equiv}1
4. $ (\Z/2^{e_2}\Z)^\times
補題$ e_2\ge3のとき、$ 5^{2^{e_2-3}}\overset{2^e}{\not\equiv}1, $ 5^{2^{e_2-2}}\overset{2^e}\equiv1が成立
証明
$ 5^{2^{e_2-3}}=1+(2k_{e_2}-1)2^{e_2-1}と書けることを示せば良い
1. $ 5=1+1\cdot2^2より$ k_3=1
2. $ 5^{2^{i-3}}=1+(2k_i-1)\cdot2^{i-1}の成立を仮定する
$ 5^{2^{(i+1)-3}}=\left(5^{2^{i-3}}\right)^2
$ =\left(1+(2k_i-1)\cdot2^{i-1}\right)^2
$ =1+(2k_i-1)\cdot2^{(i+1)-1}+(2k_i-1)\cdot2^{2(i-1)}
$ =1+((2k_i-1)\cdot2^{i-2}+2k_i-1)\cdot2^{(i+1)-1}
$ =1+(2k_{i+1}-1)\cdot2^{(i+1)-1}
本題
$ (\Z/2^{e_2}\Z)^\times\simeq\begin{cases}\{1\}&e=1\\\Z/2\Z&e=2\\\Z/2\Z\times\Z/2^{e_2-2}\Z&e\ge3\end{cases}
証明
$ e=1,2については実際に$ {\rm mod}\,2,4を調べれば良い