次: 入試問題解答 上: 解答 前: 解答

演習問題解答

解答 1 (問題1)  

(1)

$n(n+1)(n+2)(n+3)$ は4連続数だから， この4個の整数の中には2の倍数が2個あり， そのうち一方は4の倍数．また3の倍数が少なくとも1個ある． ゆえにこれは24の倍数である．

(2)

$n$ が奇数なので， $n=2k-1$ とおく．

$$n^3-n=(n-1)n(n+1)=(2k-2)(2k-1)(2k)=4(k-1)k(2k-1)$$

まず3連続数なので3の倍数がある．次に $(k-1)k$ は2連続数なので偶数． ゆえに $4(k-1)k$ は8の倍数．あわせて24の倍数であることが示せた．

(3)

$n^2-1=(n-1)(n+1)$である．$n-1,\ n,\ n+1$ のなかには3の倍数があるが， $n$ が3で割り切れないので， $n-1,\ n+1$ のいずれかは3の倍数である． また(2)と同様に $n-1,\ n+1$ のいずれかは4の倍数で他方も2の倍数である． ゆえに$n^2-1$ は24の倍数である．

(4)

$$n(n+1)(2n+1)=n(n+1)\{(n-1)+(n+2)\}=(n-1)n(n+1)+n(n+1)(n+2)$$

和の各項がともに3連続数で6の倍数なので $n(n+1)(2n+1)$ は6の倍数である．

(5)

$$\begin{eqnarray*} n^3-3n^2+8n&=&2(n^3-3n^2+2n)-(n^3-3n^2-4n)\\ &=&2(n-2)(n-1)n-n(n-4)(n+1)\\ &=&2(n-2)(n-1)n-n(n-1)(n+1)+3n(n+1)\\ \end{eqnarray*}$$

和の各項が6の倍数なので， $n^3-3n^2+8n$ は6の倍数である．

解答 2 (問題2)  

(1)

解法1

$$(7a+2b,\ 3a+b)=(2(3a+b)+a,\ 3a+b)=(a,\ 3a+b)=(a,\ b)=1$$

ゆえに分数 $\dfrac{7a+2b}{3a+b}$ は既約分数である．
解2

$$7a+2b=M,\ 3a+b=N$$

とおくと逆に解けて

$$a=M-2N,\ b=-3M+7N$$

したがって $M$ と $N$ の最大公約数を $d$ とすれば $a$ も $b$ も $d$ で割れる． $a,\ b$ は互いに素なので $d=1$ ． つまり分数 $\dfrac{7a+2b}{3a+b}$ は既約分数である．

(2)

$$pa+qb=M,\ ra+sb=N$$

とおくと逆に解けて

$$a=sM-qN,\ b=-rM+pN$$

したがって $M$ と $N$ の最大公約数を $d$ とすれば $a$ も $b$ も $d$ で割れる． $a,\ b$は互いに素なので $d=1$ ．つまり分数 $\dfrac{pa+qb}{ra+sb}$は既約分数である．

(3)

$$\begin{eqnarray*} &&11n-42=3(3n-13)+2n-3\\ &&3n-13=2n-3+n-10\\ &&2n-3=2(n-10)+17 \end{eqnarray*}$$

より

$$(11n-42,\ 3n-13)=(3n-13,\ 2n-3)=(2n-3,\ n-10)=(n-10,\ 17)$$

よって分子分母に1より大きい公約数があればそれは17である． その条件は$n-10$が17の倍数になることである．$n=17k+10$より ゆえに $n=10,\ 27,\ 44$ ．

解答 3 (問題3)  

(1)

$$\begin{eqnarray*} &&25x+13y+15z=1\\ &\iff&(13+12)x+13y+(13+2)z=1\\ &\iff... ... y=-8+5s-15t,\ z=7-6s+13t\\ &&\ (s,\ t,\ は任意の整数) \end{eqnarray*}$$

(2)

$$\begin{eqnarray*} &&2x+6y+5z+7w=1\\ &\iff& 2x+(2\cdot3+0)y+(2\cdot2+1)z+(2\... ... y=s,\ z=u,\ w=1-2t-u\\ &&\ (s,\ t,\ u,\ は任意の整数) \end{eqnarray*}$$

解答 4 (問題4)  

(1)

$d$ を $a$ の任意の約数とする．さらに $s$ を $d$ の素因数とすると， $s$は$a$の約数であり，したがって $p^{\alpha},\ q^{\beta},\ r^{\gamma},\ \cdots$ のいずれかの約数である． $s$ が素数であるから $p,\ q,\ r,\ \cdots$のいずれかと 一致する．よって

$$d=p^xq^yr^z\cdots$$

と書ける．このとき $0\le x \le\alpha$ ， $0\le y \le\beta$ ， $0\le z \le\gamma,\ \cdots$ は明らか．逆にこのような数 $d$ が約数 であることは明らか．

(2)

(1)の $x,\ y,\ z,\ \cdots$ のそれぞれがとりうる値の個数は $\alpha+1,\ \beta+1,\ \gamma+1,\ \cdots$ であり，約数はこれらのすべての組合せ の個数だけある．

$$∴\quad T(a)=(1+\alpha)(1+\beta)(1+\gamma)\cdots$$

(3)

$$\begin{eqnarray*} S(a)&=&\sum_{0\le x \le \alpha ,0\le y \le \beta,0 \le z \... ...eta+1}-1}{q-1} \cdot \dfrac{r^{\gamma+1}-1}{r-1}\cdot \cdots \end{eqnarray*}$$

(4)

(2)，(3)より $T(abc)$ ， $S(abc)$ ともそれぞれ素因数全体にわたる積 であるから明らかである．

(5)

$a=dd'$ と因数分解する．この分解で $d$ を $a$ の約数全体にわたり動かすと， $d'$ も $a$ の約数全体を動く．したがってそのように動かしたものをすべて かけあわせることにより

$$a^{T(a)}=\left(\prod_{d\vert a} d \right)^2$$

$$∴\quad \prod_{d\vert a} d = a^{\frac{T(a)}{2}}$$

解答 5 (問題5)  
［前半］

$2^n-1$ が素数なら，その約数は$1$ と $2^n-1$． $2^{n-1}$ の約数は $1,\ 2,\ \cdots ,\ 2^{n-1}$．したがって $a$ の約数は

$$1,\ 2,\ \cdots ,\ 2^{n-1},\ 2^n-1,\ 2(2^n-1),\ \cdots ,\ 2^{n-1}(2^n-1)$$

これらの和は

$$\begin{eqnarray*} &&1+2+\cdots+ 2^{n-1}+(2^n-1)+2(2^n-1)+\cdots+2^{n-1}(2^n-1)... ...frac{2^n-1}{2-1}+(2^n-1)\frac{2^n-1}{2-1}\\ &=&2^n(2^n-1)=2a \end{eqnarray*}$$

したがって真の約数の和はここから $a$ を引いて $a$ に等しい．
［後半］（オイラーの解法）

$a$ を偶数の完全数とする． $a=2^{n-1}b,\ n>1,\ (2,\ b)=1$とおける． $a$ は完全数なので$S(a)=2a$である．一方練習問題1-(4)から

$$S(a)=S(2^{n-1})S(b)=(2^n-1)S(b)$$

したがって

$$S(b)=\dfrac{2\cdot2^{n-1}b}{2^n-1}=b+\dfrac{b}{2^n-1}$$

ゆえに $\dfrac{b}{2^n-1}$ は整数である． $n>1$ より$2^n-1$は $b$ よりも小さい $b$ の約数である． つまり $b$ のすべての約数の和 $S(b)$ が $b$ の二つの異なる約数の和になる． したがって $b$ は二つの約数しかもたない．つまり$b$ は素数で， $\dfrac{b}{2^n-1}=1$ である． よってまた $2^n-1$ は素数である．

解答 6 (問題6)  

(1)

$aa'a''\cdots とbb'b''\cdots$ が互いに素でないとしてその最大公約数を $d$ とする．

$d$ の素因数 $p$ をとる． $p$ は $aa'a''\cdots とbb'b''\cdots$ の公約数である． したがって $p$ は $a,\ a',\ a'',\ \cdots$ のいずれか， $b,\ b',\ b'',\ \cdots$ のいずれかの約数である．

これは $a,\ a',\ a'',\ \cdots$ がおのおの $b,\ b',\ b'',\ \cdots$ と 互いに素であることと矛盾する．

(2)

$$\begin{eqnarray*} d_1&=&(a_1,\ a_2,\ \cdots,\ a_m)\\ d_2&=&(b_1,\ b_2,\ \cd... ...d_3&=&(a_1b_1,\ a_1b_2,\ \cdots,\ a_2b_1,\ \cdots,\ a_mb_n,\ ) \end{eqnarray*}$$

とする．

$d_1d_2$ は $a_ib_j$ のすべての約数なので $d_1d_2$ は $d_3$ の約数．

一方，$d_1$ も $d_3$ の約数なので $d_3=d_1e$ とおく． $d_3$ は

$$a_1b_1,\ a_2b_1,\ \cdots,\ a_mb_1$$

の約数で $d_1=(a_1,\ a_2,\ \cdots,\ a_m)$ なので， $e$ は $b_1$ の約数． 各 $b_i$ について言えるので $e$ は $b_1,\ b_2,\ \cdots,\ b_n$ の公約数． つまり $e$ は $d_2$ の約数．

ゆえに$d_3=d_1e$は $d_1d_2$ の約数．

$$∴\quad d_1d_2=d_3$$

(3)

$a_1,\ a_2,\ \cdots ,\ a_n$ の任意の公約数に現れる素因数は $p,\ q,\ \cdots$以外にはない．ゆえに公約数は

$$\prod_pp^{\beta(p)}\ (\beta(p) \ge 0)$$

とおける．ここで

$$\beta(p) \le \mathrm{Min}(\alpha_1(p),\ \alpha_2(p),\ \cdots,\ \alpha_n(p))$$

となり，最大公約数のときに限り

$$\beta(p) = \mathrm{Min}(\alpha_1(p),\ \alpha_2(p),\ \cdots,\ \alpha_n(p))$$

同様に，最小公倍数はその最小性により現れる素因数は $p,\ q,\ \cdots$以外にはない． ゆえに次の数

$$\prod_pp^{\gamma(p)}\ (\gamma(p) \ge 0)$$

が公倍数なら

$$\gamma(p) \ge \mathrm{Max}(\alpha_1(p),\ \alpha_2(p),\ \cdots,\ \alpha_n(p))$$

となり，最小倍約数のときに限り

$$\gamma(p) = \mathrm{Min}(\alpha_1(p),\ \alpha_2(p),\ \cdots,\ \alpha_n(p))$$

(4)

(i)

各$p$に対し $\alpha_1,\ \alpha_2,\ \cdots,\ \alpha_n$ を並べ替えて ${\alpha_1}',\ {\alpha_2}',\ \cdots,\ {\alpha_n}'$ とおく．すると(3)より

$$d_1=\prod_pp^{{\alpha_1}'}$$

以下同様に

$$d_k=\prod_pp^{{\alpha_1}'+{\alpha_2}'+ \cdots+{\alpha_k}'}$$

したがって， $k=2,\ \cdots n$ に対して$d_k$ は $d_{k-1}$ で割りきれる．

(ii)

$$\dfrac{d_k}{d_{k-1}}=e_k=\prod_pp^{{\alpha_k}'}$$

であるから

$$\dfrac{e_k}{e_{k-1}}=\prod_pp^{{\alpha_k}'-{a_{k-1}}'}$$

(iii)

また

$$\begin{eqnarray*} e_1 e_2\cdots e_n&=&\prod_pp^{{\alpha_1}'+{\alpha_2}' + \cdots+{\alpha_n}'}\\ &=&\alpha_1 \alpha_2 \cdots \alpha_n \end{eqnarray*}$$

(iv)

$$e_n=\prod_pp^{{\alpha_n}'}$$

なので(3)から$e_n$ は $\alpha_1,\ a_2,\ \cdots,\ \alpha_n$ の 最小公倍数に等しい．

(5)

$$a_k=\prod_pp^{\alpha_k},\ m=\prod_pp^{\mu}$$

とおけば，問題の等式を素因数 $p$ に指数で見ることにより，

$$\mathrm{Max}\{\mathrm{Min}(\alpha_1,\ \mu),\ \mathrm{Min}(... ...athrm{Max}\{\alpha_1,\ \alpha_2,\ \cdots,\ \alpha_n\},\ \mu)$$

を示せばよい．

$\mu \ge \alpha_1,\ a_2,\ \cdots,\ \alpha_n$ なら左辺は $\mathrm{Max}(\alpha_1,\ a_2,\ \cdots,\ \alpha_n)$ ．右辺も同じ．

次に例えば $\alpha_1 > \mu$ とする． $\mathrm{Min}(\alpha_1,\ \mu)=\mu$で， $\mathrm{Min}(\alpha_2,\ \mu),\ \cdots,\ \mathrm{Min}(\alpha_n,\ \mu)$は $\mu$ 以下でから左辺は$\mu$．

一方 $\mathrm{Max}\{\alpha_1,\ \alpha_2,\ \cdots,\ \alpha_n\}\ge \alpha_1>\mu$ より， 右辺も$\mu$になる．

(6)

$l$ の素因数分解を

$$l=p^{\alpha}q^{\beta}\cdots$$

とする． $p^{\alpha}$ は $a,\ b,\ c,\ \cdots$ の少なくとも一つに含まれている． $p$を因子に含む $a,\ b,\ c,\ \cdots$うち， べき指数が最高のものが含まれている $a,\ b,\ c,\ \cdots$を指定する． 同じ指数のものがあるときはそのうちのいずれかをとる． $a$が指定された$a$に含まれる最高べき因子の積を$a_0$とする． $b_0,\ c_0,\ \cdots$をそれぞれ同様に定める． このとき $a_0,\ b_0,\ c_0,\ \cdots$のどの2つも互いに素で

$$l=a_0b_0c_0\cdots$$

である．

解答 7 (問題7)        前半は後半の $n=1$ の場合なので，後半を示せばよい．

$$\begin{eqnarray*} {}_{p^n} \mathrm{C}_k&=&\dfrac{p^n(p^n-1)\cdots(p^n-k+1)}{k(... ...cdots 1}\\ &=&\dfrac{p^n}{k}\cdot{}_{p^n-1} \mathrm{C}_{k-1} \end{eqnarray*}$$

つまり

$$k\cdot{}_{p^n} \mathrm{C}_k=p^n\cdot{}_{p^n-1} \mathrm{C}_{k-1}$$

ここで ${}_{p^n} \mathrm{C}_k,\ {}_{p^n-1} \mathrm{C}_{k-1}$ は組合せの場合の数なので正の整数である．

$k=p^l\cdot q\ (qはpと互いに素)$ とおくと

$$q\cdot{}_{p^n} \mathrm{C}_k=p^{n-l}\cdot{}_{p^n-1} \mathrm{C}_{k-1}$$

$qはpと互いに素$なので ${}_{p^n} \mathrm{C}_k$が $p^{n-l}$ の倍数である．

解答 8 (問題8)        $n!$ に現れる素数 $p$ の最高べきの指数を $N$ とする． $N$ は $n,\ n-1,\ \cdots,\ 1$ に含まれる素数 $p$ の個数に等しい．

$$p^l \le n <p^{l+1}$$

とする．$k\ge l+1$ なら $\left[\dfrac{n}{p^k}\right]=0$ である．

$$\begin{array}{ll} n,\ n-1,\ \cdots,\ 1 のなかでちょ... ...のの個数は &\left[\dfrac{n}{p^l}\right] \end{array}$$

$$\begin{eqnarray*} ∴\quad N&=&1\cdot \left(\left[\dfrac{n}{p}\right] -\left... ...}\right]\\ &=&\sum_{k=1}^{\infty}\left[\dfrac{n}{p^k}\right] \end{eqnarray*}$$

解答 9 (問題9)  

(i)既約分数 $\dfrac{m}{n}$ が部分分数に分解できること．

$x,\ y,\ \cdots$ に関する条件を考えなければ

$$\dfrac{m}{n}=\dfrac{x}{p^{\alpha}}+\dfrac{y}{q^{\beta}}+\cdots \pm s$$

は

$$m=\dfrac{n}{p^{\alpha}}x+\dfrac{n}{q^{\beta}}y+\cdots \pm s$$

となり，これは $x,\ y,\ \cdots$ に関する一次不定方程式で 係数は互いに素なので定理5によって解を持つ．

ここで $x$ を$p^{\alpha}$で割って

$$x=p^{\alpha}\cdot Q +r$$

となったとすれば $s$ を調整して $x$ の代わりに $r$ を用いることで条件

$$0<x<p^{\alpha}$$

にできる． $x=0$ ならその項はいらないので， $0<x$ としてよい． したがって題意を満たす部分分数分解が存在する．

(ii)部分分数分解の一意性を示す．

二つの分解

$$\begin{eqnarray*} \dfrac{m}{n}&=&\dfrac{x}{p^{\alpha}}+\dfrac{y}{q^{\beta}}+\c... ... &=&\dfrac{x'}{p^{\alpha}}+\dfrac{y'}{q^{\beta}}+\cdots \pm s \end{eqnarray*}$$

があれば辺々引いて

$$0=\dfrac{x-x'}{p^{\alpha}}+\dfrac{y-y'}{q^{\beta}}+\cdots \pm s \mp s'$$

両辺に $n$ をかけて分母を払うと

$$0=(x-x')q^{\beta}\cdots +(y-y')p^{\alpha}\cdots+\cdots$$

となり $x-x'$ が $p^{\alpha}$ で割りきれる．しかし

$$0\le x<p^{\alpha},\ 0\le x'<p^{\alpha}$$

なので(一方に現れない項が他方に現れる可能性を考え等号が付いている），

$$\vert x-x'\vert<p^{\alpha}$$

ゆえに $x=x'$ ．同様に $y=y',\ \cdots$ ．その結果 $\pm s=\pm s'$．

解答 10 (問題10)  

$$\begin{eqnarray*} a&=&a_n10^n+a_{n-1}10^{n-1}+\cdots+a_110+a_0\\ &=& a_n(9+... ...s+a_1(9+1)+a_0\\ &\equiv& a_0+a_1+\cdots+a_n\quad (\bmod\ 9) \end{eqnarray*}$$

同様に

$$\begin{eqnarray*} a&=&a_n10^n+a_{n-1}10^{n-1}+\cdots+a_110+a_0\\ &=& a_n(11... ...)+a_0\\ &\equiv& a_0-a_1+\cdots+(-1)^{n}a_n\quad (\bmod\ 11) \end{eqnarray*}$$

解答 11 (問題11)  

$$\begin{eqnarray*} 10^6&=&(7+3)^6\\ &\equiv&3^6\quad (\bmod.\ 7)=(7+2)^3\qua... ...(7+3)^{100}\equiv 4\quad (\bmod.\ 7)．\quad ∴\quad 火曜日 \end{eqnarray*}$$

解答 12 (問題12)        ガウス の方法を用いる．

$$\begin{eqnarray*} 5\cdot 7\cdot t_1\equiv 1\quad (\bmod.\ 3)&より&t_1\equiv ... ..._3\equiv 1\quad (\bmod.\ 7)&より&t_3\equiv 1\quad (\bmod.\ 7) \end{eqnarray*}$$

ゆえに求める数は

$$\begin{eqnarray*} x&\equiv& 1\cdot (5\cdot 7)\cdot 2+ 2\cdot (3\cdot 7)\cdot 1... ....\ 3\cdot5\cdot7)\\ &\equiv& 52\quad (\bmod.\ 3\cdot5\cdot7) \end{eqnarray*}$$

解答 13 (問題13)  

(1)

$$\begin{eqnarray*} 2^{65}+1&=&32^{13}+1\\ &\equiv &(-1)^{13}+1\quad (\bmod.\ 11)\\ &=&0\quad (\bmod.\ 11) \end{eqnarray*}$$

(2)

$$\begin{eqnarray*} 13^{2n}+6&\equiv&36^n+6\quad (\bmod.\ 7)\\ &\equiv &1+6\quad (\bmod.\ 7)\equiv 0\quad (\bmod.\ 7) \end{eqnarray*}$$

(3)

$$\begin{eqnarray*} 3^{15}&=&27^5\\ &\equiv &7^5\quad (\bmod.\ 10)\equiv 7\qu... ....\ 10)\equiv -7\quad (\bmod.\ 10)\equiv 3\quad (\bmod.\ 10) \end{eqnarray*}$$

(4)

$$\begin{eqnarray*} (2^{100}-1)^{99}&=&(1024^{10}-1)^{99}\\ &\equiv &(24^{10}... ...421875\\ &\equiv &75\quad (\bmod.\ 100)\quad ∵75^3=421875 \end{eqnarray*}$$

解答 14 (問題14)  

(1)

$n=7k\pm e\ (e=0,\ 1,\ 2,\ 3)$ とおく．

$$n^2\equiv (\pm e)^2\equiv 0,\ 1,\ 2^2,\ 3^2 \equiv 0,\ 1,\ 2,\ 4\quad (\bmod.\ 7)$$

(2)

$n=10k \pm e\ (e=0,\ 1,\ 2,\ 3,\ 4,\ 5)$ とおく(5は二重になっている)．

$$\begin{eqnarray*} n^5-n&\equiv& (\pm e)^5-(\pm e)\quad (\bmod.\ 10)\\ &=&\pm e(e-1)\{(e+1)(e-2)(e+2)+5e)\}\\ &\equiv &0\quad (\bmod.\ 10) \end{eqnarray*}$$

(3)

$n=2k-1$ とおく．

$$n^2-1=(2k-1-1)(2k-1+1)=4k(k-1)\equiv 0\quad (\bmod.\ 8)$$

(4)

$$\begin{eqnarray*} n^4+2n^3+11n^2+10n&=&n(n+1)(n^2+n+10)\\ &=&n(n+1)\{(n+2)(... ...(n+1)(n+2)(n+3)-4(n-1)n(n+1)\\ &\equiv& 0\quad (\bmod.\ 24) \end{eqnarray*}$$

解答 15 (問題15)  

(1)

$a=3k+e\ (e=0,\ \pm1)$ に対して

$$a^2\equiv e^2\equiv \left\{ \begin{array}{ll} 0\qua... ...1\quad (\bmod.\ 3)&e\ne 0\ のとき \end{array} \right.$$

である．

$a^2+b^2=c^2$ となる整数 $c$ が存在するなら右辺は3を法として0か1に合同なので

$$a^2+b^2\equiv 2\quad (\bmod.\ 3)$$

となることはできない． ところが，左辺が $2\quad (\bmod.\ 3)$ になるのは $a,\ b$ とも 3の倍数でないときである．これが否定されるので題意が示された．

(2)

同様に

$$a^2\equiv \left\{ \begin{array}{ll} 0\quad (\bmod.\... ...iv 2,\ 3\quad (\bmod.\ 5)\ のとき \end{array} \right.$$

である．

ゆえに，1と4をどのように加えても5を法として1や4に合同にはならない．

つまり$a,\ b,\ c$ のうち少なくとも $1$ つは $5$ の倍数である．

解答 16 (問題16)        $a\equiv 3\quad (\bmod.\ 11)$より $a^3\equiv 5\quad (\bmod.\ 11)$である． 一方 $a^3+b\equiv 4\quad (\bmod.\ 11)$ なので，

$$b\equiv 4-5\quad (\bmod.\ 11)\equiv 10\quad (\bmod.\ 11)$$

解答 17 (問題17)        $(26,\ 57)=1$ なので解が存在する． $57=26\cdot2+5$ より

$$\begin{eqnarray*} &&26x\equiv 1\quad (\bmod.\ 57)\ \\ &\Rightarrow &52x\equ... ...えられた式と加えて\\ &&x\equiv 11\quad (\bmod.\ 57) \end{eqnarray*}$$

ゆえに解があれば 11 に 57 を法として合同である． 解が存在することは分かっているので

$$x\equiv 11\quad (\bmod.\ 57)$$

別解

$26x=1+57y$となる整数 $y$ があればよい．

$$57y\equiv -1\quad (\bmod.\ 26)\ より\ 5y\equiv 25\quad (\bmod.\ 26)． \ つまりy\equiv 5\quad (\bmod.\ 26)$$

$y=5+26t$ とおくと

$$26x=1+57(5+26t)=1+(26\cdot2+5)(5+26t) =26(11+57t)$$

$$x\equiv 11\quad (\bmod.\ 57)$$

解答 18 (問題18)  

$$\begin{eqnarray*} &&\left\{ \begin{array}{l} x\equiv a\quad (\bmod.\ m)\\ ... ...iff &&\ x=a+mu=b+nv\ となる整数 (u,\ v) が存在する． \end{eqnarray*}$$

つまり$a-b=-mu+nv$ となる整数解 $(u,\ v)$ が存在することと同値である． これは

$$a-b\equiv 0\quad (\bmod.\ d)$$

と同値である(定理5)．

二つの解 $x_1,\ x_2$ が存在したとする．このとき

$$x_1-x_2\equiv 0\quad (\bmod.\ m),\ かつ\ x_1-x_2\equiv 0\quad (\bmod.\ n)$$

つまり $x_1-x_2$ は $m$ と $n$ の最小公倍数 $l$ で割り切れる(定理2)．

解答 19 (問題19)        必要性は明らかである．よって，条件が成立しているとする．

ここで $\{m_1,\ m_2,\ \cdots,\ \}$ で $m_1,\ m_2,\ \cdots,$ の最小公倍数を表す． すると前問から

$$\left\{ \begin{array}{l} x\equiv a_1\quad (\bmod.\ m_1),\\ x\equiv a_2\quad (\bmod.\ m_1) \end{array} \right.$$

の解を

$$x\equiv b\quad (\bmod.\ \{m_1,\ m_2\})$$

のように表すことができる．これに第三の合同式を組合わせて

$$\left\{ \begin{array}{l} x\equiv b\quad (\bmod.\ \{m_1,... ...),\\ x\equiv a_3\quad (\bmod.\ m_3) \end{array} \right.$$

この解が $\{m_1,\ m_2,\ m_3\}$を法としてただ一つに定まることを示す．

仮定から $b\equiv a_1\quad (\bmod.\ m_1)$ ． ゆえに $b-a_3\equiv a_1-a_3\quad (\bmod.\ m_1)$． すなわち

$$b-a_3\equiv a_1-a_3\equiv 0\quad (\bmod.\ (m_1,\ m_3))$$

同様に

$$b-a_3\equiv a_2-a_3\equiv 0\quad (\bmod.\ (m_2,\ m_3))$$

つまり $b-a_3$ は $(m_1,\ m_3)$ かつ $(m_2,\ m_3)$ で割りきれ，したがって $\{(m_1,\ m_3),\ (m_2,\ m_3)\}$ で割りきれる．

$$\{(m_1,\ m_3),\ (m_2,\ m_3)\}=\{(m_1,\ m_2),\ m_3\}$$

であるから(練習問題6の(5))，前問により $x$ は

$$\{\{m_1,\ m_2\},\ m_3\}=\{m_1,\ m_2,\ m_3\}$$

に関してただ一つ定まる．

順次この操作を繰りかえすことにより題意が示された．

解答 20 (問題20)  

(1)

$x^2+x+1\equiv 3\quad (\bmod.\ 5)$ を解く．

$$\begin{eqnarray*} x^2+x-2=(x+2)(x-1)\equiv 0\quad (\bmod.\ 5)\ より\\ x\equiv 1,\ 3\quad (\bmod.\ 5) \end{eqnarray*}$$

これを用いて解く．

$$\begin{eqnarray*} x=1+5y&&とおく．\\ (1+5y)^2+(1+5y)-2&=&25y^2+15y\equi... ...uiv &4\quad (\bmod.\ 5)\\ ∴&&x\equiv 23\quad (\bmod.\ 25) \end{eqnarray*}$$

$$x\equiv 1,\ 23\quad (\bmod.\ 25)$$

(2)

$$\begin{eqnarray*} &&x^2\equiv 1\quad (\bmod.\ 3)\\ ∴&&x\equiv 1,\ -1\quad... ... 1\quad (\bmod.\ 13)\\ ∴&&x\equiv 1,\ -1\quad (\bmod.\ 3) \end{eqnarray*}$$

$$x^2\equiv 1\quad (\bmod.\ 39)$$

は四つの解をもつ．それらは，

$$\left. \begin{array}{l} x\equiv 1\\ x\equiv 1 \end... ...begin{array}{l} (\bmod.\ 3)\\ (\bmod.\ 13) \end{array}$$

から求められる．

$$∴\quad x\equiv 1,\ x\equiv 25,\ x\equiv 14,\ x\equiv 38\quad (\bmod.\ 39)$$

解答 21 (問題21)   $x=1+2y$を奇数とする．$x^2=1+4y(y+1)$ で $y(y+1)$ は偶数だから， $x^2\equiv 1\,(\bmod.\ 8)$．

ゆえに $\alpha\equiv 1\,(\bmod.\ 8)$は$\alpha$が奇数であるときに問題の合同式が解をもつための必要条件である．

このとき題意を $e$ に関する数学的帰納法で示す．

$e=3$ のとき．

解は

$$x\equiv 1,\ 3,\ 5,\ 7\,(\bmod.\ 8)$$

である．このいずれを$x_0$としても，この4数は

$$x\equiv \pm x_0,\ \pm x_0+2^2\,(\bmod.\ 8)$$

となっており，解の存在とその形に関して題意が成立している．

$e$ のときの成立を仮定して $e+1$ のときの成立を示す．

つまり

$$x^2\equiv \alpha\,(\bmod.\ 2^{e+1})$$ (9.1)

の解は四つあり，そのうちの一つを$x_0$とすれば4解は

$$\pm x_0,\ \pm x_0 +2^e$$

と表されることを示す．

さて，$e$ のときの解 $x_0$ を用いれば $e+1$のときの解は

$$\pm x_0+2^ey\quad または\quad (\pm x_0+2^{e-1})+2^ey\,(\bmod.\ 2^{e+1})$$ (9.2)

の形をしていなければならない． そして(9.2)が(9.1)を満たさなければならないので

$$(\pm x_0+2^ey)^2 \equiv \alpha\,(\bmod.\ 2^{e+1})$$ (9.3)

$$\{(\pm x_0+2^{e-1})+2^ey\}^2 \equiv \alpha\,(\bmod.\ 2^{e+1})$$ (9.4)

のいずれかが成立する$y$から$e+1$のときの解が求まる．

仮定から整数 $t$ を用いて $x_0^2=\alpha+2^et$ と表せる． これを用いると(9.3)は

$$2^et\equiv 0\,(\bmod.\ 2^{e+1})$$

となり，これは$t$が奇数ならつねに成立せず，$t$が偶数ならつねに成立する．

次に(9.4)について．$x_0$は奇数で$2n-2\ge n+1$ であるから

$$\begin{eqnarray*} (\pm x_0+2^{e-1})^2&\equiv &x_0^2\pm2^ex_0+2^{2e-2}\\ &\equiv &x_0^2+2^e\,(\bmod.\ 2^{e+1}) \end{eqnarray*}$$

よって(9.4)は

$$2^et+2^e\equiv 0\,(\bmod.\ 2^{e+1})$$

となる．これは$t$が偶数ならつねに成立せず，$t$が奇数ならつねに成立する．

つねに成立するとき$y$は任意なので， $\bmod.\ 2^{e+1}$に関しては$y=0,\ 1$をとることができる．

よって$t$が偶数なら

$$\pm x_0 \quad および \quad \pm x_0+2^e$$

の四つが解である．

$t$が奇数なら

$$\pm (x_0+2^{e-1}) \quad および \quad \pm (x_0+2^{e-1})+2^e$$

の四つが解である．

以上によって，数学的帰納法により題意が示された．

解答 22 (問題22)  

(1)

$1512=2^33^37$ であるから

$$\varphi(1512)=1512\left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right) \left(1-\dfrac{1}{7}\right)=432$$

実際

$$\begin{eqnarray*} &&1512-(\dfrac{1512}{2}+\dfrac{1512}{3}+\dfrac{1512}{7}) +... ...dfrac{1512}{42}\\ &=&1512-(756+504+216)+(252+108+72)-36=432 \end{eqnarray*}$$

である．

(2)

$a$ が1512と互いに素なら $1512-a$ も1512と互いに素である． したがって1512と互いに素なものを小さい順にならべると

$$1,\ 5,\ 11,\ \cdots,\ 1511$$

となる． $a$ と $1512-a$ を組にするとそれらの和は

$$\dfrac{432(1+1511)}{2}=326592$$

解答 23 (問題23)        点 $(a,\ b)$ と点 $(c,\ d)$ および原点が同一直線上にあるのは

$$\dfrac{b}{a}=\dfrac{d}{c}$$

となるときである．つまり一方の分子分母を約分して他方になるときである．

したがって，領域 $y < x$ の中にあって題意をみたす点 $(a,\ b)$ は 既約分数 $\dfrac{b}{a}\ (1\le a,\ b \le 12)$ の個数である． 分母を $n$ に対して $\dfrac{a}{n}$が既約なものは $\varphi (n)$個ある．

直線 $y=x$ 上では $(1,\ 1)$ のみが題意をみたす．

$$∴ \quad 求める個数=1+2\sum_{k=2}^{12}\varphi(k)=1+2(1+2+2+4+2+6+4+6+5+10+4)=91$$

解答 24 (問題24)        $a,\ b,\ c,\ \cdots$ と与えられた互いに素な数の個数に関する 数学的帰納法で証明する．

$a$ がただ一つ与えられたときは $1,\ 2,\ \cdots,\ [x]$ のなかで $a$ の倍数は

$$1\cdot a,\ 2\cdot a,\ \cdots,\ \left[ \dfrac{x}{a}\right]a$$

だけある．

$$∴\quad \Phi (x)=[x]-\left[ \dfrac{x}{a}\right]$$

$a_1=a,\ a_2=b,\ \cdots,\ a_k$ が与えられたときそれらのいずれでも 割り切れない数の個数を $\Phi_k (x)$ とし，これについては成立しているとする．

さらに $a_{k+1}$ が追加されたとする． このときは，さらに $a_{k+1}$ の倍数 $ya_{k+1}\ \left(y\le\dfrac{x}{a_{k+1}} \right)$ を除かなければならない．そのうち $y$ が $a_1=a,\ a_2=b,\ \cdots,\ a_k$ で割り切れるものは すでに除かれているので，新たに除くべきものは

$$\Phi_k \left(\dfrac{x}{a_{k+1}}\right)$$

個ある．

$$\begin{eqnarray*} ∴\quad \Phi_{k+1} (x)&=&\Phi_k (x)-\Phi_k \left(\dfrac{x}{... ...ght]- \cdots -\left[\dfrac{x}{a_1a_2a_{k+1}}\right]- \cdots \end{eqnarray*}$$

ゆえに $k+1$ のときも成立し，題意が示された．

解答 25 (問題25)        $(m,\ n)=1$ ならば， $d_1\vert m,\ d_2\vert n$ とすれば $(d_1,\ d_2)=1,\ d_1d_2\vert mn$ ．

逆に， $d\vert mn$ なら $d=d_1d_2,\ (d_1,\ d_2)=1$ の形に書ける．

$$\begin{eqnarray*} ∴\quad G(mn)&=&\sum_{d\vert mn}F(d)\\ &=&\sum_{d_1\vert... ...\ &=&\sum_{d_1\vert m}F(d_1)\sum_{d_2\vert m}F(d_2)=G(m)G(n) \end{eqnarray*}$$

注意 9.1.1        これを用いれば，補題2の別の証明ができる.

$\mu (n)$ は明らかに乗法的関数である． $G(n)=\sum^{d\vert n}\mu (d)$ で $G(n)$ を定めると $G(n)$も乗法的関数である． ゆえに $n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}$ のとき

$$G(n)=G({p_1}^{e_1})G({p_2}^{e_2})\cdots G({p_k}^{e_k})$$

ところが

$$G(p^e)=\sum_{d\vert p^e}\mu (d)=1+\mu (p)+\mu (p^2)+\cdots+\mu (p^e)=1+\mu (p)=0$$

ゆえに補題が示された．

解答 26 (問題26)        1から $[nx]$ までの整数のうち， $n$ との最大公約数が $d$ であるものは

$$yd,\ y=1,\ \cdots,\ \left[\dfrac{[nx]}{d} \right],\ かつ\ \ (yd,\ n)=d$$

と書ける．ところが

$$(yd,\ n)=d\ \iff \ \left(y,\ \dfrac{n}{d}\right)=1 ,\ \quad \left[\dfrac{[nx]}{d} \right]=\left[\dfrac{nx}{d} \right]$$

であるからその個数は1から $\left[\dfrac{nx}{d}\right]$ までの整数のうち， $\dfrac{n}{d}$ と互いに素であるものの個数 $\varphi\left(\dfrac{n}{d},\ \dfrac{nx}{d} \right)$ に等しい．1から $nx$ を超えない最大の整数までの整数は $d\vert n$ に関して1度ずつ 数えられるので，

$$[nx]=\sum_{d\vert n}\varphi\left(\dfrac{n}{d},\ \dfrac{nx}{d} \right)$$

$d$ が $n$ の正の約数を動けば $\dfrac{n}{d}$ の正の約数をすべて動くので第一式が示された．

第二式は第一式よりメビウスの反転公式で得られる．

解答 27 (問題27)  

$$F_n(x)=\prod_{d\vert n}(x^{ \frac{n}{d}}-1)^{\mu(d)}$$

であり, $n>1$ のとき

$$\sum_{d\vert n}\mu (d)=0$$

であるから， $F_n(x)$ の定数項は $n=1$ の場合以外 $+1$ である．

解答 28 (問題28)   $n>1$ のときすべての $n$ 乗根の和は，$x^n-1=0$ から0である． 従って原始 $n$ 乗根の和を $f(n)$ をおくと，

$$すべての n 乗根の和=\sum_{d\vert n}f(d) =\left\{ ... ...n = 1 のとき\\ 0&n > 1 のとき \end{array} \right.$$

整数 $n$ と $d$ に関する等式と見ればメビウスの反転公式(6節)から

$$f(n)=\mu(n)\cdot 1+\mu(d)\cdot 0+\cdots + \mu(1)\cdot 0=\mu(n)$$

解答 29 (問題29)        $\alpha^k$ はもちろん $n$ 乗根である．

$$\alpha^i=\alpha^j\ \iff \ \alpha^{i-j}=1$$

であるが， $\alpha$ が原始 $n$ 乗根なのでこれは

$$i-j\equiv 0\ (\bmod．\ n)$$

を意味する．従って $k$ を $n$ に関する剰余系にとった $\alpha^k\ (k=0,\ 1,\ \cdots,\ n-1)$ はすべて異なる． つまりこれらが，1の $n$ 乗根のすべてである．

つぎに

$$(\alpha^k)^i=1\ \iff \ ki\equiv 0\quad (\bmod．\ n)$$

$(k，\ n)=1$ なら， $i\equiv 0\quad (\bmod．\ n)$ が結論されるので， このとき $\alpha^k$ は原始 $n$ 乗根である．このような $k$ は$\varphi (n)$個ある． 定理21 から原始 $n$ 乗根はちょうど$\varphi (n)$個なので， これらが原始 $n$ 乗根のすべてである．

解答 30 (問題30)        $\alpha=\cos \dfrac{2\pi}{a}+i\sin \dfrac{2\pi}{a}$ ， $\beta=\cos \dfrac{2\pi}{b}+i\sin \dfrac{2\pi}{b}$ とおく．整數 $x，\ y$ に対して

$$\alpha^x\beta^y=\cos \dfrac{2(bx+ay)\pi}{ab}+i\sin \dfrac{2(bx+ay)\pi}{ab}$$

となる． 定理17（6節）の証明にあるように，$x，\ y$ に $a，\ b$ を法とする剰余系の値を与えれば $bx+ay$ は $ab$ を法とする剰余系になり， $x，\ y$ に $a，\ b$ を法とする既約剰余系の値を与えれば $bx+ay$ は $ab$ を法とする既約剰余系になる．

解答 31 (問題31)        $(k,\ e)=d$ とおき， $k=k'd,\ e=e'd$ とする．

$$(a^k)^{e'}=a^{k'de'}=(a^e)^{k'}\equiv 1\quad (\bmod.\ m)$$

逆に $(a^k)^x\equiv 1\quad (\bmod.\ m)$ とする．このとき定理24から $kx$ は $e$ の倍数である．このとき $k'x$ が $e'$ の倍数になる． ところが $(k',\ e')=1$ だから $x$ は $e'$ の倍数である．

ゆえに $(a^k)^x\equiv 1\quad (\bmod.\ m)$ となる最小の $x$ が $e'=\dfrac{e}{(k,\ e)}$ である．

解答 32 (問題32)  

(1)

$n=1$ のとき． $f(x)=ax+b\ (a と p は互いに素)$ とおく．

$0 \le i<j\le p-1$ の二つの整数 $i,\ j$ に対し

$$f(i)\equiv f(j)\quad (\bmod.\ p)$$

とする． $f(i)-f(j)=a(i-j)\equiv o\quad (\bmod.\ p)$ で $(a,\ p)=1$ なので $i\equiv j\quad (\bmod.\ m\ p)$ ． $0<j-i<p-1$ よりこれはあり得ない．

ゆえに $\{f(0),\ f(1),\ \cdots,\ f(p-1)\}$ は $p$ を法とする剰余系である．

$$∴\quad f(x)\equiv 0\quad (\bmod.\ p)\ となる x\ (0 \le x \le p-1) はただ一つである．$$

$n=k$ のとき(1)の命題が成立しているとする．

$n=k+1$ のときの成立を背理法で示す．

$$0 \le i_1<i_2<\cdots<i_{k+2}\le p-1$$

で

$$f(i_u)\equiv 0\quad (\bmod.\ p)\ u=1,\ 2,\ \cdots,\ k+2$$

となったとする．

このとき $f(x)-f(i_1)$ は $x-i_1$ を因数にもつので

$$f(x)-f(i_1)=(x-i_1)g(x)$$

とおく． $f(x)=ax^n+\cdots$ なら

$$f(x)-f(i_1)=a(x^n-i_1^n)+\cdots=(x-i_1)(ax^{n-1}+\cdots)$$

となるので $g(x)$ は最高次の係数が $p$ の倍数でない $n-1=k$ 次式である．

$$f(i_u)-f(i_1)=(i_u-i_1)g(i_u)\equiv 0\quad (\bmod.\ p)\ u=2,\ 3,\ \cdots k+1$$

であるが $(i_u-i_1,\ p)=1$ なので

$$g(i_u)\equiv 0\quad (\bmod.\ p)\ u=2,\ 3,\ \cdots k+1$$

である．これは $n=k$ で(1)の命題が成立しているとの帰納法の仮定と矛盾する．

したがって対偶が示され， $n=k+1$ 次の場合も

$$f(0),\ f(1),\ \cdots,\ f(p-1)$$

のうちで， $p$ の倍数となるものは， $k+1$ 個以下である．

ゆえに$n$ に関する数学的帰納法により(1)の命題が成立する．

(2)

$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots$ とおき， その係数に$p$ の倍数ではないものがあるとする． (1)から $a_n\equiv 0\quad (\bmod.\ p)$ である． $n$ 次の方から順に見て最初に $p$ の倍数でない係数を $a_m$ とする．

$$f(x)=a_nx^n+\cdots+a_{m+1}x^{m+1}+g(x)\quad g(x)=a_mx^m+\cdots$$

とおく．任意の整数 $l$ に対して $f(l)\equiv g(l)\quad (\bmod.\ p)$ なので

$$g(0),\ g(1),\ \cdots,\ g(p-1)$$

のうちに， $p$ の倍数となるものが $n+1$ 個以上ある．したがって(1)から $a_m\equiv 0\quad (\bmod.\ p)$ でなければならず， $a_m$ が $n$ 次の方から順に見て最初に $p$ の倍数でない係数であることと 矛盾した．

したがって $f(x)$ の係数に$p$ の倍数ではないものはない．つまり(2)が示された．

(3)

$f(x)=(x-1)(x-2)\cdots(x-p+1)-x^{p-1}+1$ は明らかに $p-2$ 次式である． ところが $i=1,\ 2,\ \cdots,\ p-1$ に対してフェルマの小定理より

$$f(i)=-i^{p-1}+1\equiv 0\quad (\bmod.\ p)$$

である．(2)から $f(x)$ のすべての係数は $p$ の倍数である． $p$ が奇素数なら

$$f(0)=(-1)\cdots(-1+p)+1=(p-1)!+1$$

より $(p-1)!+1$ が $p$ の倍数． $p=2$ のときも $(p-1)!+1=2$ より成立．

(4)

$p$ が素数なら(3)から $(p-1)!+1$は $p$ の倍数．ところが

$$(p-1)!+1=(p-1)!+1-p+1=(p-1)\{(p-2)!-1\}+p$$

で $(p-1,\ p)=1$ より $(p-2)!-1$は $p$ の倍数．

$p$ が素数でなければ $p=uv\ 0<u,\ v<p-1$ と因数分解される．

$(p-2)!$ は $u$ の倍数になる．したがって$(p-2)!-1$は $u$ の倍数ではなく $p$ の倍数でもない．

$$∴\quad p が素数\quad \iff\quad (p-2)!-1 が p の倍数$$

注意 9.1.2        例(3)(4)については『めざせ，数学オリンピック』(J.コフマン，現代数学社) にいくつかの計算例が載っている．

それを紹介する．

20以下の素数 $p$ について $(p-1)!+1$ を計算する．

$$\begin{eqnarray*} (2-1)!+1&=&2\\ (3-1)!+1&=&3\\ (5-1)!+1&=&25=5^2\\ (... ...=&6402373705728001=19\cdot23\cdot29\cdot61\cdot67\cdot123610951 \end{eqnarray*}$$

20以下の$p$ について $(p-2)!-1$ を計算する．

$$\begin{eqnarray*} (3-2)!-1&=&0\\ (4-2)!-1&=&1\\ (5-2)!-1&=&5\\ (6-2)!... ...7\\ (20-2)!-1&=&6402373705727999=59\cdot226663\cdot478749547 \end{eqnarray*}$$

解答 33 (問題33)        $M=(m!)^2+1$とおく． $M$は $1,\ \cdots,\ m$ で割り切れないので $M$の1でない因数はすべて $m$ より大きい． そこで $M$ が $4n-1$ 型の素因数 $p$ をもったとする． $p>m$ である． フェルマの小定理から

$$(m!)^p\equiv m!\quad (\bmod.\ p)$$ (9.5)

次に$p=4r+3$とおき，因数分解

$$x^{2k+1}+1=(x+1)(x^{2k}-x^{2k-1}+x^{2k-2}-\cdots-x+1)$$

を $x=(m!)^2,\ k=r$ で用いる．このとき $M=x+1$ であるから 因数分解は $\{(m!)^2\}^{2r+1}+1$ が $M$ で割り切れることを示している． 一方，

$$\{(m!)^2\}^{2r+1}+1=(m!)^{4r+2}+1=(m!)^{p-1}+1$$

である． $M$ で割り切れるならその素因数 $p$ でも割り切れる．

$$∴\quad m!\{(m!)^{p-1}+1\}=(m!)^p+m!\equiv 0\quad (\bmod.\ p)$$ (9.6)

(9.5), (9.6)から

$$2m!\equiv 0\quad (\bmod.\ p)$$

これは $p>m$ と矛盾した． ゆえに $M$ は $4n-1$ 型の素因数はもたない．つまりすべての素因数は$4n+1$ 型の素数である．

任意の自然数 $m$ に対して，$M$の素因数 $p$ は必ず存在し($M$ 自身が素数なら $M$ ， $M$ が合成数なら $M$ の素因数)，$p$は$p>m$である$4n+1$ 型の素数になる． つまり任意の自然数 $m$ に対してそれより大きい $4n+1$ 型の素数がつねに存在するので $4n+1$ 型の素数は無数に存在する．

解答 34 (問題34)  

$$\begin{eqnarray*} 10^1&=&10+91\cdot 0\\ 10^2&=&9+91\cdot 01\\ 10^3&=&90+91\... ...ot 0109\\ 10^5&=&82+91\cdot 01098\\ 10^6&=&1+91\cdot 010989 \end{eqnarray*}$$

10 の法 91 に対する指数 $e$ は 6 である．

$\varphi(91)=\varphi(7)\varphi(13)=72$であるから分母が91の既約真分数は72個ある．

したがって，72個の分数が6個ずつ12の循環節が等しい群に分かれる．

$$\begin{eqnarray*} \dfrac{1}{91}&=&\dfrac{010989}{10^6-1}\\ &=&\dfrac{010989}{... ...+\dfrac{1}{10^{12}}+\cdots \right\}\\ &=&0.\dot{0}1098\dot{9} \end{eqnarray*}$$

これから次の循環小数ができる．

$$\begin{array}{lll} \dfrac{10}{91}&=\dfrac{10^1}{91}-0&=0.\... ...1}&=\dfrac{10^5}{91}-01098&=0.\dot{9}0109\dot{8} \end{array}$$

分子と循環節は次の通り．

$$\begin{array}{rrrrrrr\vert l} &&分&子&&&&循環節\\ ... ...line 12)&23&48&25&68&43&66&252747\\ \hline \end{array}$$

解答 35 (問題35)        $a=2$ をとってみる．

$2^6=64\equiv 23\,(\bmod.\ 41)$ ， $2^7\equiv 46\equiv 5\,(\bmod.\ 41)$ ， $2^8\equiv 10\,(\bmod.\ 41)$ ， $2^9\equiv 20\,(\bmod.\ 41)$ ， $2^{10}\equiv 40\equiv -1\,(\bmod.\ 41)$ ． $∴\quad 2^{20}\equiv 1\,(\bmod.\ 41)$

したがって $a=3$ は原始根でない．今の計算に現れず $a$ のべきと互いに素な 数として $b=3$ をとる． $3^4=81\equiv -1\,(\bmod.\ 41)$なので $3^8\equiv 1\,(\bmod.\ 41)$ したがって3の指数は8である． $(20,\ 8)=4$ なので $4=1\cdot4$ とし $m_0=\dfrac{20}{4}=5,\ n_0=\dfrac{8\cdot4}{4}=8$ とする．

$$2^{ \frac{20}{5}}\cdot 3^{ \frac{8}{8}}=2^4\cdot3=48\equiv 7\,(\bmod.\ 41)$$

7の指数が $5\times 8=40$ になるので7は原始根である．

解答 36 (問題36)  

(1)

$100\equiv 9\quad (\bmod.\ 13)．\quad ∴\quad \Ind.100=\Ind.9=8$

(2)

$-1\equiv 12\quad (\bmod.\ 13)．\quad ∴\quad \Ind.(-1)=\Ind.12=6$

(3)

$I$ の欄が9になるのは, $a$ の欄が5．∴ $x\equiv 5\quad (\bmod.\ 13)$

(4)

$-1\equiv 11\quad (\bmod.\ 12)$．$I=11$ に対する $a=7$．∴ $x\equiv 7\quad (\bmod.\ 13)$．

解答 37 (問題37)  

(1)

$\Ind_211=7,\ \Ind_25=9$なので $\Ind_2x\equiv 2\ (\bmod.\ 12)$．ゆえに $x\equiv 4 \ (\bmod.\ 13)$ ．

(2)

$3\Ind_2x\equiv 9\ (\bmod.\ 12)$より $\Ind_2x\equiv 3\ (\bmod.\ 4)$．表から $x\equiv 7,\ 8,\ 11 \ (\bmod.\ 13)$ ．

(3)

$5x^2+3x\equiv 10\ (\bmod.\ 13)$より $5(x-1)^2\equiv 15\ (\bmod.\ 13)$ ． 5と13は互いに素なので $(x-1)^2\equiv 3\ (\bmod.\ 13)$ ． 表から$\Ind_23=4$なので $2\Ind_2(x-1)\equiv 4\ (\bmod.\ 12)$．これより $\Ind_2(x-1)\equiv 2\ (\bmod.\ 6)$．表から $x-1\equiv 4,\ 9\ (\bmod.\ 13)$． よって $x\equiv 5,\ 10\ (\bmod.\ 13)$ ．

解答 38 (問題38)  

$$\left(r^{\frac{p-1}{2}}-1\right)\left(r^{\frac{p-1}{2}}+1\right) =r^{p-1}-1\equiv 0\quad (\bmod.\ p)$$

ところが $r$ は原始根なので $r^{\frac{p-1}{2}}\not\equiv 1\quad (\bmod.\ p)$． ゆえに $r^{\frac{p-1}{2}}\equiv -1\quad (\bmod.\ p)$ ．

つまり題意が示された．

解答 39 (問題39)        $a\equiv -b\quad (\bmod.\ p)$ である．ゆえに

$$\begin{eqnarray*} \Ind.a&=&\Ind.(-1)+\Ind.b\\ &\equiv& \dfrac{p-1}{2}+\Ind.b\quad (\bmod.\ p-1) \end{eqnarray*}$$

つまり題意が示された．

解答 40 (問題40)        $r^{\alpha}\equiv a\quad (\bmod.\ p)$とおく． さらに$s=\Ind_{r'}r$ ，つまり $r\equiv {r'}^{s}\quad (\bmod.\ p)$ とおく．あわせて

$${r'}^{s\alpha}\equiv a\quad (\bmod.\ p)\quad \Rightarrow \quad \Ind_{r'}\alpha\equiv s\Ind_r\alpha$$

両辺 $s$ で割って題意の式を得る．

解答 41 (問題41)        $r$ を法 $p$ の原始根とすれば$k$ が $p-1$ で割りきれないので二つの集合

$$\begin{array}{l} \{1^k,\ 2^k,\ \cdots,\ (p-1)^k \}\\ \{1,\ r^k,\ \cdots,\ r^{(p-2)k} \} \end{array}$$

の各元は互いに $p$ を法として合同の関係で一対一に対応している．ゆえに

$$\begin{eqnarray*} &&1^k+2^k+\cdots+(p-1)^k\\ &\equiv&1+r^k+\cdots+r^{(p-2)k}\\ &\equiv&\dfrac{r^{(p-1)k}-1}{r^k-1} \equiv 0\quad (\bmod.\ p) \end{eqnarray*}$$

ここで分子は $r^{(p-1)k}-1\equiv 1^k-1\equiv ０\quad (\bmod.\ p)$ ， 分母は $r^k-1\not\equiv 0\quad (\bmod.\ p)$ であることに注意する．

解答 42 (問題42)  

$$\begin{eqnarray*} (p-1)!&\equiv& r^{1+2+\cdots+(p-2)}\\ &=& \left(r^{ \frac{p... ...\right)^{p-2}\\ &\equiv &(-1)^{p-2}\equiv -1\quad (\bmod.\ p) \end{eqnarray*}$$

解答 43 (問題43)  

$$\begin{array}{lll} \left(\dfrac{365}{1847}\right)&=\left(\... ...\dfrac{-1}{11}\right)&\\ &=1&(第一補充則) \end{array}$$

解答 44 (問題44)  

$$\left(\dfrac{-2}{p}\right)=\left(\dfrac{-1}{p}\right)\left(\dfrac{2}{p}\right) =(-1)^{ \frac{p-1}{2}+\frac{p^2-1}{8}}$$

ここで

$$\dfrac{p-1}{2}+\dfrac{p^2-1}{8}=\dfrac{p^2+4p-5}{8}=p-1+\dfrac{p^2-4p+3}{8} \equiv \dfrac{(p-3)(p-1)}{8}\quad (\bmod.\ 2)$$

$p-3,\ p-1$は隣り合う二つの偶数なのでともに4の倍数になることはない． ゆえに$(p-3)(p-1)$が16の倍数になるのは$p-3,\ p-1$のいずれかが8の倍数になるときにかぎる．

解答 45 (問題45)        相互法則から

$$\left(\dfrac{5}{p}\right)=\left(\dfrac{p}{5}\right)$$

ところが法5については

$$3^2\equiv 4,\ 4^2\equiv 1\quad (\bmod.\ 5)$$

なので

1. $p\equiv 1,\ 4\quad (\bmod.\ 5)$ のとき $\left(\dfrac{p}{5}\right)=1$
2. $p\equiv 2,\ 3\quad (\bmod.\ 5)$ のとき $\left(\dfrac{p}{5}\right)=-1$

となり，あわせて題意が示された．

解答 46 (問題46)        相互法則から

$$\left(\dfrac{3}{p}\right)=(-1)^{\frac{p-1}{2}}\left(\dfrac{p}{3}\right)$$

$p$ を 3, 4, 12 を法とする剰余で分類して値を決める．

$$p= \begin{array}{c\vert c\vert c\vert\vert c\vert c\vert ... ...&+1\\ 1&-1&5&1&-1&-1\\ -1&1&-5&-1&1&-1\\ \end{array}$$

したがって確かに題意が成立している．

解答 47 (問題47)  

$$a^2\equiv (p-a)^2\quad (\bmod.\ p)$$

で

$$x^2\equiv a^2\quad (\bmod.\ p)$$

となる $X$ は二つしかないので $p$ を法として，

$$1^2,\ 2^2,\ \cdots,\ (p-1)^2$$

はちょうど二つずつが同じになる． したがって

$$1,\ 2,\ \cdots,\ p-1$$

のうち半分が平方剰余で半分が非剰余である．

$$∴\quad \sum_{a=1}^{p-1}\left(\dfrac{a}{p}\right)=0$$

ところが第一補充法則から

$$\left(\dfrac{p-a}{p}\right)=\left(\dfrac{-a}{p}\right) =\l... ...{p}\right)\left(\dfrac{a}{p}\right)=\left(\dfrac{a}{p}\right)$$

したがって

$$\sum_{a=1}^{ \frac{p-1}{2}}\left(\dfrac{a}{p}\right)=0$$

また $a$ と $p-a$ の偶数奇数は逆なので

$$\sum_{0\le b\le p\ の偶数}\left(\dfrac{b}{p}\right) =\sum_{0\le c\le p\ の奇数}\left(\dfrac{c}{p}\right)$$

となり，これはともに0である．

解答 48 (問題48)  

$$\begin{eqnarray*} 5&=&N(1+2i)=1^2+2^2\\ 13&=&N(3+2i)=9^2+2^2\\ 65&=&N(1+2i)... ...(1+2i)^2=N(1+7i)=1^2+7^2\\ 13^3&=&N(3+2i)^2=N(5+12i)=5^2+12^2 \end{eqnarray*}$$

訂正:13=3²+2² 　　　　　　　　　　　　　　　　　　　　

解答 49 (問題49)        $z$ が偶数なら$x^2+y^2=z^2$の右辺は4の倍数．左辺が4の倍数になるのは $x,\ y$ とも偶数のときにかぎる．$(x,\ y)=1$よりこれはあり得ない．ゆえに $z$ は奇数．

また $x+iy$ と $x-iy$ に単数以外の公約数があれば，それを $\alpha$ とすると その共役も公約数になり，公約数として実数$a$がとれ$x+iy=a(p+qi)$ と $x-iy=a(p-qi)$ となる．ゆえに $x=ap,\ y=aq$ となって$(x,\ y)=1$に反する． ゆえに, $x+iy$ と $x-iy$ は互いに素である．

$z^2=x^2+y^2=(x+iy)(x-iy)$ となるので単数倍を除けば$x+iy$ と $x-iy$自体が ガウス整数の平方である．つまり

$$x+iy=\epsilon(m+in)^2\ ,\ \quad x-iy=\bar{\epsilon}(m-in)^2$$

とおける．ただし $\epsilon$ は単数である．

$(x,\ y)=1$より$(m,\ n)=1$で，さらに$x+iy$ と $x-iy$はともに2の因数 $\pm 1 \pm i$ で 割れないので，$m+in$ と $m-in$も$\pm 1 \pm i$ で割れない．つまり $m$ と $n$ の一方が 偶数で他方が奇数である．

このとき

$$x+iy=\epsilon(m^2-n^2+2imn) \ ,\ z=m^2+n^2$$

となり，題意が示された．

注意 9.1.3   これはガウス環を用いてピタゴラス数の一般解を求めるものである．

解答 50 (問題50)        3次方程式の他の解は実数なのでこれを$\beta$とおく．解と係数の関係から

$$\begin{eqnarray*} &&u+vi+u-vi+\beta=-p\\ &&(u+vi)(u-vi)+\beta(u+vi)+\beta(u-vi)=q\\ &&(u+vi)(u-vi)\beta=-r \end{eqnarray*}$$

となる．これを整理して

$$\begin{eqnarray*} &&2u+\beta=-p\\ &&u^2+v^2+2u\beta=q\\ &&(u^2+v^2)\beta=-r \end{eqnarray*}$$

である．

まず$u$がある整数$a$を用いて$\dfrac{a}{2}$と表せること示す． 第2式から

$$(u^2+v^2)\beta+2u\beta^2=q\beta$$

ここに第1式,第3式を用いて$\beta$と$u^2+v^2$を消去する．

$$-r+2u(-2u-p)^2=q(-2u-p)$$

整理して

$$8u^3+8pu^2+2(p^2+q)u+pq-r=0$$

ここで有理数$u$を互いに素な整数$a$と$b$を用いて $u=\dfrac{a}{b}\ (b>0)$とおく． 方程式に代入して$b^3$を乗じ一部移項する．

$$8a^3=-b\{8pa^2+2(p^2+q)ab+(pq-r)b^2\}$$

右辺は$b$の倍数である． 左辺も$b$の倍数であるが$a^3$と$b$は互いに素なので， 8が$b$の倍数，つまり$b$が8の約数となることが必要である．

$b=8$なら代入して8で割ると

$$a^3=-\{8pa^2+16(p^2+q)a+64(pq-r)\}$$

これから$a$が偶数となり$a$と$b$が互いに素に反する．

$b=4$なら代入して8で割ると

$$a^3=-\{4pa^2+4(p^2+q)a+84(pq-r)\}$$

これから$a$が偶数となり$a$と$b$が互いに素に反する．

よって$b =1,\ 2$．つまり$u$は整数$a$を用いて $u=\dfrac{a}{2}$とおける．

この結果，$\beta=-p-2u$が整数となりさらに $u^2+v^2=q-2u\beta$も整数である．

$$v^2=-u^2+q-2u=\dfrac{-a^2+4q-4a}{4}$$

なので有理数$v$も整数$c$を用いて $v=\dfrac{c}{2}$とおける．そして

$$u^2+v^2=\dfrac{a^2+c^2}{4}$$

が整数． そのためには分子が偶数でなければならないので$a,\ c$がともに偶数かともに奇数であることが必要． ともに奇数の場合 $a=2k+1,\ c=2l+1$とすると

$$a^2+c^2=4(k^2+k+l^2+l)+2$$

となり $\dfrac{a^2+c^2}{4}$が整数でない．

よって$a$も$c$も偶数となり，その結果$u$と$v$が整数となる．

注意 9.1.4        ガウスによる有理整数係数の多項式に関する定理：

整数係数多項式$f(x)$が有理数の範囲で因数分解されれば， 有理整数の範囲で因数分解される．

を用いると，$\alpha$が$x^2$の係数が1の 有理整数係数の二次方程式の根であることがわかる． この二次方程式を$x^2+lx+m=0$とおくと，

$$\alpha=\dfrac{-l\pm\sqrt{4m-l^2}i}{2}$$

となる．これから$\sqrt{4m-l^2}$が整数とならねばならず， $4m-l^2=b^2$とおく．$b$が奇数とすると$l$も奇数であるが，このとき両辺4で割った余りが異なるので，これはない．かくして$b,\ l$が偶数となり， 題意が示される．

注意 9.1.5        最高次の項の係数が1である整数係数の代数方程式の解となる数を 「(代数的)整数」と呼ぶ． ガウス整数 $a+bi\ (a,\ b\in \mathbb{Z})$は 二次方程式 $x^2-2ax+a^2+b^2=0$の解なので代数的整数である．

ガウス整数環に対してその商環

$$\left\{\dfrac{c+di}{a+bi}\bigl\vert\ a,\ b,\ c,\ d \in \mathbb{Z},\ a+bi\ne 0 \right\}$$

は体である．ガウス商体といおう．これは分母を実数化することで

$$\left\{u+vi\ \vert\ u,\ v \in \mathbb{Q}\right\}$$

と同じものになる．

本問はガウス商体の元で代数的整数であるものの集合は， ちょうどガウス整数環になることを示している．

代数的整数の理論が19世紀末から20世紀にかけて大発展した． 『数論初歩』に引き続く分野である． 高木貞治はこの分野で「類体論」と呼ばれる決定的な仕事をした．

解答 51 (問題51)  

$$\begin{eqnarray*} \sqrt{7} &=& \matrix{2}{1}{1}{0} \left( \dfrac{1}{\sqrt{7}-2... ...}{14}{3}\left(\dfrac{\sqrt{7}+2}{3}\right) \\ &\cdots&\cdots \end{eqnarray*}$$

したがって

$$\dfrac{2}{1} <\dfrac{5}{2} <\dfrac{37}{14} <\cdots <\sqrt{7} < \cdots <\dfrac{8}{3} <\dfrac{3}{1}$$

解答 52 (問題52)        $ax^2+bxy+cy^2 = \dfrac{2\sqrt{-D}}{\pi}$はちょうど面積が4の楕円である． これについては『数学対話』「三角形に辺の中点で内接する楕円(シュタイナー楕円）」の なかの「一次変換」参照のこと．ゆえにミンコフスキーの定理より領域 $ax^2+bxy+cy^2 \le \dfrac{2\sqrt{-D}}{\pi}$ には原点以外の格子点が含まれる．

解答 53 (問題53)  

1. $(x,\ y)\in S$ かつ $x+\sqrt{D} y >1$ であるものの中で最小の元を確定させなけ ればならない. そこで, まず
   
   $$x+\sqrt{D}y>1\ ならば, \ x>0, \ y>0$$
   
   
   を示す. $x^2-Dy^2=(x+\sqrt{D}y)(x-\sqrt{D}y)=\pm 1$ より,
   
   $$\vert\,x-\sqrt{D}y\,\vert=\dfrac{1}{x+\sqrt{D}y}<1$$
   
   
   したがって,
   
   $$-1<x-\sqrt{D}y<1$$
   
   
   となる. すると, $1<x+\sqrt{D}y$, $-1<x-\sqrt{D}y$ より,
   
   $$0<2x\qquad∴\quad x>0$$
   
   
   また, $1<x+\sqrt{D}y$, $-1<-x+\sqrt{D}y$ より,
   
   $$0<2\sqrt{D}y\qquad∴\quad y>0$$
   
   
   以上より, $x>0,\ y>0$ という条件のもとで, $x+\sqrt{D} y$ の値が最小と なるものを考 えればよい.
   1. $D=2$ のとき, $(x,\ y)=(1,\ 1)$ に対して,
      
      $$x^2-2y^2=1^2-2\cdot1^2=-1\qquad∴\quad (1,\ 1)\in S$$
      
      
      となり, 上の考察と合わせると, これが求めるものである. この場合,
      
      $$A=\matrix{p}{2q}{q}{p}=\matrix{1}{2}{1}{1}$$
      
      

   2. $D=3$ のとき, $(x,\ y)=(1,\ 1),\ (2,\ 1)$ に対して,
      $$\begin{eqnarray*} &&(x,\ y)=(1,\ 1)\ のとき, \ x^2-3y^2=1^2-3\cdot1^2\ne\pm... ...とき, \ x^2-3y^2=2^2-3\cdot1^2 =1\,\,∴\,\,(2,\ 1)\in S \end{eqnarray*}$$
      
      
      となり, 上の考察と合わせると, $(x,\ y)=(2,\ 1)$ が求めるものである. この場 合,
      
      $$A=\matrix{p}{3q}{q}{p}=\matrix{2}{3}{1}{2}$$
      
      

2. $x^2-3y^2=-1$ の解があれば, $x^2\equiv -1\quad (\bmod.\ 3)$ となる $x$ が存在することになるが， オイラーの規準より
   
   $$\left(\dfrac{-1}{3} \right)=(-1)^{\frac{3-1}{2}}=-1$$
   
   
   なので，法3に関して $-1$ は平方剰余ではないので，そのような解はない．

解答 54 (問題54)        $\omega_1=4+\sqrt{13}$ のとき． $D=13$ である．

$$\begin{array}{lll} \omega&二次方程式&\omega'\\ \... ...}{\sqrt{13}-3}=\dfrac{\sqrt{13}+3}{4}=\omega_2& \end{array}$$

解答 55 (問題55)  

$$\begin{array}{lll} \sqrt{19}&=\matrix{4}{1}{1}{0}x_1&x_1... ...}{1}{1}{0}x_7&x_7=\dfrac{1}{\sqrt{19}-4} =x_1 \end{array}$$

ゆえに $k=6$ 最小解 $(x,\ y)=(170,\ 39)$ ．

$$170^2-19\cdot39^2=1$$

解答 56 (問題56)  

$$\begin{array}{lll} \sqrt{46}&=\matrix{6}{1}{1}{0}x_1&x_1... ...}{0}x_{13}&x_{13} =\dfrac{1}{\sqrt{46}-6}=x_1 \end{array}$$

ゆえに $k=12$ 最小解 $(x,\ y)=(24335,\ 3588)$ ．

$$24335^2-19\cdot3588^2=1$$

次: 入試問題解答 上: 解答 前: 解答