今日もシルヴァーマン『A Friendly Introduction to Number Theory』の演習問題をやっていきます．
邦訳がこちら．
原著はこちら．
問題文
この章で私たちは $m$ を法とした $b$ の $k$ 乗根をどのように解くかについて述べた．しかし，あなたはおそらく $b$ の $k$ 乗根が１つよりも多くあり得るのか自問したことだろう．実際，それは可能である！たとえば，$a$ が $m$ を法として $b$ の平方根であれば，明らかに $-a$ も $m$ を法として $b$ の平方根になっている．
(a) $b,k,m$ を
$$ \gcd(b,m) = 1, \quad \gcd(k,φ(m)) = 1 $$
を満たす整数とする．$b$ は $m$ を法としてただひとつの $k$ 乗根をもつことを示せ．
(b) 代わりに $\gcd(k,φ(m)) > 1$ とせよ．$b$ は $m$ を法として $k$ 乗根を持たないか，あるいは少なくとも２つの根を持つことを示せ．（現時点までに扱ってきた題材では，この問題は難問である．）
(c) $m=p$ が素数のとき，例をいくつか調べ，$p$ を法とした（少なくとも１つはあると仮定したときの）$b$ の $k$ 乗根の個数の公式を見つけることに挑戦せよ．
問c の回答
$m = p$ が素数なので $\mathbb{Z}_m^*$ は巡回群です．
したがって，その原始根を $g$ とすると方程式 $x^ k = b \mod p$ は $g^ {zk} = g^ β$ と書き換えることができます．つまり $zk - β \equiv 0 \mod (p-1)$ です．これで冪乗根を求める問題を，一次合同式に書き換えることができました．
これにより，$b$ の $k$ 乗根の数は，$zk - \beta \equiv 0 \mod p-1$ の解の個数と一致することがわかりました．
$k$ が $φ(p) = p-1$ と互いに素ならば，解はちょうどひとつ存在します．
$\gcd(k, φ(p)) = g > 1$ とします．このときは法 $(p-1)/g$ に関して解がただひとつ存在するか，あるいは解が存在しないかのどちらかです．存在する場合には，解は法 $p-1$ に関して $g$ 個存在します．
感想とまとめ
これで長かった演習問題17.3も終わりです．
回答だけ書いたので悩んでないように見えますが，私は結構問b で悩みました．
最初にどういう勘違いをしていたか書こうと思っていたのですが，あまりにも救いようのない勘違いだったので省略しました．
