アルゴリズム論特論（塩田）第11回 (2)　位数
前へ / 戻る / 次へ $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$ $\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

位数

　前ページの観察で $e$ と書いた数はとても重要な役割を果たしますので名前が付いています。
Def.1　$p$ を素数、$a \in \znzc{p}$ とするとき、 $a^e = 1$ となる最小の自然数を「 元 $a$ の位数 (いすう, order) 」と呼ぶ。
Ex.2　$p=3$ のとき
  • $1$ の位数は $1$
  • $2$ の位数は $2$
    $\because\quad 2^1=2\neq 1,\quad 2^2=1$.
$p=5$ のとき
  • $1$ の位数は $1$
  • $2$, $3$ の位数は $4$
    $\because\quad 2^1=2\neq 1,\quad 2^2=4\neq 1,\quad 2^3=3\neq 1,\quad 2^4=1$,
    $\phantom{\because iii} 3^1=3\neq 1,\quad 3^2=4\neq 1,\quad 3^3=2\neq 1,\quad 3^4=1$.
  • $4$ の位数は $2$
    $\because\quad 4^1=4\neq 1,\quad 4^2=1$.
　「最小の」というところが効いて次の定理が成り立ちます。
Th.3　$a \in \znzc{p}$ の位数を $e$ とするとき、 $a^f=1$ であることと、$f$ が $e$ の倍数であることは同値である。
証明　$\Rightarrow$)　$f$ を $e$ で割って
$f = e q + r$   ( $0 \leqq r \lt e$ )
とおくと
$1 = a^f = (a^e)^q \times a^r = 1^q \times a^r = a^r$
となりますが、$e$ の最小性から $r = 0$. 従って $f$ は $e$ の倍数になります。
$\Leftarrow$)　$f = e k$ とおけるので $a^f = (a^e)^k = 1^k = 1$.(証明終)

前へ / 戻る / 次へ