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

Well-Known Problems and Theorems in Mathematics

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

整数の剰余

整数の剰余

定理《整数に関する除法の定理》

 すべての整数 $a$ と正の整数 $b$ に対して, \[ a = bq+r \quad \cdots [1], \quad 0 \leqq r < b \quad \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' \quad \cdots [1]', \quad 0 \leqq r' < b \quad \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$ の存在が示された.

問題《連続する $n$ 個の正の整数の積》

 $n$ を $2$ 以上の整数とする. 連続する $n$ 個の正の整数の積は $n$ 乗数でないことを示せ. ただし, ある整数の $n$ 乗の形に表される整数を $n$ 乗数と呼ぶ.
(参考: $2012$ 東京大)
標準定理$2022/06/25$$2022/06/25$

解答例

 連続する $n$ 個の整数 $a,$ $a+1,$ $\cdots,$ $a+n-1$ の積が正の整数 $b$ を用いて \[ a(a-1)\cdots (a+n-1) = b^n \quad \cdots [1]\] と表されるとして, 矛盾を導く. このとき, \[ a^n < a(a-1)\cdots (a+n-1) < (a+n-1)^n\] から \[\begin{aligned} a^n &< b^n < (a+n-1)^n \\ a &< b < a+n-1 \end{aligned}\] が成り立つので, $b$ は \[ b = a+k \quad (1 \leqq k \leqq n-2)\] と表される. $[1]$ の両辺を $a+k = b$ で割ると \[ a(a-1)\cdots (a+k-1)(a+k+1)\cdots (a+n-1) = b^{n-1}\] となる. $a+k+1$ の素因数 $p$ に対して, $b^{n-1}$ は $p$ で割り切れ, よって $b = a+k$ は $p$ で割り切れる. これは $a+k,$ $a+k+1$ が互いに素であることに反する.
 ゆえに, 連続する $n$ 個の正の整数の積は $n$ 乗数でない.

問題《フィボナッチ数列の性質》

 $m,$ $n$ を非負整数とする. \[ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_n+F_{n+1}\] により定まる数列 $\{ F_n\}$ について, \[ F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1} \quad \cdots [1]\] の成り立つことが知られている (こちらを参照). 次のことを示せ.
(1)
$0 < m \leqq n$ とする. $m$ が $n$ を割り切るならば, $F_m$ は $F_n$ を割り切る.
(2)
$F_n,$ $F_{n+1}$ は互いに素である.
(3)
$2 < m \leqq n$ とする. $F_m$ が $F_n$ を割り切るならば, $m$ は $n$ を割り切る.
(4)
$n \neq 4$ とする. $F_n$ が素数ならば, $n$ は素数である.
発展定理$2019/05/06$$2022/11/08$

解答例

(1)
$m$ を固定して, 正の整数 $q$ に関する数学的帰納法で “ $F_m$ が $F_{mq}$ を割り切ること ” $\cdots [2]$ を示す.
(i)
$q = 1$ のとき. $F_m$ は $F_{m\cdot 1} = F_m$ を割り切るから, $[2]$ が成り立つ.
(ii)
$q = k$ ($k$: 正の整数) のとき $[2]$ が成り立つとする. このとき, $d = \dfrac{F_{mk}}{F_m}$ は整数であるから, $F_m$ は \[\begin{aligned} F_{m(k+1)} &= F_{mk+(m-1)+1} \\ &= F_{mk}F_{m-1}+F_{mk+1}F_m \quad (\because [1]) \\ &= dF_mF_{m-1}+F_{mk+1}F_m \\ &= F_m(dF_{m-1}+F_{mk+1}) \end{aligned}\] を割り切り, $q = k+1$ のとき $[2]$ が成り立つ.
(i), (ii) から, すべての正の整数 $m,$ $q$ に対して $[2]$ が成り立つ. ゆえに, $m$ が $n$ を割り切るならば, $F_m$ は $F_n$ を割り切る.
(2)
$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}$ は互いに素である.
(3)
$n$ を $m$ で割った商を $q,$ 余りを $r$ とおく. このとき, $n = mq+r,$ $0 \leqq r < m$ であり, $[1]$ により \[ F_n = F_{(mq-1)+r+1} = F_{mq-1}F_r+F_{mq}F_{r+1}\] が成り立つ. (1) により, $F_m$ は $F_{mq}$ を割り切る. また, (2) により $F_{mq-1},$ $F_{mq}$ は互いに素であるから, $F_{mq-1},$ $F_m$ は互いに素である. よって, $F_m$ が $F_n$ を割り切るとき, $F_m$ は $F_r$ を割り切る. このとき, $m > 2,$ $r < m$ と $\{ F_n\}$ が単調増加であることから $F_r < F_m$ あることに注意すると, $F_r = 0$ とならざるを得ず, $r = 0$ となるので, $m$ は $n$ を割り切る.
(4)
$n$ が素数でないならば $F_n$ は素数でないことを示す. $F_0 = 0,$ $F_1 = 1$ は素数でない. そこで, $n$ を $0,$ $1,$ $4$ でも素数でもない非負整数とする. このとき, $n$ は $2 < m < n$ なる約数 $m$ をもつ. (1) で示したことから, $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}\] から導かれる.
  • (1), (3) と $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$ の倍数
    の成り立つことがわかる.
  • $L_1 = 1,$ $L_2 = 3,$ $L_{n+2} = L_n+L_{n+1}$ で定まる「リュカ数列」(Lucas sequence) $\{ L_n\}$ については, $n$ が $m$ の奇数倍であるときに限って $L_m$ が $L_n$ を割り切ることが知られている.

問題《ピタゴラスの $3$ つ組の性質: 媒介変数表示》

 $m,$ $n$ を $m > n$ なる正の整数とする. 次のことを示せ.
(A)
$m^2-n^2,$ $2mn$ の少なくとも一方は $3$ の倍数である.
(B)
$m^2-n^2,$ $2mn,$ $m^2+n^2$ の少なくとも $1$ つは $5$ の倍数である.
標準定理$2022/07/07$$2022/07/08$

解答例

(A)
$2mn$ が $3$ の倍数でないならば $m^2-n^2$ が $3$ の倍数であることを示せばよい. $3$ の倍数でない整数は $3d\pm 1$ ($d$: 整数) の形に表され, その $2$ 乗 \[ (3d\pm 1)^2 = 3(3d^2\pm 2d)+1\] を $3$ で割った余りは $1$ である. $2mn$ が $3$ の倍数でないとき, $m,$ $n$ は $3$ の倍数でなく, $m^2,$ $n^2$ を $3$ で割った余りはいずれも $1$ であるから, $m^2-n^2$ は $3$ の倍数である.
(B)
$m^2-n^2,$ $2mn$ が $5$ の倍数でないならば $m^2+n^2$ が $5$ の倍数であることを示せばよい. $5$ の倍数でない整数は $5d\pm 1$ または $5d\pm 2$ ($d$: 整数) の形に表され, その $2$ 乗 \[\begin{aligned} (5d\pm 1)^2 &= 5(5d^2\pm 2d)+1, \\ (5d\pm 2)^2 &= 5(5d^2\pm 4d)+4 \end{aligned}\] を $5$ で割った余りは $1,$ $4$ である. $m^2-n^2,$ $2mn$ が $5$ の倍数でないとき, $m,$ $n$ は $5$ の倍数でなく, $m^2,$ $n^2$ を $5$ で割った余りは相異なる値 $1,$ $4$ (順不同) をとるから, $m^2+n^2$ を $5$ で割った余りは $0,$ つまり $m^2+n^2$ は $5$ の倍数である.

参考

  • $a^2+b^2 = c^2$ の正の整数解 $(a,b,c)$ を「ピタゴラスの $3$ つ組」(Pythagorean triple) または「ピタゴラス数」と呼ぶ. すべての「ピタゴラスの $3$ つ組」$(a,b,c)$ は, 必要に応じて $a,$ $b$ を入れ替えると, 正の整数 $k,$ $m,$ $n$ ($m,$ $n$ は偶奇が異なり, 互いに素, $m > n$) を用いて \[ a = k(m^2-n^2), \quad b = 2kmn, \quad c = k(m^2+n^2)\] と表されることが知られている (こちらを参照). 本問で示したのは, $a,$ $b$ の少なくとも一方が $3$ の倍数であること, $a,$ $b,$ $c$ の少なくとも $1$ つが $5$ の倍数であることである.
  • この性質は, 方程式 $a^2+b^2 = c^2$ から直接的に示すこともできる (こちらを参照).

問題《$3$ 個の平方数の和として表される整数》

(1)
整数 $A$ に対して, $A^2$ を $8$ で割った余りは $0,$ $1$ または $4$ であることを示せ.
(2)
$N = 4^m(8n+7)$ ($m,$ $n$: 非負整数) の形の整数 $N$ は高々 $3$ 個の平方数の和として表されないことを示せ.
(3)
(2) の逆が成り立ち, 特に $N = 8n+3$ ($n$: 非負整数) の形の整数は高々 $3$ 個の平方数の和として表されることが知られている. この定理を用いて, すべての正の整数 $n$ は高々 $3$ 個の「三角数」の和として表されることを示せ. ただし, $1+\cdots +a = \dfrac{a(a+1)}{2}$ ($a$: 正の整数) の形の整数を「三角数」と呼ぶ.
実戦定理$2023/01/18$$2023/10/23$

解答例

(1)
(i)
$A = 4d$ ($d$: 整数) のとき. \[ A^2 = 16d^2 = 8\cdot 2d^2\] を $8$ で割った余りは $0$ である.
(ii)
$A = 4d\pm 1$ ($d$: 整数) のとき. \[ A^2 = 16d^2\pm 8d+1 = 8(2d^2\pm d)+1\] を $8$ で割った余りは $1$ である.
(iii)
$A = 4d+2$ ($d$: 整数) のとき. \[ A^2 = 16d^2+16d+4 = 8(2d^2+2d)+4\] を $8$ で割った余りは $4$ である.
ゆえに, $A^2$ を $8$ で割った余りは $0,$ $1$ または $4$ である.
(2)
$m$ に関する数学的帰納法で示す.
(i)
$m = 0$ のとき. 平方数を $8$ で割った余りは $0,$ $1$ または $4$ であり, \[\begin{aligned} 0+0+0 &= 0,\\ 0+0+1 &= 1, \\ 0+0+4 &= 4, \\ 0+1+1 &= 2, \\ 0+1+4 &= 5, \\ 0+4+4 &= 8, \\ 1+1+1 &= 3, \\ 1+1+4 &= 6, \\ 1+4+4 &= 9, \\ 4+4+4 &= 12 \end{aligned}\] であるから, $3$ 個の平方数の和を $8$ で割った余りは $7$ でない. よって, $N = 8n+7$ は $3$ 個の平方数の和として表されない.
(ii)
$m = k$ ($k$: 非負整数) のとき主張が成り立つとする.
 仮に 整数 $N = 4^{k+1}(8n+7)$ ($n$: 非負整数) が
$N = A^2+B^2+C^2$ ($A,$ $B,$ $C$: 非負整数)
の形に表されるとする.
  • $A,$ $B,$ $C$ のうち, $3$ 個が奇数であるとき, または $2$ 個が偶数で $1$ 個が奇数であるとき, $N$ は奇数になってしまう.
  • $A,$ $B,$ $C$ のうち, $1$ 個が偶数で $2$ 個が奇数であるとき, $N$ を $4$ で割った余りは $2\,(\neq 3)$ になってしまう.
よって, $A,$ $B,$ $C$ はすべて偶数であるから,
$A = 2a, \quad B = 2b,\quad C = 2c$ ($a,$ $b,$ $c$: 非負整数)
とおける. このとき, \[ N = (2a)^2+(2b)^2+(2c)^2 = 4(a^2+b^2+c^2)\] は $4$ の倍数であり, \[\frac{N}{4} = 4^k(8n+7) = a^2+b^2+c^2\] は高々 $3$ 個の平方数の和である. これは $m = k$ のとき主張が成り立つことに反する.
 したがって, $N = 4^{k+1}(8n+7)$ は $3$ 個の平方数の和として表されない.
(i), (ii) から, $N = 4^m(8n+7)$ ($m,$ $n$: 非負整数) の形の整数 $N$ は高々 $3$ 個の平方数の和として表されない.
(3)
$n$ を正の整数とする. 定理により, $8n+3$ は
$8n+3 = A^2+B^2+C^2$ ($A,$ $B,$ $C$: 非負整数)
の形に表される.
  • $A,$ $B,$ $C$ のうち, $1$ 個が偶数で $2$ 個が奇数であるとき, または $3$ 個が偶数であるとき, 右辺は偶数になってしまう.
  • $A,$ $B,$ $C$ のうち, $2$ 個が偶数で $1$ 個が奇数であるとき, 右辺を $4$ で割った余りは $1\,(\neq 3)$ になってしまう.
よって, $A,$ $B,$ $C$ はすべて奇数であるから,
$A = 2a+1,\ B = 2b+1,\ C = 2c+1$ ($a,$ $b,$ $c$: 非負整数)
とおける. このとき, \[\begin{aligned} 8n+3 &= (2a+1)^2+(2b+1)^2+(2c+1)^2 \\ &= (4a^2+4a+1)+(4b^2+4b+1)+(4c^2+4c+1) \\ 8n &= 4a(a+1)+4b(b+1)+4c(c+1) \\ n &= \frac{a(a+1)}{2}+\frac{b(b+1)}{2}+\frac{c(c+1)}{2} \end{aligned}\] が成り立つから, $n$ は高々 $3$ 個の「三角数」の和として表される.

参考

  • $2$ 個の平方数の和として表される整数については, こちらを参照.
  • 正の整数 $N$ が高々 $3$ 個の平方数の和として表されるためには, $N = 4^m(8n+7)$ ($m,$ $n$: 非負整数) の形に表されないことが, 必要十分である (必要性は (2) の対偶, 十分性の証明は難しい).
  • すべての正の整数は高々 $4$ 個の平方数の和として表されることが,「ラグランジュの $4$ 平方和定理」(Lagrange's four-square theorem) として知られている.
  • すべての正の整数が高々 $3$ 個の「三角数」の和として表されることは, ガウスにより証明された.
  • 一般に, $3$ 以上の整数 $p$ に対して, $1$ を初項とする公差 $p-2$ の等差数列において, 初項からある項までの和を「$p$ 角数」と呼ぶ (こちらを参照). すべての正の整数は高々 $p$ 個の「$p$ 角数」の和として表されることが,「多角数定理」(polygonal number theorem) として知られている. さらに, $p \geqq 5$ のとき, 十分大きな正の整数は高々 $4$ 個の $p$ 角数の和として表されることも知られている.

合同式

定義《合同式》

 $m$ を整数とする. 整数 $a,$ $b$ について, $a-b$ が $m$ の倍数であるとき, $a,$ $b$ は $m$ を法として合同 (congruent modulo $m$) であるといい, \[ a \equiv b \pmod m\] と表す. このような関係を合同関係と呼び, このような数式を合同式と呼ぶ.

注意

(1)
$m = 0$ を法とする合同関係は, 等号関係に他ならない.
(2)
$m = 1$ を法とする合同関係は, すべて真である.
(3)
整数 $m$ を法とする合同関係, $-m$ を法とする合同関係は, 互いに同値である.
 これらの理由により, 合同関係は $1$ より大きい整数 $m$ を法とする場合が本質的である. また, すべての整数 $a$ に対して,
$a \equiv 0 \pmod m$ $\iff$ $a$ は $m$ の倍数
が成り立つ.

定理《合同関係は同値関係》

 $m$ を整数とする. すべての整数 $a,$ $b,$ $c$ に対して,
(1)
$a \equiv a \pmod m$ 
(2)
$a \equiv b \pmod m$ $\Longrightarrow$ $b \equiv a \pmod m$
(3)
$a \equiv b,$ $b \equiv c \pmod m$ $\Longrightarrow$ $a \equiv c \pmod m$
が成り立つ.

証明

(1)
$a-a = 0 = m\cdot 0$ は $m$ の倍数であるから, (1) が成り立つ.
(2)
$a-b$ が $m$ の倍数であるならば $-(a-b) = b-a$ は $m$ の倍数であるから, (2) が成り立つ.
(3)
$a-b,$ $b-c$ が $m$ の倍数であるならば $(a-b)+(b-c) = a-c$ は $m$ の倍数であるから, (3) が成り立つ.

注意

 (3) のとき, $a \equiv b \equiv c \pmod m$ と書く. $1$ つの等式の中で $=$ と $\equiv \pmod m$ を併用してもよい.

定理《合同式の性質》

 $m,$ $a,$ $b,$ $a',$ $b',$ $c$ を整数, $n$ を正の整数とする.
(1)
$a \equiv a' \pmod m,$ $b \equiv b' \pmod m$ ならば \[\begin{aligned} a+b &\equiv a'+b' \pmod m \quad \cdots [1], \\ a-b &\equiv a'-b' \pmod m \quad \cdots [2], \\ ab &\equiv a'b' \pmod m \quad \cdots [3], \\ ca &\equiv ca' \pmod m \quad \cdots [4], \\ a^n &\equiv a'^n \pmod m \quad \cdots [5] \end{aligned}\] が成り立つ.
(2)
$a,$ $m$ が互いに素であるならば, \[ ax \equiv 1 \pmod m.\] を満たす $m$ と互いに素な整数 $x$ が存在する.

証明

(1)
$a-a',$ $b-b'$ が $m$ の倍数であるとすると \[\begin{aligned} (a-a')+(b-b') &= (a+b)-(a'+b'), \\ (a-a')-(b-b') &= (a-b)-(a'-b'), \\ (a-a')b+a'(b-b') &= ab-a'b' \end{aligned}\] も $m$ の倍数となるから, $[1]$~$[3]$ が成り立つ. $[4],$ $[5]$ は $[3]$ から従う.
(2)
$a,$ $m$ は互いに素であるから, $m \neq 0$ である. $ax \equiv 1 \pmod m \iff ax \equiv 1 \pmod{-m}$ であるから, $m > 0$ の場合を示せばよい. $m = 1$ のとき, すべての整数 $x$ に対して $ax \equiv 1 \pmod m$ が成り立つ. 以下, $m > 1$ の場合を考える. 整数 $b,$ $b'$ が \[\begin{aligned} &ab \equiv ab' \pmod m \quad \cdots [1], \\ &0 \leqq b' \leqq b \leqq m-1 \quad \cdots [2] \end{aligned}\] を満たすとき, $[1]$ から $ab-ab' = a(b-b')$ は $m$ の倍数とるが, $a$ が $m$ と互いに素であるという仮定から $b-b'$ が $m$ の倍数となり, $[2]$ から $b-b' = 0$ つまり $b = b'$ となる. よって, 集合 $\{ ab|0 \leqq b \leqq m-1\}$ の要素は $m$ を法として互いに合同でない. したがって, この集合の要素を $m$ で割った余りは $0$ から $m-1$ までのすべての値をとる. 特に, $0$ 以上 $m-1$ 以下のある整数 $x$ に対して $ax$ を $m$ で割った余りが $1$ となり, $ax \equiv 1 \pmod m$ となる. $x,$ $m$ の最大公約数を $g$ とおき, $q = \dfrac{ax-1}{m}$ とおくと, \[ 1 = ax-mq = g\left( a\frac{x}{g}-\frac{m}{g}q\right)\] となるから, $g = 1$ である. よって, $x,$ $m$ は互いに素である.

問題《フェルマーの小定理と RSA 暗号系の原理》

 $a,$ $b,$ $a',$ $b',$ $c,$ $n$ $(n > 1)$ を整数とし, $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)$ が成り立つ.
(参考: $2020$ 静岡大, 東京農業大)
実戦定理$2016/06/29$$2024/03/23$

解答例

(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$ が互いに素であることに注意すると,
$ac \equiv a'c\ (\text{mod}\ p)$$\iff$ $ac-a'c$ は $p$ の倍数
$\iff$ $(a-a')c$ は $p$ の倍数
$\iff$ $a-a'$ は $p$ の倍数
$\iff$ $a \equiv a'\ (\text{mod}\ p)$
となる.
(3)
$k,$ $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\] と表せる. $a^e \equiv b\ (\text{mod}\ n)$ であるとする. このとき, \[\begin{aligned} 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{aligned}\] が成り立つ. 同様にして, $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)$ が成り立つ.

別解

(1)
$a \equiv a',$ $b \equiv b'\ (\text{mod}\ n)$ ならば, $a-a',$ $b-b'$ は $n$ の倍数であるから, \[ ab-a'b' = (a-a')b+a'(b-b')\] も $n$ の倍数であり, $ab \equiv a'b'\ (\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$ と互いに素, $1 < 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}$ は証明なしに使ってよい.
実戦定理$2020/09/05$$2024/01/04$

解答例

 整数は, 偶数と奇数に分けられる. 奇数は, $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{aligned} a_n &= 78557\cdot 2^{2q}+1 \\ &\equiv 2\cdot 1^q+1 = 3 \equiv 0 \pmod 3 \end{aligned}\] が成り立つ.
(B)
$n \equiv 1 \pmod 4$ のとき, $n = 4q+1$ とおくと, $2^4 \equiv 1 \pmod 5$ であるから, \[\begin{aligned} a_n &= 78557\cdot 2^{4q}\cdot 2+1 \\ &\equiv 2\cdot 1^q\cdot 2+1 = 5 \equiv 0 \pmod 5 \end{aligned}\] が成り立つ.
(C)
$n \equiv 3 \pmod{36}$ のとき, $n = 36q+3$ とおくと, $2^9 \equiv 1 \pmod{73}$ であるから, \[\begin{aligned} 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{aligned}\] が成り立つ.
(D)
$n \equiv 15 \pmod{36}$ のとき, $n = 36q+15$ とおくと, $2^{18} \equiv 1 \pmod{19}$ であるから, \[\begin{aligned} 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{aligned}\] が成り立つ.
(E)
$n \equiv 27 \pmod{36}$ のとき, $n = 36q+27$ とおくと, $2^{36} \equiv 1 \pmod{37}$ であるから, \[\begin{aligned} a_n &= 78557\cdot 2^{36q}\cdot 2^{27}+1 \\ &\equiv 6\cdot 1^q\cdot 6+1 = 37 \equiv 0 \pmod{37} \end{aligned}\] が成り立つ.
(F)
$n \equiv 7 \pmod{12}$ のとき, $n = 12q+7 = 6(2q+1)+1$ とおくと, $2^6 \equiv 1 \pmod 7$ であるから, \[\begin{aligned} 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{aligned}\] が成り立つ.
(G)
$n \equiv 11 \pmod{12}$ のとき, $n = 12q+11$ とおくと, $2^{12} \equiv 1 \pmod{13}$ であるから, \[\begin{aligned} a_n &= 78557\cdot 2^{12q}\cdot 2^{11}+1 \\ &\equiv 11\cdot 1^q\cdot 7+1 = 78 \equiv 0 \pmod{13} \end{aligned}\] が成り立つ.
 以上により, すべての正の整数 $n$ に対して $a_n$ は合成数である.

参考

 シェルピンスキーは, $k\cdot 2^n+1$ ($n$: 正の整数) がすべて合成数になるような正の奇数 $k$ が無限に存在することを証明した ($1960$ 年). このような整数 $k$ を「シェルピンスキー数」と呼ぶ. $78557$ がシェルピンスキー数であることは, セルフリッジによって発見された. $78557$ は最小のシェルピンスキー数であると考えられている.
問題一覧 (整数の性質)整数の剰余 $1$ 次不定方程式 素数
ユークリッドの互除法 いろいろな不定方程式
不等式の整数解 記数法 整数の他の問題