ベキ根を求める手続きがうまくいかないとき - Ex 17.4

今日もシルヴァーマン『はじめての数論』の演習問題をやっていきます．

はじめての数論 原著第4版

今回やるのは演習17.4です．

\[ %%% 黒板太字 %%% \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} %%% カリグラフィー %%% \newcommand{\calf}{\mathcal{F} } \newcommand{\calg}{\mathcal{G} } %%% 引数を取るもの %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \newcommand{\im}{\operatorname{im} } \]

問題文

$x^ k \equiv b \mod m$ を解く私たちの方法では，まず整数 $u,v$ で $ku - φ(m) v = 1$ を満たすものを求める．そのとき解は $x \equiv b^ u \mod m$ である．しかし，オイラーの公式 $b^ {φ(m)} \equiv 1 \mod m$ を使ったので，$\gcd(b,m) = 1$ のときに限りこの方法がうまくいくことを示しただけである．

(a) $m$ が相異なる素数の積であるとき，$x \equiv b^ u \mod m$ は，たとえ $\gcd(b,m)>1$ だとしても，いつでも $x^ k \equiv b \mod m$ の解であることを示せ．

(b) 私たちの方法は合同式 $x^ 5 \equiv 6 \mod 9$ ではうまくいかないことを示せ．

回答

問a

中国式剰余定理でアレすればOK．

ノートを貼っておきます．

問b

普通に計算すると $x^ 5 \equiv 0$ となって失敗する，というだけです．

感想とまとめ

この問題は，あとでRSA暗号の手続きを説明する時に必要になります．

秘密鍵 $p,q$ を相異なる素数とすることには，そんな理由があったんですね．