最大公約数と最小公倍数

2 つの正の整数 $a,b$ の最大公約数が $12$、最小公倍数が $180$ であるとする。$a=36$ のとき、$b$ を求めよ。

2 つの正の整数 $a,b$ は $a<b$ を満たしています。$a$ と $b$ の最大公約数は $8$、最小公倍数は $240$ で、$a+b=88$ です。組 $(a,b)$ を求めよ。

2 つの正の整数 $a,b$ $(a<b)$ があり、最大公約数は $6$、最小公倍数は $72$ である。$a,b$ がともに 2 けたの整数であるとき、組 $(a,b)$ を求めよ。

正の整数 $n$ に対して、$3n+7$ と $5n+2$ の最小公倍数を $L$ とする。$n\leqq 200$ を満たす正の整数 $n$ のうち、
$$L=\frac{(3n+7)(5n+2)}{29}$$
が成り立つものすべての和を求めよ。

$n$ は $1\leqq n\leqq 200$ を満たす整数とする。2 つの整数 $n^2+2$ と $n+4$ の最大公約数が $6$ となるような $n$ の個数を求めよ。

赤い玉 4 個と青い玉 6 個（同じ色の玉どうしは区別しない）の計 10 個を、円周上に等間隔に並べた 10 か所に 1 個ずつ置き、ひもを通して輪（ブレスレット）を作る。輪の回転および裏返しによって互いに重ね合わせられる並べ方は同じものとみなすとき、異なる輪は何通りできるか。

$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$ が存在することは用いてよい。

実数 $x$ に対して、$x$ を超えない最大の整数を $[x]$ で表す。$m$ を正の整数とし、$n=2^m$ とおく。このとき、和
$$S=\sum _{i=1}^{n-1}\sum _{j=1}^{n-1}\left[\frac{ij}{n}\right]$$
を $m$ の式で表せ。

英字 $26$ 文字を $\mathrm{A}=0,\mathrm{B}=1,\dots ,\mathrm{Z}=25$ と数に対応させ、$\mathbb{Z}/26\mathbb{Z}$ の元とみなす。正の整数 $m$ と鍵 $K=(k_0,k_1,\dots ,k_{m-1})\in (\mathbb{Z}/26\mathbb{Z}{)}^m$ に対し、鍵の長さ $m$ のヴィジュネル暗号は、平文 $x_0{x}_1{x}_2\cdots$ を
$$y_j\equiv x_j+k_{j\mathrm{mod}m}(\mathrm{mod}26)(j=0,1,2,\dots )$$
で暗号文 $y_0{y}_1{y}_2\cdots$ に変換する（$j\mathrm{mod}m$ は $j$ を $m$ で割った余り）。鍵の成分はどれも $0$ から $25$ の任意の値をとってよいものとする。

いま、長さ $18$ の文字列全体の集合 $(\mathbb{Z}/26\mathbb{Z}{)}^{18}$ 上で、まず鍵の長さ $6$ の鍵 $K=(k_0,\dots ,k_5)$ でヴィジュネル暗号化し、その結果をさらに鍵の長さ $9$ の鍵 $L=(l_0,\dots ,l_8)$ でヴィジュネル暗号化する二重暗号化を考える。鍵の組 $(K,L)$ は全部で $26^{15}$ 通りある。

鍵の組 $(K,L)$ をすべて動かしたとき、この二重暗号化によって得られる $(\mathbb{Z}/26\mathbb{Z}{)}^{18}$ から $(\mathbb{Z}/26\mathbb{Z}{)}^{18}$ への写像は何通りあるか。答えは $26$ の累乗の形で答えよ。

$K$ を体、$L$ を $K$ の有限次拡大体とし、$m=[L:K]$ とおく。$f(x)\in K[x]$ を $K$ 上既約な $n$ 次多項式（$n$ は正の整数）とし、$e=\gcd (m,n)$ とおく。$f(x)$ を $L[x]$ の多項式とみて
$$f(x)=c{p}_1(x)p_2(x)\cdots p_r(x)(c\in L,c\ne 0)$$
と、$L$ 上既約なモニック多項式 $p_1(x),\dots ,p_r(x)\in L[x]$（同じものがあってもよい）の積に分解する。このとき、因子の個数 $r$ は $r\le e$ を満たすことを証明せよ。

ただし、次の事実は用いてよい。
- $L[x]$ の次数 $1$ 以上の多項式は、上のように $L$ 上既約なモニック多項式の積に分解できる
- 拡大次数の連鎖律: 体の拡大 $F\subset E\subset M$ について $[M:F]=[M:E][E:F]$（右辺の 2 つが有限ならば左辺も有限であり、左辺が有限ならば右辺の 2 つも有限である）
- 体 $F$ 上の多項式 $g(x)$（次数 $1$ 以上）に対して、$g(x)$ が根をもつような $F$ の拡大体が存在する
- $\alpha$ が体 $F$ 上代数的ならば、$[F(\alpha ):F]$ は $\alpha$ の $F$ 上の最小多項式の次数に等しく、$\alpha$ を根にもつ $F[x]$ の多項式はすべて最小多項式で割り切れる

正の整数 $n$ に対して
$$f(n)=\#\{(a,b)\in {\mathbb{Z}}_{>0}^2:\mathrm{lcm}(a,b)=n\}$$
とおく（$\mathrm{lcm}(a,b)$ は $a,b$ の最小公倍数）。また、複素数 $s$ に対して $\sigma =\mathrm{Re}s$ と書き、$\sigma >1$ のとき $\zeta (s)={\sum }_{n=1}^{\infty }{n}^{-s}$ とする。

$\mathrm{Re}s>1$ を満たす任意の複素数 $s$ に対して、ディリクレ級数 ${\sum }_{n=1}^{\infty }f(n)n^{-s}$ は絶対収束し、$\zeta (2s)\ne 0$ であって
$$\sum _{n=1}^{\infty }\frac{f(n)}{n^s}=\frac{\zeta (s{)}^3}{\zeta (2s)}$$
が成り立つことを証明せよ。

ただし、素因数分解の一意性、$\sigma >1$ で ${\sum }_{n=1}^{\infty }{n}^{-\sigma }$ が収束すること、絶対収束する級数の項の並べ替えと、絶対収束する有限個の級数の積の展開（コーシー積）は用いてよい。$\zeta$ のオイラー積表示は用いる場合には証明すること。

$m,n$ は $1\leqq m<n\leqq 60$ を満たす整数とする。$2$ つの整数 $2^m-1$ と $2^n-1$ の最大公約数が $15$ となるような組 $(m,n)$ の個数を求めよ。

$m,n$ は $1\leqq m\leqq 20$, $1\leqq n\leqq 20$ を満たす整数とする。2 つの整数 $4^m-1$ と $8^n-1$ の最大公約数が $63$ となるような整数の組 $(m,n)$ の個数を求めよ。