群の位数と元の位数

加法群 $\mathbb{Z}/36\mathbb{Z}$ において、元 $\overline{27}$（$27$ を代表とする剰余類）の位数を求めよ。

加法群 $\mathbb{Z}/36\mathbb{Z}$ を考える。その元 $\overline{k}$（$k=0,1,2,\dots ,35$）のうち、位数がちょうど $12$ であるものの個数を求めよ。

加法群 $\mathbb{Z}/40\mathbb{Z}$ を考える。その元を $k=0,1,2,\dots ,39$ の剰余類で表す。$\mathbb{Z}/40\mathbb{Z}$ の元のうち、位数がちょうど $8$ であるものの個数を求めよ。

四元数全体 $\mathbb{H}$ の中の単位四元数全体 $S^3=\{q\in \mathbb{H}:|q|=1\}$ を考える。
$$x=\cos \frac{\pi }{3}+i\sin \frac{\pi }{3},y=j$$
で生成される $S^3$ の部分群を $G$ とし、$G$ を左からの積で $S^3$ に作用させた商空間 $X=G\backslash S^3$ を考える。$X$ の基本群 ${\pi }_1(X)$ の位数と、そのアーベル化 ${\pi }_1(X{)}^{\mathrm{ab}}={\pi }_1(X)/[{\pi }_1(X),{\pi }_1(X)]$ の位数を、この順に組で答えよ。

加法群の直積 $G=\mathbb{Z}/12\mathbb{Z}\times \mathbb{Z}/18\mathbb{Z}$ を考える。$G$ の部分群のうち、位数が $6$ の巡回群であるものの個数を求めよ。

有限アーベル群 $G=\mathbb{Z}/3\mathbb{Z}\times \mathbb{Z}/9\mathbb{Z}$ の部分群全体を包含関係で順序づけた半順序集合（部分群束）を $L(G)$ とし、$\mu$ を $L(G)$ のメビウス関数とする。$$S=\sum _{H\in L(G)}\mu (H,G)|H{|}^2$$ の値を求めよ。ただし $|H|$ は部分群 $H$ の位数を表す。

有限群 $G$（単位元を $e$ とする）が、元の個数 $k$（$k$ は正の整数）の集合 $X$ に左から推移的に作用しているとする。すなわち、任意の $x,y\in X$ に対して $g\cdot x=y$ となる $g\in G$ が存在する。$g\in G$ が固定点をもたないとは、$g\cdot x=x$ を満たす $x\in X$ が存在しないことをいう。

各 $x\in X$ の固定部分群 $G_x=\{g\in G\mid g\cdot x=x\}$ が $G$ の部分群であること、および軌道・固定部分群定理（$x\in X$ の軌道 $G\cdot x$ について $|G\cdot x|=[G:G_x]$）とラグランジュの定理は用いてよい。

このとき、固定点をもたない $G$ の元は少なくとも $k-1$ 個あることを証明せよ。

$q$ を奇素数の冪とし、${\mathbb{F}}_q$ を位数 $q$ の有限体とする。$S{L}_2({\mathbb{F}}_q)=\{A\in M_2({\mathbb{F}}_q)\mid \det A=1\}$ とおき、$I$ を $2$ 次の単位行列とする。このとき、$S{L}_2({\mathbb{F}}_q)$ の位数 $2$ の元はちょうど $1$ 個であり、それは $-I$ であることを証明せよ。体上の線形代数の基本事項（最小多項式、最小多項式が相異なる $1$ 次式の積に分解するとき行列が対角化可能であること）は用いてよい。

$p$ を奇素数とする。$p$ と互いに素な整数 $b$ の $p$ を法とする位数とは、$b^m\equiv 1(\mathrm{mod}p)$ をみたす最小の正の整数 $m$ のことであり、位数が $p-1$ である整数を $p$ を法とする原始根という。$g$ を $p$ を法とする原始根とする。

ディフィー・ヘルマン鍵共有では、秘密の 0 以上の整数 $a$ に対して $A=g^a$ を $p$ で割った余りが公開される。このとき、すべての 0 以上の整数 $a$ に対して
$${\left(g^a\right)}^{\frac{p-1}{2}}\equiv (-1{)}^a(\mathrm{mod}p)$$
が成り立つこと（したがって公開された値から秘密 $a$ の偶奇がわかること）を証明せよ。

ただし、次の事実は用いてよい。
- $p$ と互いに素な整数 $b$ の位数を $e$ とすると、0 以上の整数 $m$ について $b^m\equiv 1(\mathrm{mod}p)$ となるのは $e\mid m$ のとき、かつそのときに限る
- 素数 $p$ が整数の積 $uv$ を割り切るならば、$p\mid u$ または $p\mid v$ である

$p$ を $p\equiv 2(\mathrm{mod}3)$ をみたす素数とし、$F(X,Y)\in {\mathbb{F}}_p[X,Y]$ を 3 次斉次多項式または零多項式とする。射影平面 ${\mathbb{P}}^2$ の曲線
$$C:Z^3=F(X,Y)$$
の ${\mathbb{F}}_p$ 有理点の集合を
$$C({\mathbb{F}}_p)=\{[X:Y:Z]\in {\mathbb{P}}^2({\mathbb{F}}_p)\mid Z^3=F(X,Y)\}$$
と定める（両辺はともに 3 次斉次なので、この条件は斉次座標の取り方によらない）。このとき、$F$ の取り方によらず
$$\#C({\mathbb{F}}_p)=p+1$$
であることを証明せよ。ただし、有限群の元の位数は群の位数を割り切ること（ラグランジュの定理）は用いてよい。

0 胞体 $x_0$ を 1 つ、1 胞体 $a,b$ を 2 つもち（それぞれ $x_0$ を基点とするループとして向きを定める）、2 胞体 $e_1,e_2$ を、境界がそれぞれループ $a^3$、$b^2$ に沿うように貼り付けて得られる CW 複体を $X$ とする。基本群 $G={\pi }_1(X,x_0)$ は無限群であるが、そのアーベル化 $G^{\mathrm{ab}}=G/[G,G]$ は位数 $6$ の有限群であることを証明せよ。ここで $[G,G]$ は $G$ の交換子部分群である。

ただし、次の事実は証明なしに用いてよい: 連結な CW 複体の 1 骨格が 1 点で束ねた円周の族で、その円周に対応するループを $g_1,\dots ,g_r$ とするとき、2 胞体を接着写像のループ $w_1,\dots ,w_s$ に沿って貼り付けた空間の基本群は、群の表示 $⟨g_1,\dots ,g_r\mid w_1,\dots ,w_s⟩$ で与えられる（ファン・カンペンの定理の帰結）。

RSA 暗号の公開鍵として、相異なる 2 つの素数 $p,q$ の積 $n=pq=2257$ と暗号化指数 $e=13$ が公開されている。暗号化は、平文 $m$（$0\le m\le n-1$ を満たす整数）に対して
$$c\equiv m^e(\mathrm{mod}n),0\le c\le n-1$$
で行う。いま、攻撃者はオイラー関数の値 $\phi (n)=(p-1)(q-1)=2160$ を知ったとする。

暗号化しても値が変わらない平文、すなわち
$$m^{13}\equiv m(\mathrm{mod}2257),0\le m\le 2256$$
を満たす整数 $m$ の個数を求めよ。

合成数 $n=143$ を法とする離散対数を考える。
$$2^x\equiv 19(\mathrm{mod}143)$$
を満たす最小の正の整数 $x$ を求めよ。

正十角形の頂点に、反時計回りに $1,2,\dots ,10$ と番号を付ける。この正十角形を自分自身に重ねる合同変換（回転と裏返し）全体は位数 $20$ の二面体群 $D_{10}$ をなす。各変換を頂点の番号の置換とみなすことで、$D_{10}$ を $10$ 次対称群 $S_{10}$ の部分群 $H$ とみなす。

$S_{10}$ の元 $\sigma$ のうち、$H$ のある元と $S_{10}$ の中で共役であるもの（すなわち $\sigma \in {\bigcup }_{g\in S_{10}}gH{g}^{-1}$ を満たすもの）の個数を求めよ。

${\mathbb{F}}_7$ を位数 $7$ の有限体とし、$G=G{L}_2({\mathbb{F}}_7)$ を ${\mathbb{F}}_7$ の元を成分とする $2\times 2$ 正則行列全体が行列の積についてなす群とする。$G$ の元のうち、位数がちょうど $3$ であるものの個数を求めよ。

${\mathbb{F}}_3$ を位数 $3$ の有限体とし、$G=G{L}_3({\mathbb{F}}_3)$ を ${\mathbb{F}}_3$ の元を成分とする $3$ 次正則行列全体が行列の積についてなす群とする。$G$ の元のうち、位数がちょうど $2$ であるもの（すなわち $A^2=I$ かつ $A\ne I$ を満たす $A\in G$）の個数を求めよ。

位数 $12$ の二面体群
$$G=⟨r,s\mid r^6=s^2=1,sr{s}^{-1}=r^{-1}⟩$$
を考える（正六角形の合同変換全体のなす群）。$G$ の部分群全体を包含関係で順序づけた半順序集合（部分群束）を $L(G)$ とし、その最小元は自明な部分群 $1=\{e\}$、最大元は $G$ である。$L(G)$ のメビウス関数を $\mu$ とするとき、$\mu (1,G)$ の値を求めよ。

$60$ と互いに素な剰余類全体がなす乗法群を $G=(\mathbb{Z}/60\mathbb{Z}{)}^{\times }$ とする。$G$ の部分群のうち、位数がちょうど $4$ であるものの個数を求めよ。

加法群の直積 $G=\mathbb{Z}/8\mathbb{Z}\times \mathbb{Z}/4\mathbb{Z}$ を考える。$G$ の位数がちょうど $4$ である元の個数を $a$、$G$ の位数 $4$ の部分群の個数を $b$ とする。組 $(a,b)$ をこの順に求めよ。

$5$ 次対称群 $S_5$ を考える。$S_5$ の位数 $3$ の部分群の個数を $p$、位数 $4$ の巡回部分群の個数を $q$、位数 $5$ の部分群の個数を $r$ とする。組 $(p,q,r)$ をこの順に求めよ。

$p=1009$ とする（$p$ は素数である）。有限体 ${\mathbb{F}}_p$ 上の楕円曲線
$$E:y^2=x^3-x$$
について、$E$ の ${\mathbb{F}}_p$ 有理点全体 $E({\mathbb{F}}_p)$ の個数（無限遠点 $O$ を含む）を求めよ。

$G$ を位数 $2023$ の群とし、$G$ は位数 $289$ の元をもたないとする。$G$ の元のうち、位数がちょうど $119$ であるものの個数を求めよ。

${\mathbb{F}}_7$ を位数 $7$ の有限体とし、$$G=\{f_{a,b}:{\mathbb{F}}_7\to {\mathbb{F}}_7,f_{a,b}(x)=ax+b\mid a\in {\mathbb{F}}_7^{\times },b\in {\mathbb{F}}_7\}$$ を写像の合成に関する群（位数 $42$）とする。${\mathbb{F}}_7$ の各元に赤・青・緑の $3$ 色のいずれかを塗る塗り方全体の集合を $X$ とする（$|X|=3^7$）。$c\in X$ を写像 $c:{\mathbb{F}}_7\to \{\text{赤},\text{青},\text{緑}\}$ とみなし、$g\in G$ を $(g\cdot c)(x)=c(g^{-1}(x))$ によって $X$ に作用させる。この作用の軌道の個数を求めよ。

素数 $p=37$ について、$2$ は法 $37$ の原始根である（$2$ の法 $37$ での位数は $36$）ことを用いてよい。

$1\le a\le 36$ を満たす整数 $a$ のうち、法 $37$ における位数（$a^k\equiv 1(\mathrm{mod}37)$ となる最小の正の整数 $k$）がちょうど $12$ であるものをすべて考える。それらの $a$ の総和を求めよ。

${\mathbb{F}}_5$ を位数 $5$ の有限体とし、$$G=\{{\phi }_{a,b}:{\mathbb{F}}_5\to {\mathbb{F}}_5,{\phi }_{a,b}(x)=ax+b\mid a\in {\mathbb{F}}_5^{\times },b\in {\mathbb{F}}_5\}$$ を写像の合成を積とする群（位数 $20$）とする。写像 $f:{\mathbb{F}}_5\to \{1,2,3\}$ 全体の集合を $X$ とし（$|X|=3^5$）、$G$ は $X$ に $$(g\cdot f)(x)=f\left(g^{-1}(x)\right)(g\in G,f\in X,x\in {\mathbb{F}}_5)$$ によって作用する。この作用による $X$ の軌道の個数を求めよ。

$p$ を素数とし、$L/K$ を拡大次数 $[L:K]=p^2$ の有限次ガロア拡大とする。$K⊊M⊊L$ をみたす中間体 $M$ の個数を $N$ とする。

このとき、$N=1$ または $N=p+1$ であることを証明せよ。

ただし、ガロア理論の基本定理と、位数 $p^2$ の群は巡回群 $\mathbb{Z}/p^2\mathbb{Z}$ または $\mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/p\mathbb{Z}$ のいずれかに同型であることは用いてよい。

$n$, $k$ を正の整数とし、$\phi$ をオイラー関数（正の整数 $d$ に対し、$1\le s\le d$ で $\gcd (s,d)=1$ を満たす整数 $s$ の個数）とする。このとき
$$\sum _{d\mid n}\phi (d)k^{n/d}$$
は $n$ で割り切れることを、バーンサイドの補題を用いて証明せよ。ここで ${\sum }_{d\mid n}$ は $n$ の正の約数 $d$ すべてについての和を表す。

ただし、バーンサイドの補題（有限群 $G$ が有限集合 $X$ に作用するとき、軌道の個数は $\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$ に等しい。$\mathrm{Fix}(g)=\{x\in X:gx=x\}$）と、整数 $a,b$（少なくとも一方は $0$ でない）に対して $ax+by=\gcd (a,b)$ を満たす整数 $x,y$ が存在することは用いてよい。

$p$ を奇素数、$g$ を $p$ を法とする原始根とする。$p$ と互いに素な整数 $c$ について、$y^2\equiv c(\mathrm{mod}p)$ をみたす整数 $y$ が存在するとき $c$ を $p$ を法とする平方剰余、存在しないとき平方非剰余という。

アリスとボブが群 $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ 上でディフィー・ヘルマン鍵共有を行う。アリスは秘密の正の整数 $a$、ボブは秘密の正の整数 $b$ を選び、$A\equiv g^a(\mathrm{mod}p)$、$B\equiv g^b(\mathrm{mod}p)$ を公開し、共有鍵を $K\equiv g^{ab}(\mathrm{mod}p)$ とする。

このとき、「$K$ が $p$ を法とする平方非剰余であるための必要十分条件は、$A$ と $B$ がともに $p$ を法とする平方非剰余であることである」を証明せよ。ただし、原始根の定義（$g$ の位数が $p-1$ であり、$p$ と互いに素な任意の整数は $p$ を法としてある $g^t$（$0\le t\le p-2$）と合同になること）と、「$g^m\equiv 1(\mathrm{mod}p)$ となる整数 $m\ge 0$ は $p-1$ の倍数に限る」ことは用いてよい。

${\mathbb{F}}_2$ を元の個数が $2$ の有限体とする。${\mathbb{F}}_2$ 上の $8$ 次のモニック既約多項式（最高次の係数が $1$ である既約多項式）$f(x)$ のうち、原始多項式でないものの個数を求めよ。ただし、${\mathbb{F}}_2$ 上の $8$ 次既約多項式 $f(x)$ が原始多項式であるとは、$f(x)$ の根（元の個数が $2^8=256$ の有限体 ${\mathbb{F}}_{256}$ の中の根）が乗法群 ${\mathbb{F}}_{256}^{\times }$ の生成元であることをいう。

正 $12$ 角形の対称性全体がなす二面体群
$$D_{12}=⟨r,s\mid r^{12}=s^2=e,sr{s}^{-1}=r^{-1}⟩$$
を考える。$D_{12}$ の位数は $24$ であり、その元は $r^i$ と $r^{i}s$（$0\le i\le 11$）で重複なく表される。$D_{12}$ の部分群の個数を求めよ。ただし、単位元だけからなる部分群 $\{e\}$ と $D_{12}$ 自身も数える。

$Q_8=\{\pm 1,\pm i,\pm j,\pm k\}$ を四元数群とする（$i^2=j^2=k^2=ijk=-1$）。また、$C_4=⟨z⟩$ を位数 $4$ の巡回群とし、直積群
$$G=Q_8\times C_4$$
を考える。$G$ の自己同型群 $\mathrm{Aut}(G)$（$G$ から $G$ への群同型全体が写像の合成についてなす群）の位数 $|\mathrm{Aut}(G)|$ を求めよ。

${\mathbb{F}}_3$ を元の個数が $3$ の有限体とする。${\mathbb{F}}_3$ 上の $4$ 次のモニック既約多項式 $f(x)$（最高次の係数が $1$ である既約多項式）のうち、次の条件を満たすものの個数を求めよ。

条件: $f(x)$ の根 $\alpha$（元の個数が $81$ の有限体 ${\mathbb{F}}_{81}$ の元）の乗法群 ${\mathbb{F}}_{81}^{\times }$ における位数が $80$ ではない。

$1001=7\cdot 11\cdot 13$ とする。$1$ 以上 $1000$ 以下の整数 $a$ で $\gcd (a,1001)=1$ を満たすもののうち、$1001$ を法とする位数がちょうど $12$ であるもの（すなわち $a^{12}\equiv 1(\mathrm{mod}1001)$ かつ $1\le k<12$ なる整数 $k$ に対して $a^k\not\equiv 1(\mathrm{mod}1001)$）の個数を求めよ。

$N=12096=2^6\cdot 3^3\cdot 7$ とする。$N$ と互いに素な整数 $a$ に対し、$a^k\equiv 1(\mathrm{mod}N)$ をみたす最小の正の整数 $k$ を法 $N$ における $a$ の位数という。$N$ と互いに素な整数の法 $N$ における位数としてとりうる値のうち最大のものを $L$ とする。$1\leqq a\leqq N-1$ をみたし $N$ と互いに素な整数 $a$ のうち、法 $N$ における位数がちょうど $L$ であるものの個数を求めよ。

$n=360$ とする。
$$S=\sum _{\begin{array}{c}1\leqq k\leqq n\\ \gcd (k,n)=1\end{array}}\gcd (k-1,n)$$
の値を求めよ。ただし和は $1\leqq k\leqq 360$ かつ $360$ と互いに素な整数 $k$ すべてにわたってとり、$\gcd (0,n)=n$ とする。

$N=520$ とする。法 $N$ のディリクレ指標とは群準同型 $\chi :(\mathbb{Z}/N\mathbb{Z}{)}^{\times }\to {\mathbb{C}}^{\times }$ のことで、$\gcd (n,N)>1$ のとき $\chi (n)=0$ と定めて整数全体の関数とみなす。法 $N$ のディリクレ指標全体は積について群をなし、その中での $\chi$ の位数を単に $\chi$ の位数という。また、$\chi$ が $N$ の真の約数 $M$ を法とする指標から誘導されないとき、$\chi$ は原始的であるという。

法 $520$ のディリクレ指標 $\chi$ で、次の $3$ つの条件をすべて満たすものの個数を求めよ。

$(1)$ $\chi$ は原始的である。

$(2)$ $\chi$ の位数はちょうど $4$ である。

$(3)$ $\chi (-1)=1$ である。

ディフィー・ヘルマン鍵共有の公開パラメータとして、素数 $p=71$ と、法 $71$ の原始根 $g$ を選びたい。ここで整数 $g$ が法 $71$ の原始根であるとは、$g$ の法 $71$ における位数（$g^k\equiv 1(\mathrm{mod}71)$ を満たす最小の正の整数 $k$）が $70$ であることをいう。

$1\le g\le 70$ を満たす法 $71$ の原始根 $g$ のうち、最小のものを求めよ。

有限体 ${\mathbb{F}}_{23}$ 上の楕円曲線
$$E:y^2=x^3+2x+9$$
を考える。$E$ の ${\mathbb{F}}_{23}$ 有理点全体は、無限遠点 $O$ を単位元とし、通常の加法（弦と接線による加法）で群をなす。点 $P=(0,3)\in E({\mathbb{F}}_{23})$ について、$nP=O$ となる最小の正の整数 $n$（$P$ の位数）を求めよ。