有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

整数の剰余

整数の剰余

定理≪整数に関する除法の定理≫

 すべての整数 $a$ と正の整数 $b$ に対して, \[ a = bq+r\ \cdots [1], \quad 0 \leqq r < b\ \cdots [2]\] なる整数 $q,$ $r$ がただ $1$ 組存在する.

証明

 まず, $[1],$ $[2]$ を満たす $q,$ $r$ の存在を示す. すべての整数は
$bn \leqq x < b(n+1)$ ($n$: 整数)
の形の無限個の範囲に分けられる. よって, \[ bq \leqq a < b(q+1)\] なる整数 $q$ が存在する. このとき, \[ 0 \leqq a-bq < b\] となるから, 整数 $r$ を \[ r = a-bq\] により定めると, $q,$ $r$ は $[1],$ $[2]$ を満たす.
 次に, $q,$ $r$ の一意性を示す. 上記の $q,$ $r$ に加えて, \[ a = bq'+r'\ \cdots [1]', \quad 0 \leqq r' < b\ \cdots [2]'\] なる整数 $q',$ $r'$ の存在を仮定する. $[1],$ $[1]'$ の辺々を引くと, \[ r-r' = b(q'-q)\] が得られる. よって, $r-r'$ は $b$ の倍数である. 一方, $[2],$ $[2]'$ から \[ -b < r-r' < b\] が成り立つので, $r-r' = 0$ つまり $r = r'$ である.
これと $bq+r = bq'+r'$ から $bq = bq' = 0$ つまり $b(q-q') = 0$ であるので, $q-q' = 0$ つまり $q = q'$ である.
以上から, $q,$ $r$ の一意性が示された.

存在の別証明:「全段仮定」の帰納法を利用

(I)
$a \geqq 0$ の場合. $a$ に関する数学的帰納法で示す.
(i)
$a = 0$ のとき. $q = r = 0$ に対して $[1],$ $[2]$ が成り立つ.
(ii)
$a > 0$ のとき. $a$ 未満のすべての非負整数に対して $q,$ $r$ の存在を仮定する.
  • $a < b$ のとき. $q = 0,$ $r = a$ に対して $[1],$ $[2]$ が成り立つ.
  • $a \geqq b$ のとき. $0 \leqq a-b < a$ であるので, 帰納法の仮定から \[ a-b = bq_1+r_1, \quad 0 \leqq r_1 < b\] なる整数 $q_1,$ $r_1$ が存在する. $a = b(q_1+1)+r_1$ から, $q = q_1+1,$ $r = r_1$ に対して $[1],$ $[2]$ が成り立つ.
(i), (ii) から, $a \geqq 0$ のとき $q,$ $r$ の存在が示された.
(II)
$a < 0$ の場合. $-a > 0$ と (I) から, \[ -a = bq_2+r_2, \quad 0 \leqq r_2 < b\] なる整数 $q_2,$ $r_2$ が存在する.
  • $r_2 = 0$ のとき. $q = -q_2,$ $r = 0$ に対して $[1],$ $[2]$ が成り立つ.
  • $r_2 > 0$ のとき. \[ a = b(-q_2-1)+(b-r_2), \quad 0 \leqq b-r_2 < b\] から, $q = -q_2-1,$ $r = b-r_2$ に対して $[1],$ $[2]$ が成り立つ.
(I), (II) から, すべての場合に $q,$ $r$ の存在が示された.

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

 $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^{p-1}(p-1)! \equiv (p-1)!\ (\text{mod}\ p)\] となる. $(p-1)!$ は $p$ と互いに素なので, (2) から, $a^{p-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$ の素因数分解が $n = p_1{}^{e_1}\cdots p_r{}^{e^r}$ のとき, \[\varphi (n) = n\left( 1-\frac{1}{p_1}\right)\cdots\left( 1-\frac{1}{p_r}\right) \] であることが知られている.
  • 上記の整数 $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$ には数百桁の素数が用いられている.
  • 素数を法とする合同式についても剰余の定理(等式を合同式に置き換えた定理)が知られており, それを用いると「フェルマーの小定理」から「ウィルソンの定理」(Wilson's theorem)
    $p$ が素数 $\Longrightarrow$ $(p-1)! \equiv -1 \pmod p \quad \cdots [\ast ]$
    を導くことができる. 実際, 多項式 $f(x) = x^{p-1}-1$ について, $0 < k < p$ なる各整数 $k$ に対し $f(k) \equiv 0 \pmod p$ であるから, 剰余の定理により \[ f(x) \equiv (x-1)\cdots\{ x-(p-1)\} \pmod p\] が成り立つ. これに $x = 0$ を代入すると, \[ -1 \equiv (-1)^{p-1}(p-1)! \pmod p\] が得られる. $p \geqq 3$ のとき, $p$ は奇数だから, $(-1)^{p-1} = 1$ より $[\ast ]$ が成り立つ.
    $p = 2$ のときは, $(2-1)! = 1 \equiv -1 \pmod 2$ より, $[\ast ]$ が成り立つ.

問題≪フェルマーの小定理とシェルピンスキー数≫

 すべての正の整数 $n$ に対して $a_n = 78557\cdot 2^n+1$ は合成数であることを,
(A) $n \equiv 0$$\pmod 2$ $\Longrightarrow$ $a_n \equiv 0 \pmod 3$
(B) $n \equiv 1$$\pmod 4$ $\Longrightarrow$ $a_n \equiv 0 \pmod 5$
(C) $n \equiv 3$$\pmod{36}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{73}$
(D) $n \equiv 15$$\pmod{36}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{19}$
(E) $n \equiv 27$$\pmod{36}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{37}$
(F) $n \equiv 7$$\pmod{12}$ $\Longrightarrow$ $a_n \equiv 0 \pmod 7$
(G) $n \equiv 11$$\pmod{12}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{13}$
を示すことによって証明せよ. 「フェルマーの小定理」
$a^{p-1} \equiv 1 \pmod p$ ($p$: 素数, $a$: $p$ と互いに素な整数)
と, $2^9 \equiv 1 \pmod{73}$ は証明なしに用いてよい.

解答例

 整数は, 偶数と奇数に分けられる. 奇数は, $4$ で割った余りが $1,$ $3$ である整数に分けられる. $4$ で割った余りが $3$ である整数は, $12$ で割った余りが $3,$ $7,$ $11$ である整数に分けられる. $12$ で割った余りが $3$ である整数は, $36$ で割った余りが $3,$ $15,$ $27$ である整数に分けられる. よって, (A)~(G) を示せば, すべての正の整数 $n$ に対して $a_n$ が合成数であることが示される.
(A)
$n \equiv 0 \pmod 2$ のとき, $n = 2q$ とおくと, $2^2 \equiv 1 \pmod 3$ であるから, \begin{align*} a_n &= 78557\cdot 2^{2q}+1 \\ &\equiv 2\cdot 1^q+1 = 3 \equiv 0 \pmod 3 \end{align*} が成り立つ.
(B)
$n \equiv 1 \pmod 4$ のとき, $n = 4q+1$ とおくと, $2^4 \equiv 1 \pmod 5$ であるから, \begin{align*} a_n &= 78557\cdot 2^{4q}\cdot 2+1 \\ &\equiv 2\cdot 1^q\cdot 2+1 = 5 \equiv 0 \pmod 5 \end{align*} が成り立つ.
(C)
$n \equiv 3 \pmod{36}$ のとき, $n = 36q+3$ とおくと, $2^9 \equiv 1 \pmod{73}$ であるから, \begin{align*} a_n &= 78557\cdot 2^{9\cdot 4q}\cdot 2^3+1 \\ &\equiv 9\cdot 1^{4q}\cdot 2^3+1 = 73 \equiv 0 \pmod{73} \end{align*} が成り立つ.
(D)
$n \equiv 15 \pmod{36}$ のとき, $n = 36q+15$ とおくと, $2^{18} \equiv 1 \pmod{19}$ であるから, \begin{align*} a_n &= 78557\cdot 2^{18\cdot 2q}\cdot 2^{15}+1 \\ &\equiv 11\cdot 1^{2q}\cdot 12+1 = 133 \equiv 0 \pmod{19} \end{align*} が成り立つ.
(E)
$n \equiv 27 \pmod{36}$ のとき, $n = 36q+27$ とおくと, $2^{36} \equiv 1 \pmod{37}$ であるから, \begin{align*} a_n &= 78557\cdot 2^{36q}\cdot 2^{27}+1 \\ &\equiv 6\cdot 1^q\cdot 6+1 = 37 \equiv 0 \pmod{37} \end{align*} が成り立つ.
(F)
$n \equiv 7 \pmod{12}$ のとき, $n = 12q+7 = 6(2q+1)+1$ とおくと, $2^6 \equiv 1 \pmod 7$ であるから, \begin{align*} a_n &= 78557\cdot 2^{6(2q+1)}\cdot 2^1+1 \\ &\equiv 3\cdot 1^{2q+1}\cdot 2+1 = 7 \equiv 0 \pmod 7 \end{align*} が成り立つ.
(G)
$n \equiv 11 \pmod{12}$ のとき, $n = 12q+11$ とおくと, $2^{12} \equiv 1 \pmod{13}$ であるから, \begin{align*} a_n &= 78557\cdot 2^{12q}\cdot 2^{11}+1 \\ &\equiv 11\cdot 1^q\cdot 7+1 = 78 \equiv 0 \pmod{13} \end{align*} が成り立つ.
 以上により, すべての正の整数 $n$ に対して $a_n$ は合成数である.

背景

 シェルピンスキーは, $k\cdot 2^n+1$ ($n$: 正の整数)すべて合成数になるような正の奇数 $k$ が無限に存在することを証明した($1960$ 年). このような整数 $k$ を「シェルピンスキー数」と呼ぶ. $78557$ がシェルピンスキー数であることは, セルフリッジによって発見された. $78557$ は最小のシェルピンスキー数であると考えられている.