まず, $[1],$ $[2]$ を満たす $q,$ $r$ の存在を示す. すべての整数は の形の無限個の範囲に分けられる. よって, \[ 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$ 個の整数 $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$ 乗数でない.

(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$ をもつから, 素数でない. ゆえに, 対偶は真であるから, 示すべき命題も真である.

(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$ の倍数である.

(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$ 個の「三角数」の和として表される.

(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) が成り立つ.

(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$ は互いに素である.

(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$ で割った余りが $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$ は合成数である.