COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

整数の剰余

整数の剰余

問題≪フィボナッチ数列の加法定理と性質≫

 $m,$ $n$ を非負整数とする. \[ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_n+F_{n+1}\] により定まる数列 $\{ F_n\}$ について, 次のことを示せ.
(1)
$F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1}\ \cdots (P)$ が成り立つ. 
(2)
$0 < m \leqq n$ のとき, $m$ が $n$ を割り切るならば, $F_m$ は $F_n$ を割り切る.
(3)
$F_n,$ $F_{n+1}$ は互いに素である.
(4)
$2 < m \leqq n$ のとき, $F_m$ が $F_n$ を割り切るならば, $m$ は $n$ を割り切る.
(5)
$n \neq 4$ のとき, $F_n$ が素数ならば, $n$ は素数である.

解答例

(1)
$m$ を固定して, $n$ に関する数学的帰納法で $(P)$ を示す.
(i)
$F_0 = 0,$ $F_1 = 1,$ $F_2 = 0+1 = 1$ から \begin{align*} &F_mF_0+F_{m+1}F_1 = F_{m+1}, \\ &F_mF_1+F_{m+1}F_2 = F_m+F_{m+1} = F_{m+2} \end{align*} であるので, $n = 1,$ $2$ のとき $(P)$ が成り立つ.
(ii)
$n = k,$ $k+1$ ($k$: 非負整数)のとき $(P)$ が成り立つとすると, \begin{align*} &F_{m+k+3} \\ &= F_{m+k+1}+F_{m+k+2} \\ &= F_mF_k+F_{m+1}F_{k+1}+F_mF_{k+1}+F_{m+1}F_{k+2} \\ &= F_m(F_k+F_{k+1})+F_{m+1}(F_{k+1}+F_{k+2}) \\ &= F_mF_{k+2}+F_{m+1}F_{k+3} \end{align*} となり, $n = k+2$ のとき $(P)$ が成り立つ.
(i), (ii) から, すべての非負整数 $m,$ $n$ に対して, $(P)$ が成り立つ.
(2)
$m$ を固定して, 正の整数 $q$ に関する数学的帰納法で「$F_m$ が $F_{mq}$ を割り切ること」$\cdots (Q)$ を示す.
(i)
$F_m$ は $F_{m\cdot 1} = F_m$ を割り切るから, $q = 1$ のとき $(Q)$ が成り立つ.
(ii)
$q = k$ ($k$: 正の整数)のとき $(Q)$ が成り立つとすると, $d = \dfrac{F_{mk}}{F_m}$ は整数であるから, $F_m$ は \begin{align*} F_{m(k+1)} &= F_{mk+(m-1)+1} \\ &= F_{mk}F_{m-1}+F_{mk+1}F_m \quad (\because (P)) \\ &= dF_mF_{m-1}+F_{mk+1}F_m \\ &= F_m(dF_{m-1}+F_{mk+1}) \end{align*} を割り切り, $q = k+1$ のとき $(Q)$ が成り立つ.
(i), (ii) から, すべての正の整数 $m,$ $q$ に対して $(Q)$ が成り立つ. これで, 題意が示された.
(3)
$d$ を $F_n,$ $F_{n+1}$ の正の公約数とする. $n > 1$ のとき, $d$ は $F_{n+1}-F_n = F_{n-1}$ を割り切る. これを繰り返すと, $d$ は $F_1 = 1$ を割り切るから, $d = 1$ である. ゆえに, $F_n,$ $F_{n+1}$ は互いに素である.
(4)
$n$ を $m$ で割った商を $q,$ 余りを $r$ とおく. このとき, $n = mq+r,$ $0 \leqq r < m$ であり, $(P)$ から \[ F_n = F_{(mq-1)+r+1} = F_{mq-1}F_r+F_{mq}F_{r+1}\] が成り立つ. (2) から, $F_m$ は $F_{mq}$ を割り切る. また, (3) から $F_{mq-1},$ $F_{mq}$ は互いに素なので, $F_{mq-1},$ $F_m$ は互いに素である. よって, $F_m$ が $F_n$ を割り切るとき, $F_m$ は $F_r$ を割り切る. このとき, $m > 2,$ $r < m$ から $F_r < F_m$ であることに注意すると, $F_r = 0$ から $r = 0$ となるので, $m$ は $n$ を割り切る. これで, 題意が示された.
(5)
$n \neq 4$ のとき, $n$ が素数でないならば $F_n$ は素数でないことを示す. $F_0 = 0,$ $F_1 = 1$ は素数でない. そこで, $n$ を $0,$ $1,$ $4$ でも素数でもない非負整数とする. このとき, $n$ は $2 < m < n$ なる約数 $m$ をもつ. (2) で示したことから, $F_m$ は $F_n$ を割り切る. また, 数列 $\{ F_n\}$ は定義から単調増加なので, $1 = F_2 < F_m < F_n$ である. よって, $F_n$ は, $1$ でも $F_n$ でもない正の約数 $F_m$ を持つから, 素数でない. ゆえに, 対偶は真であるから, 示すべき命題も真である.

背景

  • $\{ F_n\}$ は「フィボナッチ数列」(Fibonacci sequence)と呼ばれ, その多くの性質が「フィボナッチ数列の加法定理」(addition theorem) \[ F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1}\] から導かれる. 本問では, これを証明し, それを使って $F_m$ が $F_n$ を割り切るための必要十分条件と $F_n$ が素数であるための必要条件を求めた.
  • (2), (5) と $F_3 = 2,$ $F_5 = 5$ から,
    $F_n$ が $2$ の倍数 $\iff$ $F_n$ が $F_3$ の倍数 $\iff$ $n$ が $3$ の倍数,
    $F_n$ が $5$ の倍数 $\iff$ $F_n$ が $F_5$ の倍数 $\iff$ $n$ が $5$ の倍数
    の成り立つことがわかる.

問題≪フェルマーの小定理と RSA 暗号の原理≫

 $a,$ $b,$ $a',$ $b',$ $c,$ $n$ を整数とし, $p,$ $q$ を相異なる素数とする. $a-a'$ が $n$ で割り切れるとき, $a \equiv a'\ (\text{mod}\ n)$ と表す. 次のことを示せ.
(1)
$a \equiv a',$ $b \equiv b'\ (\text{mod}\ n)$ ならば, $ab \equiv a'b'\ (\text{mod}\ n)$ が成り立つ.
(2)
$c$ が $p$ の倍数でないとする. このとき, $ac \equiv a'c\ (\text{mod}\ p)$ ならば, $a \equiv a'\ (\text{mod}\ p)$ が成り立つ.
(3)
$a$ が $p$ の倍数でないとき, $p-1$ 以下の正の整数全体から成る集合を $G$ とおき, $k \in G$ なる各整数 $k$ に対して $ak$ を $p$ で割った余りを $r_k$ とおくと, $\{ r_k|k \in G\} = G$ が成り立つ.
(4)
$a$ が $p$ の倍数でないとき, $a^{p-1} \equiv 1\ (\text{mod}\ p)$ が成り立つ.
(5)
$n = pq$ とし, 整数 $e,$ $d$ が \[ ed \equiv 1\ (\text{mod}{(p-1)(q-1)})\] を満たすとする. このとき, $n$ と互いに素な整数 $a,$ $b$ に対して, $a^e \equiv b\ (\text{mod}\ n)$ ならば, $b^d \equiv a\ (\text{mod}\ n)$ が成り立つ.

解答例

(1)
$a \equiv a',$ $b \equiv b'\ (\text{mod}\ n)$ ならば,
$a = a'+n\alpha,$ $b = b'+n\beta$ ($\alpha,$ $\beta$: 整数)
と書けて, \[ ab = a'b'+n(\alpha b'+a'\beta +n\alpha\beta ) \equiv a'b'\ (\text{mod}\ n)\] となる.
(2)
$c$ が $p$ と互いに素であることに注意すると, \begin{align*} ac \equiv a'c\ (\text{mod}\ p) &\iff ac-a'c\text{ は }p\text{ の倍数} \\ &\iff (a-a')c\text{ は }p\text{ の倍数} \\ &\iff a-a'\text{ は }p\text{ の倍数} \\ &\iff a \equiv a'\ (\text{mod}\ p) \end{align*} となる.
(3)
$k \in G,$ $l \in G,$ $k \neq l$ なる整数 $k,$ $l$ に対して, $k \not\equiv l\ (\text{mod}\ p)$ であるから, $a$ が $p$ と互いに素であるという仮定と (2) の対偶から, $ak \not\equiv al\ (\text{mod}\ p)$ が成り立ち, よって $r_k \neq r_l$ が成り立つ.
これは $\{ r_k|k \in G\} = G$ が成り立つことを意味する.
(4)
$k \in G$ なるすべての整数 $k$ について $ak \equiv r_k\ (\text{mod}\ p)$ の辺々を掛けると, (1), (3) から \[ a^{n-1}(p-1)! \equiv (p-1)!\ (\text{mod}\ p)\] となる. $(p-1)!$ は $p$ と互いに素なので, (2) から, $a^{n-1} \equiv 1\ (\text{mod}\ p)$ が成り立つ.
(5)
仮定から, $ed$ はある整数 $k$ を用いて \[ ed = (p-1)(q-1)k+1\] と書ける. よって, \begin{align*} b^d &\equiv (a^e)^d = a^{ed} \\ &= a^{(p-1)(q-1)k+1} = (a^{p-1})^{(q-1)k}a \\ &\equiv 1^{(q-1)k}a = a\ (\text{mod}\ p) \end{align*} が成り立つ. 同様にして, $b^d \equiv a\ (\text{mod}\ q)$ が示される.
よって, $b^d-a$ は $p,$ $q$ の倍数であるが, $p,$ $q$ は相異なる素数であるから, $b^d-a$ は $pq = n$ の倍数である.
すなわち, $b^d \equiv a\ (\text{mod}\ n)$ が成り立つ.

背景

  • (4) の結果は「フェルマーの小定理」(Fermat's little theorem)として知られている.
  • 「フェルマーの小定理」は「オイラーの定理」(Euler's theorem) $a^{\varphi (n)} \equiv 1\ (\text{mod}\ n)$ に一般化される. ここで, $\varphi (n)$ は正の整数 $n$ を $n$ と互いに素な $n$ 以下の正の整数の個数に対応させる関数で, 「オイラーのトーシェント関数」(Euler's (totient) function)と呼ばれる.
  • 上記の整数 $n,$ $e,$ $d$ を用いて,「RSA 暗号」(RSA encryption)と呼ばれる暗号が, 次の方法で実現できる.
    (i)
    公開鍵の公開: $n,$ $e$ の値を送信者と受信者の間で共有する.
    (ii)
    暗号文の送信: 送信者は, 整数 $a$ ($n$ と互いに素, $0 \leqq a < n$)の値を伝えたいとき, $a^e$ を $n$ で割った余り $b$ の値を受信者に送る.
    (iii)
    復号: 受信者は, 秘密にしておいた $d$ の値を用いて, $b^d$ を $n$ で割った余りを計算して, 送信者がもともと伝えたかった整数 $a$ の値を求める.
     本問では, (iii) の方法でなぜもとの値が求まるのかを示した. $n$ が相異なる素数 $p,$ $q$ の積であるとき $\varphi (n) = (p-1)(q-1)$ であるから, 復号には $n = pq$ の場合の「オイラーの定理」$a^{\varphi (n)} \equiv 1\ (\text{mod}\ n)$ を利用している.
     この暗号方式には, 受信者が $n,$ $e$ の値を公開するだけで複数の送信者に安全に暗号化の方法を知らせられるという利点がある. このような暗号を「公開鍵暗号」(public-key encryption)と呼ぶ. 「RSA 暗号」は, 電子メールやインターネット通信, カード情報の処理など, さまざまな場面で使われている. なお,「RSA 暗号」は巨大な整数の素因数分解の難しさを通信の安全性の根拠にしているため, $p,$ $q$ には数百桁の素数が用いられている.