次: 出典と文献 上: 解答 前: 演習問題解答

入試問題解答

解答 1 (問題1)  

(1)

$$\begin{array}{ll} &a_1=1998,\ b_1=185\\ 1998=185\time... ...0より &a_4=37,\ b_4=0\\ &a_5=37,\ b_5=0 \end{array}$$

(2)

$b_n\ne 0$ のとき $b_{n+1}$ は $a_n$ を$b_n$ で割った余りであるから 余りの定義より，

$$0\le b_{n+1}<b_n$$

$b_n=0$ のとき 数列 $\{ b_n \}$ の定義から $b_{n+1}=b_n$ ． よって 任意の $k,\ l,\ n$ について $b_n\ge b_{n+1}$ (等号は $b_n=0$ のときに限る) が成立する．

(3)

もし $b_n=0$ となる $n$ が存在しないとすると， すべての $b_n$ は自然数でしかも

$$b_n>b_{n+1}$$

が成り立つ．このことは 集合 $\{b_n \ \vert\ n=1,\ 2,\ \cdots\ \}$に最小値が存在しないことになり， 自然数の部分集合にはつねに最小値が存在するという，自然数の基本性質と矛盾する． よって$b_n=0$ となる $n$ が存在する．

(4)

$(a,\ b)$ で $a$ と $b$ の最大公約数を表すことにする． $b_k\ne 0$ のとき

$$(a_k,\ b_k)=(b_k,\ b_{k+1})$$

を示す．

$a_k$を$b_k$で割った商を$q_k$とおくと， $a_k=b_k\cdot q_k+b_{k+1}$ とかける． これから$a_k$ と $b_k$ の公約数は $b_{k+1}$ の 約数になり，$b_k$と$b_{k+1}$の公約数である． $b_k$と$b_{k+1}$の公約数で最大のものが最大公約数 $(b_k,\ b_{k+1})$である． ゆえに $(a_k,\ b_k)\le(b_k,\ b_{k+1})$． また$b_k$ と $b_{k+1}$ の公約数は $a_k$ の約数になる． 同様に考え $(a_k,\ b_k)\ge(b_k,\ b_{k+1})$である．

$$∴\quad (a_k,\ b_k)=(b_k,\ b_{k+1})$$

これをいいかえると $(a_k,\ a_{k+1})=(a_{k+1},\ a_{k+2})$． (3)からある自然数 $N$ で $b_{N-1}\ne0,\ b_N=0$ となるものがある．このとき

$$(k ,\ l)=(a_1,\ a_2)= \cdots=(a_{N-1},\ a_N)=(a_N,\ b_N) =a_N$$

$N\le n$ の $n$ で同様の等式が成り立つので題意が示された．

解答 2 (問題2)  

(1)

$r_{n-1}>0$ のとき,

$$r_{n-2}=r_{n-1}q_{n-1}+r_{n},\quad 0\leq r_n<r_{n-1}$$

したがって,

$$r_1=a\geq r_2=b>r_3>r_4>\cdots\geq 0$$

となり, 各 $r_n$ は自然数または0であるから, 高々 $a+1$ 回 この操作を繰り返すとこれは0となる. つまり,

$$r_{N-1}>r_N>0=r_{N+1}$$

となる整数 $N$ が存在する.

(2)

$k$ についての帰納法で示す.

(i)

$k=1$ のとき,

$$r_{N+2-k}=r_{N+1}=0, \ f_k=f_1=0$$

なので, 不等式は成り立つ. 次に, $k=2$ のとき,

$$r_{N+2-k}=r_N\geq 1, \ f_k=f_2=1$$

よって, 不等式は成り立つ.

(ii)

$k=m-1,\ m\ (m\geq 2)$ のときの不等式の成立, すなわち,

$$r_{N+2-(m-1)}\geq f_{m-1},\quad r_{N+2-m}\geq f_m$$

を仮定する. このとき,

$$\begin{eqnarray*} r_{N+2-(m+1)} &=& r_{N+2-m}\cdot q_{N+2-m}+r_{N+2-(m-1)} \\ ... ...{m-1} \quad (なぜなら, \ q_{N+2-m}\geq1) \\ &=& f_{m+1} \end{eqnarray*}$$

となるので, $k=m+1$ のときも成立する.

(iii)

よって, (i), (ii)より, $k=1,\ 2,\ \cdots,\ N+1$ の すべての $k$ に対して不等式が成り立つ.

(3)

$n$ に関する帰納法で示す.

(i)

$n=1$ のとき,

$$f_{n+1}=f_2=1, \ \left(\dfrac{3}{2}\right)^{n-2} =\left(\dfrac{3}{2}\right)^{1-2}=\dfrac{2}{3}$$

$n=2$ のとき,

$$f_{n+1}=f_3=f_2+f_1=1, \ \left(\dfrac{3}{2}\right)^{n-2} =\left(\dfrac{3}{2}\right)^{2-2}=1$$

よって, いずれの場合も不等式は成り立つ.

(ii)

$n=k-1,\ k\ (k\geq 2)$ のときの不等式の成立, すなわち

$$f_k\geq\left(\dfrac{3}{2}\right)^{k-3},\quad f_{k+1} \geq\left(\dfrac{3}{2}\right)^{k-2}$$

を仮定する. このとき

$$\begin{eqnarray*} f_{(k+1)+1} &=& f_{k+1}+f_k \\ &\geq & \left(\dfrac{3}{2}... ...rac{9}{4}\right)\\ &=& \left(\dfrac{3}{2}\right)^{(k+1)-2} \end{eqnarray*}$$

よって, $n=k+1$ のときも不等式は成り立つ.

(iii)

よって, (i), (ii)より, すべての自然数 $n$ に対して不等式が成り立つ.

(4)

(2)より, $k=N+1$ のとき,

$$a=r_1=r_{N+2-(N+1)}\geq f_{N+1}$$

よって, (3)より,

$$a \geq \left(\dfrac{3}{2}\right)^{N-2}$$

で, 両辺の底を $\dfrac{3}{2}$ とする対数をとれば,

$$\log_{\frac{3}{2}}a \geq N-2\qquad∴\quad N \leq 2+\log_{\frac{3}{2}}a$$

注意 9.2.1   この入試問題は，ユークリッドの互除法で割り算をどれくらい行えばよいかを評価するものである． いちばん長くなるのが，割り算での商が常に 1 になるときで，あまりの列を逆にたどればいわゆる フィボナッチ数列になるときである．このことを問う本格的な問題である．

解答 3   問題3 $S$に属する最小の数を$d$とする． $S$の任意の要素$a$をとり，$a$を$d$で割り商が$q$，余りが$r$とする．

$$a=dq+r$$

$r>0$とする． $a-d \in S$であり，自然数$1\le j<q$に対して $a-jd \in S$なら $a-jd-d=a-(j+1)d \in S$なので，数学的帰納法で$r=a-dq\in S$である． $d$が$S$に属する正で最小の整数という仮定に反する．よって$r=0$である． $S$のすべての要素は$d$の倍数である．

$S$に属する最大の要素を$md$とおく， $1<j\le m$の整数に対して$jd \in S$なら $jd-d=(j-1)d\in S$なので

$$md,\ (m-1)d,\ \cdots,\ d$$

はすべて$S$に属する．要素の個数を考え$m=n$であり

$$S=\{nd,\ (n-1)d,\ \cdots,\ d\}$$

となる． $a_1,\ a_2,\ \cdots ,\ a_n$ の順序を適当に変えれば 初項$d$，公差$d$の等差数列になる．

※　大小の順で並べ替えて示してもよい．

解答 4   問題4

(1)

（イ），（ロ）とも成り立たないとする．$S$の属する最大の数を$M$， 最小の数を$m$とする． このとき$m<0<M$が成り立っている．$M-m$か$m-M$は$S$に属するので， $M<M-m$または$m-M<m$が成り立つ． これは$M$の最大性または$m$の最小性に矛盾する． よって（イ），（ロ）のうちいずれか一方が成立する．

(2)

（イ）が成り立っているとする． $S$の要素で正で最小のものを$d$とする．

$S$の$d$と異なる正の任意の要素$a$をとる．

$$qd\le a<(q+1)d$$

となる自然数$q$をとる．$r=a-qd$とおく． $r>0$とする． $a-d \in S$であり，自然数$1\le j<q$に対して $a-jd \in S$なら $a-jd-d=a-(j+1)d \in S$なので，数学的帰納法で$r=a-dq\in S$である． $d$が$S$の要素で正で最小のものであるという仮定に反する．よって$r=0$である． $S$のすべての要素は$d$の倍数である．

$S$に属する最大の要素を$md$とおく， $1<j\le m$の整数に対して$jd \in S$なら $jd-d=(j-1)d\in S$なので

$$md,\ (m-1)d,\ \cdots,\ d$$

はすべて$S$に属する．要素の個数は， 0が$S$にあるかどうかを考え$m=n$か$m=n-1$であり

$$S=\{nd,\ (n-1)d,\ \cdots,\ d\},\ \{(n-1)d,\ (n-2)d,\ \cdots,\ d,\ 0 \}$$

のいずれかである． $a_1,\ a_2,\ \cdots ,\ a_n$ の順序を適当に変えれば 初項が$d$または0，公差$d$の等差数列になる．

（ロ）の場合，すべての要素の絶対値をとって考えれば同様である．

※　大小の順で並べ替えて示してもよい．

解答 5   問題5 自然数$j$に対して $jd \in G$なら $d+jd=(j+1)d \in G$なので，数学的帰納法によって

$$\{kd\ \vert\ k\ は自然数\ \}\subset G$$

$G$の任意の要素$a$をとり，$a$を$d$で割り商が$q$，余りが$r$とする．

$$a=dq+r$$

$dq\in G$なので$r=a-dq\in S$である． ここで$r>0$とすると $d$が$G$に属する正で最小の整数という仮定に反する．よって$r=0$である． $G$のすべての要素は$d$の倍数である．

$$G\subset \{kd\ \vert\ k\ は自然数\ \}$$

が示され，題意が証明された．

解答 6 (問題6)  

(1)

$1\le i,\ j\le p$の範囲の$i$と$j$に対して $x-iq$と$x-jq$を$p$で割った余りが相等しいとする．それぞれの商を$l_1,\ l_2$とし，余りを$r$とすると

$$x-iq=pl_1+r,\ \quad x-jq=pl_2+r$$

辺々引いて

$$(j-i)q=p(l_1-l_2)$$

右辺は$p$の倍数であるが，$p$と$q$が互いに素なので， $j-i$が$p$の倍数でなければならない．

ところが$i$と$j$の動く範囲より

$$-1+p\le j-i\le p-1$$

この範囲にある$p$の倍数は0のみ．つまり$j-i=0$．

対偶をとって

$$i \ne j\quad ならば\quad x-iq\ と\ x-jq\ を\ p\ で割った余り は異なる．$$

ことが示された．つまり$p$個の整数 $x-q$，$x-2q$，$\cdots$，$x-pq$を$p$で割った余りはすべて相異なる．

(2)

$x-q$，$x-2q$，$\cdots$，$x-pq$を$p$で割った余りは $0,\ 1,\ 2,\ \cdots,\ p-1$の$p$個のうちのいずれかであり， しかもすべて異なる． よって$x-q$，$x-2q$，$\cdots$，$x-pq$を$p$で割った余りは $0,\ 1,\ 2,\ \cdots,\ p-1$の各値を一つずつとる．

従ってこのなかに$p$で割った余りが0， つまり$p$の倍数となるものが存在する．

それを$x-bq$とし，$x-bq=ap$とおく． $1\le b \le p$より$b$は正である．

$$ap=x-bq>(p-b)q\ge 0$$

より$a>0$である．

よって，$x>pq$なる任意の整数$x$は， 適当な正整数$a,\ b$を用いて$x=pa+qb$と表せることが示された．

解答 7 (問題7)  

(1)

$4m+6n=7$においてどのような整数 $m,\ n$ に対しても左辺は2で割り切れる． 一方右辺はつねに2で割ると1余る．ゆえにこの等式を満たす整数 $m,\ n$は存在しない．

(2)

$3m+5n=2$を満たすひと組の $(m,\ n)$ として $(-1,\ 1)$ がとれる．

任意の解$(m,\ n)$ に対して

$$\begin{array}{l} 3m+5n=2\\ 3(-1)+5(1)=2 \end{array}$$

で辺々引くと，

$$3(m+1)+5(n-1)=0$$

3と5は互いに素なので， $m+1$ が5の倍数．これを $m+1=5t$ とおく．

このとき $n-1=-3t$ となる．つまり

$$(m,\ n)=(-1+5t,\ 1-3t)$$

と表される．逆にこの形をしたものがもとの方程式を満たすことは明らか． ゆえにすべての解は

$$(m,\ n)=(-1+5t,\ 1-3t)\quad (tは任意の整数)$$

(3)

背理法で示す．

$$\begin{eqnarray*} r(k)=r(l)&\iff&ak-al が b の倍数\\ (a と b は互い... ...,\ l\le b-1より&&-(b-2)\le k-l\le b-2 \\ &∴&\quad k-l=0 \end{eqnarray*}$$

ゆえに対偶が示されたので，

$$k\ne l\quad ならば \quad r(k)\ne r(l)$$

である．

(4)

二つの集合

$$\begin{array}{l} A=\{1,\ 2,\ \cdots,\ b-1\}\\ B=\{r(k)\vert k=1,\ 2,\ \cdots,\ b-1\} \end{array}$$

この $k$ に対して $r(k)=0$ なら $ak$ が $b$ の倍数． $a$ と $b$ は互いに素なので $k$ が $b$ の倍数となるが， $k=1,\ 2,\ \cdots,\ b-1$ よりあり得ない． したがって $r(k)$ は $b$ で割った余りでしかも0でないので

$$B\subset A$$

一方(3)より

$$k\ne l\quad ならば \quad r(k)\ne r(l)$$

なので， $k=1,\ 2,\ \cdots,\ b-1$ に対して $r(k)$ はすべて異なる． つまり集合 $B$ の個数は $b-1$ で，集合 $A$ の個数と等しい．

$$∴\quad A=B$$

したがって $B$ の元のなかに

$$r(k)=1$$

となるものがある．このとき

$$ak-1が b の倍数$$

つまり $ak-1=bl$ となる $(k,\ l)$が存在した．

$(m,\ n)=(k,\ l)$ という解が存在した．

解答 8 (問題8)  

(1)

$$ax_0+by_0=c,\ al+bm=c$$

の辺々を引くと

$$a(x_0-l)+b(y_0-m)=0$$

ここで $a,\ b$ は互いに素なので， $x_0-l$ が $b$ の倍数． これを $bu\ (u は整数)$ とおく．このとき $y_0-m=-au$ となる．つまり，

$$l=x_0+bu,\ m=y_0-au$$

を満たす整数 $u$ が存在する．

(2)

$ax+by=ab$の整数解を考える．

$$a(x-b)+by=0$$

よりある整数で $y=au,\ x-b=-bu$，つまり $x=b(1-u)$と書ける ． ここで $x>0,\ y>0$ であるためには

$$0<u<1$$

これは $u$ が整数であることに反する．よって， $c=ab$ のとき $ax+by=c$ を満たす正の整数の組 $(x,\ y)$ は存在しない．

(3)

$c=ab$ のとき $ax+by=ab$ を満たす整数の組 $(l,\ m)$ は(1)から

$$l=x_0+bu,\ m=y_0-au$$

と書ける．
$l>0,\ m>0$ となるためには

$$l=x_0+bu>0,\ m=y_0-au>0$$

となる整数 $u$ がとれねばならない．つまり

$$\dfrac{y_0}{a}>u>- \dfrac{x_0}{b}$$

ところが $c>ab$ のとき

$$\dfrac{y_0}{a}-\left(-\dfrac{x_0}{b}\right) =\dfrac{ax_0+by_0}{ab} =\dfrac{c}{ab}>1$$

従って題意を満たす整数 $u$ が必ずとれる．つまり$c>ab$ のとき $ax+by=c$ を満たす正の整数の組 $(x,\ y)$ が存在する．

(4)

$0<k<ab$に対し二組の正の整数 $(x_0,y_0)$ と $(x_1,y_1)$ があるとする．

これは図の斜線領域内の格子点である．

(1)から

$$x_1=x_0+bu,\ y_1=y_0-au$$

となる整数 $u$ がある．ところがこのとき

$$x_1-x_0=bu,\ y_0-y_1=au$$

となり，明らかに2点がともに斜線領域に存在することはできない．

逆に言えば斜線領域の各格子点 $(x,\ y)$ に対する$ax+by$の値はすべて異なる． 格子点は

$$\dfrac{(a-1)(b-1)}{2}$$

個あるから，正の整数の組 $(x,\ y)$ が存在しない $k$ は

$$ab- \dfrac{(a-1)(b-1)}{2}=\dfrac{(a+1)(b+1)}{2}-1\ （個）$$

ある．

解答 9 (問題9)  

(1)

$\mathrm{A}(k,\ l),\ \mathrm{B}(m,\ n)$ とする．

$N(\mathrm{A})=N(\mathrm{B})$ より$kp+lq=mp+nq$である．つまり

$$p(k-m)=q(n-l)$$

であるが， $p$ と $q$ が互いに素なので $k-m$ が $q$ の倍数でなければならない． ところが $0\le k,\ m<q-1$ なので

$$-(q-1)<k-m<q-1$$

である．この範囲で $q$ の倍数は0しかない．つまり $k=m$ .

その結果 $l=n$ となり， $\mathrm{A}=\mathrm{B}$ であることが示された．

(2)

$\mathrm{A}^{\char93 }=\mathrm{A}$ とする．つまり

$$q-2-m=m,\ p-2-n=n$$

これから

$$q=2m+2,\ p=2n+2$$

となり， $p$ と $q$ は公約数2をもち互いに素であることに反する．ゆえに $\mathrm{A}^{\char93 } \ne \mathrm{A}$ である．

(3)

条件 $N(\mathrm{A})\le pq-(p+q)$ は

$$mp+nq\le pq-(p+q)$$

である．他方，条件 $N(\mathrm{A}^{\char93 })\ge pq-(p+q)$ は

$$(q-2-m)p+(p-2-n)q\ge pq-(p+q)$$

である．ここで

$$\begin{eqnarray*} &&(q-2-m)p+(p-2-n)q\ge pq-(p+q)\\ &\iff&pq-mp-nq-p-q\ge 0\\ &\iff&pq-(p+q)\ge mp+nq \end{eqnarray*}$$

ゆえに2つの条件が同値であることが示され，題意が示された．

(4)

(3)から $N(\mathrm{A})=pq-(p+q)$ なら $N(\mathrm{A}^{\char93 })= pq-(p+q)$ となる．つまり等号が成立すると $N(\mathrm{A})=N(\mathrm{A}^{\char93 })$である． (1)から $\mathrm{A}=\mathrm{A}^{\char93 }$となるが，これは(2)の結果と矛盾する． ゆえに $N(\mathrm{A})\le pq-(p+q)$ で等号は成立しない．

$\mathrm{A}(m,\ n)$ のとき

$$(\mathrm{A}^{\char93 })^{\char93 }=(q-2-(q-2-m),\ p-2-(p-2-n))=(m,\ n)=\mathrm{A}$$

なので，$L$ の元 $\mathrm{A}$と $\mathrm{A}^{\char93 }$は1:1に対応する．(4)から $N(\mathrm{A})\le pq-(p+q)$となる$L$の元 $\mathrm{A}$の個数は $L$ の半分である．

$L$ は明らかに $(p-1)(q-1)$ 個からなるので，求める元の個数は

$$\dfrac{(p-1)(q-1)}{2}$$

注意     条件 $mp+nq\le pq-(p+q)$は書きかえると

$$\dfrac{m+1}{q}+\dfrac{n+1}{p}\le 1$$

である．

     (4)の解答中にあるように，直線 $\dfrac{x+1}{q}+\dfrac{y+1}{p}=1$上には格子点がないので，この直線が$L$の格子点を二分することがわかる．

     $\mathrm{A}$と $\mathrm{A}^{\char93 }$の対応は， この二分された二つの領域の中の格子点の一対一対応である．

解答 10 (問題10)   $x$ をひとつ固定する． $m=2x,\ n=-x$ は $x=3m+5n$ を満たす．

$x=3m+5n$ を満たす任意の解を $(m,\ n)$ とする．

$$\begin{eqnarray*} 3m+5n&=&x\\ 3(2x)+5(-x)&=&x \end{eqnarray*}$$

この辺々を引いて，

$$3(m-2x)+5(n+x)=0$$

3 と 5 は互いに素なので，ある整数 $t$ によってつぎのようにおけなければならない．

$$\begin{eqnarray*} m-2x&=&-5t\\ n+x&=&3t \end{eqnarray*}$$

つまり $x$ を表す $(m,\ n)$ は整数 $t$ によって次のように表される．

$$(m,\ n)=(2x-5t,\ -x+3t)$$

この $(m,\ n)$ が $x$ を表すことも明らかである．

$m=2x-5t \ge 0,\ n=-x+3t \ge 0$ なので

$$\dfrac{1}{3}x \le t \le \dfrac{2}{5}x$$

したがってこの範囲に整数 $t$ が存在することと， $x$ が非負整数 $m,\ n$ を用いて表わせることが同値である．

$$\dfrac{2}{5}x-\dfrac{1}{3}x \ge 1$$

つまり $x \ge 15$ なら必ず条件を満たす整数 $t$ がとれる．したがって

$$1 \le x \le 14$$

について調べればよい．

$$\begin{array}{lll\vert lll} x=1&0<\dfrac{1}{3}<\dfrac{2}... ...& x=14&\dfrac{14}{3}<5<\dfrac{28}{5}&あり \end{array}$$

したがって表せないものはつぎの四つである．

$$x=1,\ 2,\ 4,\ 7$$

$x$ を3で割った余りで分類して考える．

$$\left\{ \begin{array}{lll} x=3k&x=3\cdot k+5\cdot 0 よ... ... （m,\ n)=(k-1,\ 1)で表せる． \end{array} \right.$$

したがってのこるのは1，2，4，7    である．ところが
            $3m$ のとりうる値は0，3，6，9，…
            $5n$ のとりうる値は0，5，10，15，…
であるから，明らかに1，2，4，7は $3m+5n$ の形で表せない．

解答 11 (問題11)  

(1)

$$a(-ak)+(a^2+1)k=k\quad \cdots\maru{1}$$

であるから，格子点$(-ak,\ k)$は$L$上にある．

(2)

$(m,\ n)$を$L$上の任意の格子点とする．つまり

$$am+(a^2+1)n=k\quad \cdots\maru{2}$$

である． $\maru{2}-\maru{1}$をとる．

$$a(m+ak)+(a^2+1)(n-k)=0\quad \cdots\maru{3}$$

$a$の約数は$a^2$の約数であり，$a^2+1$の約数ではありえないので $a$と$a^2+1$は互いに素である．

したがって$\maru{3}$より$m+ak$は$a^2+1$の倍数である． 整数$t$を用いて$m+ak=(a^2+1)t$とおける．このとき$n-k=-at$となる．

つまり $L$ 上の格子点は整数 $t$ によって，

$$\left\{ \begin{array}{l} m=-ak+(a^2+1)t\\ n=k-at \end{array} \right.$$

と表される．逆にこのように表されるものが $L$ 上にあることは明らかである．

題意をみたす格子点が存在するのは，

$$\left\{ \begin{array}{l} m=-ak+(a^2+1)t>0\\ n=k-at>0 \end{array} \right.$$

をみたす $t$ が存在することと同値である．つまり

$$\dfrac{k}{a}>t>\dfrac{ak}{a^2+1}\quad \cdots\maru{4}$$

ここで $k=a(a^2+1)$ のとき$\maru{4}$は

$$a^2+1>t>a^2$$

となる．よって条件をみたす整数 $t$ が存在せず， 題意をみたす $L$ 上の格子点も存在しない．

(3)

$k>a(a^2+1)$のとき$\maru{4}$の左辺から右辺を引くと，

$$\dfrac{k}{a}-\dfrac{ak}{a^2+1}=\dfrac{k}{a(a^2+1)}>1$$

したがって条件をみたす $t$ がつねに存在し， 題意をみたす $L$ 上の格子点も存在する．

解答 12 (問題12)  

(1)

$a$ と $b$ が互いに素であるから， $\dfrac{b}{a}x,\ \dfrac{b}{a}x+1$ が整数となるのは $x$ が $a$ の倍数であるときにかぎる．直線OA，CBの方程式が $y=\dfrac{b}{a}x,\ y=\dfrac{b}{a}x+1$なので，$0<k<a$ の範囲の整数 $k$ に対し，直線 $x=k$ と直線 OA, CBの交点はいずれも格子点ではない．したがって, 直線 $x=k$ のOABCの内部にある部分には，ちょうど一つの格子点がある．よって$\mathrm{OABC}$の内部には$a-1$個の格子点がある．

(2)

OABCの内部の格子点を $\mathrm{P}_i(p_i,\ q_i)$ とおく.

$$\triangle\mathrm{OP}_iA=\dfrac{1}{2}\vert aq_i-bp_i\vert$$

である． $\mathrm{P}_i(p_i,\ q_i)$ は領域 $y>\dfrac{b}{a}x$ にあるので,

$$aq_i-bp_i\ge1$$

よって,

$$\triangle\mathrm{OP}_iA\ge\dfrac{1}{2}$$

である．ここで等号が成立する $i$ が存在することを示す.

まず， $\mathrm{P}_i(p_i,\ q_i)$ に対し，$aq_i-bp_i$ がすべて異なることを示す. $0<i,\ j<a$ に対して $aq_i-bp_i=aq_j-bp_j$ ならば,

$$a(q_i-q_j)=b(p_i-p_j)$$

となる．$a$ と $b$ が互いに素であるから，$p_i-p_j$ は $a$ の倍数である. ところが，$0<p_i,\ p_j<a$ より,

$$1-a<p_i-p_j<a-1$$

であるから，$a$ の倍数は $p_i-p_j=0$ 以外にないことがわかる. よって，$q_i=q_j$ も成り立ち， $\mathrm{P_{\it i}}=\mathrm{P_{\it j}}$ がわかる. したがって，集合 $\{aq_i-bp_i\}$ の元の個数は $a-1$ である.

一方,

$$\dfrac{b}{a}p_i< q_i< \dfrac{b}{a}p_i+1\quad \iff\quad 0<aq_i-bp_j<a$$

なので，集合 $\{aq_i-bp_i\}$ は集合 $\{1,\ 2,\ \cdots,\ a-1\}$ に含まれ， かつ元の個数が一致する．よって二つの集合は一致し，かならず $aq_i-bp_i=1$ となる番号 $i$ がある. したがって，求める最小値は,

$$\dfrac{1}{2}$$

参考
・等号成立の別証

$$J=\{aq-bp\vert(p,\ q)はすべての格子点\}$$

とする． $J$ の元で正で最小のものを $aq_0-bp_0$ とする.

任意の $J$ の元 $aq-bp$ を $aq_0-bp_0$ で割る.

$$aq-bp=(aq_0-bp_0)Q+r,\quad 0\le r<aq_0-bp_0$$

ここで,

$$r=a(q-q_0 Q)-b(p-p_0 Q)\in J$$

であるから，$aq_0-bp_0$ の最小性によって,

$$r=0$$

である．つまり $aq-bp$ は，$aq_0-bp_0$ の倍数である.
ところが

$$a=a\cdot1+b\cdot0\in J$$

同じく $b$ も $J$ の元であるから,

$$aq_0-bp_0\ は\ a\ と\ b\ の約数$$

となり，$a$ と $b$ が互いに素であるから,

$$aq_0-bp_0=1$$

この $(p_0,\ q_0)$ に対して整数 $n$ を用いて,

$$p_1=p_0+an,\quad q_1=q_0+bn$$

とおくと，$aq_1-bp_1=1$ であり，$n$ を適当にとると $0<p_1<a$ にできる.
このとき $q_1=\dfrac{b}{a}p_1+\dfrac{1}{a}$ より,

$$\dfrac{b}{a}p_1<q_1<\dfrac{b}{a}p_1+1$$

となるので，$(p_1,\ q_1)$ は, OABCの内部にある.

解答 13 (問題13)   傾きが $\dfrac{2}{5}$ である直線$2x-5y-u=0$を $l_u$ と表すことにする.

このとき， $l_u$ と格子点$(m,\ n)$との距離は,次の式で与えられる．

$$\dfrac{\vert 2m-5n-u\vert}{\sqrt{2^2+5^2}}\quad \cdots\maru{1}$$

$m,\ n$ が変化するとき， $2m-5n$ は任意の整数値をとりうる．実際，任意の整数 $k$ に対して

$$2\cdot3k-5\cdot k=k$$

が成り立つ． $u$ を整数部分と小数部分に分けて

$$u=k+\alpha\quad (k\ \ は整数,\ 0\le \alpha<1)$$

と書くことにする．したがって上に述べたことから $m,\ n$ が変化するとき，

$$\vert 2m-5n-u\vert\ge \mathrm{min}(\alpha,\ 1-\alpha)$$

ゆえに1は

$$\dfrac{\vert 2m-5n-u\vert}{\sqrt{2^2+5^2}}\ge\mathrm{min}\... ...ac{\alpha}{\sqrt{29}},\ \dfrac{1-\alpha}{\sqrt{29}}\right)$$

そしてこの等号が成立する $m,\ n$ が必ず存在する．したがって

$$r\ge \mathrm{min}\left(\dfrac{\alpha}{\sqrt{29}},\ \dfrac{1-\alpha}{\sqrt{29}}\right)$$

に円の半径をとれば，直線 $l_u$ は円のいずれかと共有点をもつ．

$u$ の値に関わらず共有点をもつためには $u$ を動かしたときの $\mathrm{min}\left(\dfrac{\alpha}{\sqrt{29}},\ \dfrac{1-\alpha}{\sqrt{29}}\right)$ の 最大値以上に $r$ をとればよい．

明らかに

$$\dfrac{1}{2}\ge \mathrm{min} \left(\dfrac{\alpha}{\sqrt{29}},\ \dfrac{1-\alpha}{\sqrt{29}}\right)$$

で等号は $\alpha=\dfrac{1}{2}$ のときである．

したがって

$$r \ge \dfrac{1}{2}\sqrt{29}$$

であれば， $u$ に関わらず直線 $l_u$ は円のいずれかと共有点をもつ．求める $r$ の最小値は

$$\dfrac{1}{2\sqrt{29}}$$

注意 9.2.2   論証の根幹に， $m,\ n$ が変化するとき， $2m-5n$ は任意の整数値をとりうる，事実がある．

解答 14 (問題14)  

(1)

集合 $A=\{f(k) \vert k は整数 \}$ とおく．明らかに $f(k)=f(n+k)$ である．

$$∴\quad A=\{f(k) \vert k =0,\ \cdots,\ n-1\}$$

さらに

$$f(n-k)=\left\vert \sin \frac{ 2 \pi (n-k)}{n} \right\vert =\left\vert- \sin \frac{ 2 \pi k}{n} \right\vert=f(k)$$

したがって

$$f(1)=(n-1),\ \cdots,\ f \left(\dfrac{n-1}{2} \right) =f \left(\dfrac{n+1}{2} \right)$$

であるから

$$A=\left\{f(k) \vert k =0,\ \cdots,\ \dfrac{n-1}{2}\right\}$$

次に $0,\ \cdots,\ \dfrac{n-1}{2}$で $k\ne l$ のとき

$$f(k)=f(l)$$

となるのは $\dfrac{ 2 \pi k}{n}+ \dfrac{ 2 \pi l}{n}=\pi$ のときのみ．
このとき

$$2(k+l)=n$$

となり， $n$ が奇数であることに反する． ゆえに $k=0,\ \cdots,\ \dfrac{n-1}{2}$ に対して $f(k)$ はすべて異なる．

$$∴\quad A は\dfrac{n+1}{2}個の元からなる．$$

(2)

集合

$$B= \{f(mk) \vert k は 0 \le k \le \displaystyle \frac{n-1}{2} なる整数 \}$$

とおく．定義から

$$B\subset A$$

である． ここで

$$\begin{eqnarray*} f(m(k+n))&=&f(mk+mn)=f(mk)\\ f(m(n-k))&=&\left\vert \sin ... ...&\quad =\left\vert- \sin \frac{ 2 \pi mk}{n} \right\vert=f(mk) \end{eqnarray*}$$

したがって集合 $A$ の考察と逆に考えて

$$B= \{f(mk) \vert k は 整数 \}$$

である．

$$A \subset B$$

を示す． $\mathrm{A}$ の任意の元 $f(k)$ に対して $f(k)=f(mk')$ となる $k'$ が存在すればよい．

$$\dfrac{2\pi k}{n}+2l\pi=\dfrac{2\pi mk'}{n}$$

となる $k'とl$ が存在すれば十分である（十分条件で成り立つ）． これは

$$mk'=nl+k$$

となる $k'$ と $l$ が存在することである． $n$ と $m$ は互いに素なので $mk-ml$ が $n$ の倍数になれば $k-l$ 自身が $n$ の倍数でなければならないので

$$m,\ m\cdot2,\ \cdots,\ m(n-1)$$

を $n$ で割った余りはすべて異なる．ゆえに必ず余りが $k$ になるものが存在する．

$$∴\quad A\subset B$$

となり

$$A=B$$

である．つまり集合として $A$ と $B$ は等しく $m$ によらず一定である．

注意 9.2.3   ここは演習問題7とは違うやり方で $A=B$ を示した． いずれも一次不定方程式の解の存在が基本的事実である．

解答 15 (問題15)  

(1)

$k$を整数とし$3x+2y=k$とおく． これを満たす$0$以上の整数解$(x,\ y)$の個数を $k=0,\ 1,\ \cdots,\ 2008$の$k$について加えればよい．

まず，$3x+2y=k$を満たすすべての整数の組を求める．

$$3k+2(-k)=k$$

より任意の整数解$(x,\ y)$に対して

$$3(x-k)+2(y+k)=0$$

2と3は互いに素なので，$x-k$は2の，$y+k$は3の倍数である． よって整数解$(x,\ y)$は整数$t$を用いて

$$x=k-2t,\ y=-k+3t$$

と表せ，この形をしたものはすべて整数解である．

$x\ge 0,\ y\ge 0$という条件は

$$\dfrac{k}{3}\le t \le \dfrac{k}{2}$$

と同値である． よって$k$に対しこの範囲にある整数$t$の個数が， $3x+2y=k$となる0以上の整数の組$(x,\ y)$の個数である． 負でない整数$m$を用いて$k$を場合に分け，個数を求める．

$$\begin{array}{lll} &t\ の範囲&t\ の個数\\ k=6m... ...rac{5}{3}\le t \le 3m+\frac{5}{2} &m+1個\\ \end{array}$$

一つの$m$に対し個数は$6m+5$個ある． $2008=6\cdot334+4$なので $m=0,\ 1,\ \cdots,\ 334$について$6m+5$を加え， 2009のときの個数 335 個を除けばよい．

$$\begin{eqnarray*} ∴\quad \sum_{m=0}^{334}(6m+5)-335 &=&6\cdot167\cdot335+5\cdot335-335\\ &=&(1002+4)\cdot335=337010\ (個) \end{eqnarray*}$$

(2)

不等式は$3x+2y+z\le 60$と同値である． $3x+2y=k$となる一組の$(x,\ y)$に対し， $z$は $0\le z\le 60-k$の範囲に$60-k+1$個とれる． 組$(x,\ y)$の個数に$z$の個数を乗じたものが， $3x+2y=k$かつ$3x+2y+z\le 60$となる整数の組 $(x,\ y,\ z)$の個数である．

$$\begin{array}{ll} k=6mのとき&(m+1)(60-6m+1)個\\ k... ...)個\\ k=6m+5のとき&(m+1)(60-6m-4)個\\ \end{array}$$

これを加える．

$$(m+1)(300-30m-9)+m(60-6m)=-36m^2+321m+291$$

$m=0,\ \cdots,\ 9$についてこれを加え， $3x+2y=60$とき(このとき$z$は0のみ)の$11$個を加える．

$$\begin{eqnarray*} ∴\quad \sum_{m=0}^9(-36m^2+321m+291)+11 &=&-6\cdot9\cdot... ...ot19 +321\cdot45+2910+11\\ &=&-10260+14445+2921=7106\ (個) \end{eqnarray*}$$

解答 16 (問題16)  

(1)

$$\begin{array}{lll} f(k)=1となるkは& \left[\dfrac{50}... ...るkは& \left[\dfrac{50}{2^5} \right]&=1\ 個 \end{array}$$

ゆえに

$$S_{50}=1\cdot(25-12)+2\cdot(12-6)+3\cdot(6-3)+4\cdot(3-1)+5\cdot1=47$$

(2)

$n=2^l$ とする．(1)と同様に

$$\begin{eqnarray*} S_n&=&1\cdot \left( \left[\dfrac{2^l}{2} \right] - \left[\... ...right]\\ &=&2^{l-1}+2^{l-2}+\cdots+1=\dfrac{2^l-1}{2-1}=n-1 \end{eqnarray*}$$

(3)

$2^l \le n <2^{l+1}$ とする．

$$\begin{eqnarray*} S_n&=&1\cdot \left( \left[\dfrac{n}{2} \right] - \left[\df... ...-\dfrac{1}{2}} <\dfrac{n}{2}\cdot\dfrac{1}{1-\dfrac{1}{2}}=n \end{eqnarray*}$$

次に

$$\begin{eqnarray*} S_n&\ge&S_{2^l}=2^l-1\\ &&(\ 2^{l+1}\ge n+1\quad なので)\\ &\ge&\dfrac{n+1}{2}-1=\dfrac{n-1}{2} \end{eqnarray*}$$

以上から

$$\dfrac{n-1}{2}\le S_n<n$$

解答 17 (問題17)  

(1)

（イ）⇒（ロ）を示す．

$60=2^2\cdot 3 \cdot5$であるから $n$ が60の倍数なら

$$a_1=1,\ a_2=2,\ 3_3=3,\ a_4=4,\ a_5=5,\ a_6=6 \cdots$$

である．

$$∴\quad \dfrac{1}{a_3}+\dfrac{1}{a_6} =\dfrac{1}{3}+\dfrac{1}{6} =\dfrac{1}{2}=\dfrac{1}{a_2}$$

(2)

（ロ）⇒（イ）を示す．

条件式から $a_2a_3+a_2a_6=a_3a_6$である．これを変形すると，

$$(a_3-a_2)(a_6-a_2)=a_2^2$$

$a_2$は必ず素数だから， $a_2=p$ とおくと， $a_3<a_6$ より

$$a_3-a_2=1,\ a_6-a_2=p^2\quad ∴\quad a_3=p+1,\ a_6=p^2+p$$

$a_3$ としてあり得るのは

$$a_3=p^2,\ または，pと異なる素数$$

$p^2=p+1$は整数解がない．よって $p$ と異なる素数．
$p$ と $p+1$ がともに素数になるのは $p=2$ のみ．このとき，

$$a_2=2,\ a_3=3,\ a_6=6$$

なので， $a_4=4,\ a_5=5$ 以外にない． よって $n$ は少なくとも $3,\ 4,\ 5$ を因数にもつ．つまり60の倍数である．

解答 18 (問題18)  

(1)

$81=3^4$ であるから，正の約数の和は

$$1+3+3^2+3^3+3^4=\dfrac{3^5-1}{3-1}=121$$

(2)

$378=2 \times 3^3 \times 7$ であるから約数の個数は

$$2 \times 4 \times 2=16$$

それらの和は

$$(1+2)(1+3+3^2+3^3)(1+7)=960$$

(3)

$N$ の素因数分解の素数 $p$ の部分が $p^n$ であるとする．このとき和には

$$1+p+\cdots +p^n=\dfrac{p^{n+1}-1}{p-1}\cdots \maru{1}$$

が現れる．60の約数は

$$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 10,\ 12,\ 15,\ 20,\ 30,\ 60$$

である．このなかで1の形をしているものを調べる．

(i)

$3=1+2$ このとき $60=3 \cdot 20$ とすると， $20=1+19$ ．

$$∴\quad N=2 \cdot 19=38$$

(ii)

$3=1+2$ このとき $60=3 \cdot 4 \cdot 5$ とすると， $5$は1の形をしていない．

(iii)

$4=1+3$ このとき $60=4 \cdot 15$ ． $15=1+2+2^2+2^3$ ．

$$∴\quad N=3 \cdot 2^3=24$$

(iv)

$6=1+5$ このとき $60=6 \cdot 10$．$10$は1の形をしていない．

(v)

$12=1+11$ このとき $60=12 \cdot 5$．$5$は1の形をしていない．

(vi)

$30=1+29$ このとき $60=30 \cdot 2$．$2$は1の形をしていない．

(vii)

$60=1+59$

$$∴\quad N=60$$

題意を満たす $N$ は $24,\ 38,\ 60$ の3個ある． そのうち2と3でできているのは $24$ ．

解答 19 (問題19)  

(1)

$$b(p^2+q^2)=apq\quad \cdots \maru{1}$$

左辺は $b$ の倍数． $a$ と $b$ が互いに素なので $pq$ は $b$ の倍数である．

(2)

$p$ と $q$ の最大公約数を $g$ とし，

$$p=gp',\ q=gq',\ (p'とq'は互いに素)$$

とおく．このとき$\maru{1}$は

$$bg^2({p'}^2+{q'}^2)=ag^2p'q'$$

となる．つまり

$$b({p'}^2+{q'}^2)=ap'q'\quad \cdots \maru{2}$$

(1)と同様に $p'q'$ が $b$ の倍数になる．$p'q'=bk$ とおく．このとき $\maru{2}$から

$${p'}^2+{q'}^2=ak$$

ここで $k\ne 1$ なら

$$\begin{eqnarray*} &&{p'}^2+{q'}^2とp'q'が互いに素でない\\ &\iff&{p... ...いに素でない\\ &\iff&p'とq'が互いに素でない \end{eqnarray*}$$

ゆえに $k=1$ となり， $b=p'q'$ ， $a={p'}^2+{q'}^2$ ．つまり

$$\sqrt{a+2b}=p'+q'．$$

これは自然数である．

解答 20 (問題20)  

(1)

$a$が奇数のとき，$b$も奇数と仮定する． このとき$c$は偶数である．

$$a=2k+1，b=2l+1,\ c=2m$$

とおく．

$$a^2+b^2=4(k^2+k+l^2+l)+2,\ c^2=4m^2$$

となり，4で割った余りが異なる．つまり$a^2+b^2=c^2$が成り立ち得ない．

ゆえに$b$は偶数であり，$c$は奇数である．

(2)

$a^2+b^2=c^2$より $b^2=(c-a)(c+a)$となるが(1)から$c-a,\ c+a$ はともに偶数である．

$$\left(\dfrac{b}{2} \right)^2=\dfrac{c-a}{2}\cdot\dfrac{c+a}{2}$$

ここで $\dfrac{c+a}{2}>\dfrac{c-a}{2}\ge 1$なので， $p$を$\dfrac{b}{2}$の素因数の一つとすると$p>1$．

$\dfrac{c-a}{2}$と $\dfrac{c+a}{2}$がともに$p$を因数に持てば

$$\dfrac{c-a}{2}=kp,\ \dfrac{c+a}{2}=lp$$

とおくと

$$c=(k+l)p,\ a=(l-k)p$$

となり$p$が$a$と$b$の公約数となる．$a$と$b$は互いに素で， $p>1$であるから，$p$は $\dfrac{c-a}{2}$と $\dfrac{c+a}{2}$のいずれか一方 のみの素因数となる．

$\left(\dfrac{b}{2} \right)^2$の最高べき指数は偶数であるから $\dfrac{c-a}{2}$と $\dfrac{c+a}{2}$のいずれもが平方数となる．

つまり

$$\dfrac{a+c}{2}=d^2$$

となる自然数$d$が存在する．

解答 21 (問題21)  

(1)

$b$ の約数を $b_i\ (i=1,\ 2,\ \cdots,\ l)$とする． 2と$b$は互いに素なので$a=2^mb$の約数のすべては，

$$2^jb_i\ \ (j=0,\ 1,\ \cdots,\ m,\ i=1,\ 2,\ \cdots,\ l)$$

で与えられる．

$$\begin{eqnarray*} ∴ \quad f(a)&=&\sum_{j=0,\ i=1}^{j=m,\ i=l}2^jb_i =\sum_... ...=0}^m2^j\right)f(b)=\dfrac{2^{m+1}-1}{2-1}f(b)=(2^{m+1}-1)f(b) \end{eqnarray*}$$

(2)

$p$ が2以上の整数なので$pq\ne q$である．したがって $q$ と $pq$ は $a=pq$ の異なる約数である．

$$∴ \quad f(a)\ge (p+1)q$$

等号が成り立つのは，$a=pq$の約数が $q$ と $a$ のみのときである． 1とその数自身は必ず約数になるので$q=1$で， かつ1とその数自身以外の約数がないので$p$は素数でなければならない．

(3)

(1)から

$$\left\{ \begin{array}{l} f(a)=(2^{m+1}-1)f(r)=2b=2^{n+... ...(s)=2a=2^{m+1}r \end{array} \right. \quad \cdots\maru{1}$$

ここで，$2^{m+1}-1$と$2^{n+1}$は互いに素なので， $s$ は$2^{m+1}-1$を約数にもつ． $r$ についも同様．

$$s=(2^{m+1}-1)s',\ \quad r=(2^{n+1}-1)r'$$

とおける．このとき$\maru{1}$から

$$f(r)=2^{n+1}s',\ \quad f(s)=2^{m+1}r'\quad \cdots\maru{2}$$

一方(2)から

$$f(r)\ge\{(2^{n+1}-1)+1\}r'=2^{n+1}r',\ \quad f(s)\ge\{(2^{m+1}-1)+1\}s'=2^{m+1}s'\quad \cdots\maru{3}$$

である．

$$2^{n+1}s'\ge2^{n+1}r' \quad かつ \quad 2^{m+1}r'\ge 2^{m+1}s'$$

より $r'=s'$ で3が等号になる．

(2)より$r'=s'=1$なので2から

$$r=2^{n+1}-1,\ \quad s=2^{m+1}-1$$

解答 22 (問題22)  

$$\begin{eqnarray*} 3^{n+1}+4^{2n-1}&=&9\cdot3^{n-1}+4\cdot16^{n-1}\\ &=&9\cd... ...n-1}\,(\bmod.\ 13)\\ &=&13\cdot3^{n-1}\equiv 0\,(\bmod.\ 13) \end{eqnarray*}$$

解答 23 (問題23)  

$$\begin{eqnarray*} 19^n+(-1)^{n-1}2^{4n-3}&=&19^n+2\cdot(-16)^{n-1}\\ &=&(14... ...\\ &\equiv &5\cdot5^{n-1}+2\cdot5^{n-1}\equiv 0\,(\bmod.\ 7) \end{eqnarray*}$$

解答 24 (問題24)  

(1)

$\alpha=\dfrac{p}{q}$ とする．ここで $p,\ q$ は互いに素とする．

$$f\left(\dfrac{p}{q}\right) =\left(\dfrac{p}{q}\right)^n+... ...ight)^{n-1} +\cdots a_{n-1}\left(\dfrac{p}{q}\right)+a_n=0$$

$$∴\quad p^n=-(a_1p^{n-1}q +\cdots a_{n-1}pq^{n-1}+a_nq^n)$$

右辺は $q$ の倍数で $q$ は $p$ と互いに素なので$q=1$ ．

つまり$\alpha$ は整数である．

(2)

背理法でしめす．

方程式 $f(x)=0$ が有理数の解をもてば(1)からそれは整数である．

$\alpha$ を $k$ で割って

$$\alpha=q\cdot k+r$$

とおく． $0\le r<k$ である．

$$0=f(\alpha)=f(q\cdot k+r)\equiv f(r)\,(\bmod.\ k)$$

ゆえに$k$ 個の整数 $f(0),\ f(1),\ \cdots,\ f(k-1)$のどれかが $k$ で割り切れる．

さらに

$$f(k)\equiv f(0)\,(\bmod.\ k)$$

であるから $k$ 個の整数 $f(1),\ f(2),\ \cdots,\ f(k)$のどれかが $k$ で割り切れなければならない．

これは条件と矛盾するので，題意が示された．

解答 25 (問題25)  

解1      $n^9-n^3=n^2(n^7-n)$ なので $n$ が3の倍数なら明らかに9の倍数である．

3の倍数でないときに示す．$n=3k\pm 1$とおく．

$$\begin{eqnarray*} n^9-n^3&=&(3k\pm 1)^3\{(3k\pm 1)^6-1\}\\ &=&(27k^3\pm27k^... ...\bmod.\ 9)\\ &=&(\pm1)(18k^2\pm 9k+1-1)\equiv 0\,(\bmod.\ 9) \end{eqnarray*}$$

ゆえに $n^9-n^3$ は9で割り切れる．

解2     

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

$n$が3の倍数なら$n^3$が9の倍数， $n$が3で割って1余る数なら $(n-1)\{(n-1)^2+3n\}$が9の倍数， $n$が3で割って2余る数なら $(n+1)\{(n+1)^2+3n\}$が9の倍数となり， つねに3の倍数である．

解答 26 (問題26)  

1. 1. $gcd(N,\ n)\ne 1$となるものは，$p$または$q$の倍数である． したがって$N$より小さい自然数$n$では
      
      $$\begin{array}{l} p,\ 2p,\ 3p,\ \cdots,\ (q-1)p\\ q,\ 2q,\ 3q,\ \cdots,\ (p-1)q \end{array}$$
      
      
      である．
   2. $1\le n<N$の範囲で $gcd(N,\ n)\ne 1$となるものが(i)より
      
      $$(q-1)+(p-1)\ 個$$
      
      
      ある．同じ範囲で$gcd(N,\ n)=1$となるものはそれらを除いたものである．
      
      $$∴\quad \phi(N)=pq-1-(q-1)-(p-1)=(p-1)(q-1)$$
      
      

2. $N=pq$なので(ii)から
   
   $$\phi(N)=N-(p+q)+1$$
   
   
   つまり，
   
   $$p+q=N+1-\phi(N),\ pq=N$$
   
   
   よって， $p$と$q$を解としてもつ二次方程式は未知数を$x$とすれば次のようになる．
   
   $$x^2-\{N+1-\phi(N)\}x+N=0$$
   
   

3. 
   
   $$N+1-\phi(N)=18426=2\cdot 9213$$
   
   
   である．よって
   
   $$p,\ q=9213\pm\sqrt{9213^2-84754668}=9213\pm\sqrt{106276}=9539,\ 8887$$
   
   

解答 27 (問題27)  

(1)

$$\begin{eqnarray*} &&\alpha^n=\alpha^m \\ &\iff&\dfrac{n\pi}{3}=\dfrac{m\pi}... ...る整\ k\ が存在する\\ &\iff&n\equiv m\,(\bmod.\ 6) \end{eqnarray*}$$

である．ゆえに6個．

(2)

$n$ が6と互いに素なら $1\le i,\ j\le 5$ に対して

$$ni\equiv nj\,(\bmod.\ 6)\ \iff \ i\equiv j\,(\bmod.\ 6)$$

である．ゆえに

$$\{\alpha^n,\ \alpha^{2n},\ \alpha^{3n},\ \alpha^{4n},\ \al... ...\} =\{\alpha,\ \alpha^2,\ \alpha^3,\ \alpha^4,\ \alpha^5\}$$

となる．

一方 $n\equiv 2,\ 4\,(\bmod.\ 6)$ のときは $\alpha^{3n}=1$ ， $n\equiv 3\,(\bmod.\ 6)$ のときは $\alpha^{2n}=1$である．

$$∴\quad 与式=\left\{ \begin{array}{ll} 1&n\equiv 1,... ... 0,\ 2,\ 3,\ 4(\bmod.\ 6)\ のとき \end{array} \right.$$

解答 28 (問題28)  

(1)

条件(イ)より $z_k$ は1と異なる1の $p$ 乗根である．

$$\alpha=\cos\dfrac{2\pi}{p}+i\sin\dfrac{2\pi}{p}$$

とおくと， 1と異なる1の $p$ 乗根は

$$z_k=\alpha^{x_k},\ x_k \ は\ 1\le x_k \le p-1 \ の範囲の整数$$

一意に表される． このとき条件(ロ)は

$$x_1+x_2+\cdots+x_n=(p\ の倍数)\quad \cdots \maru{1}$$

となる．$a_n$ は$\maru{1}$の解

$$(x_1,\ x_2,\ \cdots,\ x_n)\ ,\ 1\le x_1,\ x_2,\ \cdots,\ x_n \le p-1$$

の個数を表す．

$$x_n=(pの倍数)-(x_1+x_2+\cdots+x_{n-1})$$

であるから， $(x_1,\ x_2,\ \cdots,\ x_{n-1})$ を $(x_1+x_2+\cdots+x_{n-1})$ が $p$ の倍数でないようにさえ選べば，一組の解が得られる．

$$∴\quad a_n=(p-1)^{n-1}-a_{n-1}\ (n\ge 3)$$

ここで $a_2$ を求める． $a_2$ は$x_1+x_2$ がpの倍数となる

$$(x_1,\ x_2)=(1,\ p-1),\ (2,\ p-2),\ \cdots ,\ (p-1,\ 1)$$

$p-1$ 個である．

$$a_2=(p-1)$$

$$∴\quad a_3=(p-1)^2-(p-1)=(p-1)(p-2)$$

(2)

(1)から

$$a_{n+2}=(p-1)^{n+1}-a_{n+1}$$

(3)

$$a_{n+1}=(p-1)^n-a_n$$

を解く． $p-1\ne 0$ なので

$$\begin{eqnarray*} &&\dfrac{a_{n+1}}{(p-1)^{n+1}} =-\dfrac{1}{p-1}\cdot\dfrac... ...ght)^{n-2} \left\{ \dfrac{a_2}{(p-1)^2}+\dfrac{1}{p}\right\} \end{eqnarray*}$$

これから

$$a_n=\dfrac{p-1}{p}\{(p-1)^{n-1}-(-1)^{n-1}\}$$

［漸化式の別解］

$$x_1+x_2+\cdots+x_n+x_{n+1}+x_{n+2}=(p\ の倍数)$$

の解を二つに分類する．

(i)

$x_{n+1}+x_{n+2}$ がpの倍数のとき．この $(x_{n+1},\ x_{n+2})$ は $a_2=p-1$ 個あり，その各に対し結局

$$x_1+x_2+\cdots+x_n=(p\ の倍数)-(x_{n+1}+x_{n+2})=(p\ の倍数)$$

となる．この場合の個数は

$$(p-1)a_n$$

(ii)

$x_{n+1}+x_{n+2}$ がpの倍数でないとき． $y_{n+1}=x_{n+1}+x_{n+2}$ とおくと

$$x_1+x_2+\cdots+x_n+y_{n+1}=(p\ の倍数)$$

の解は $a_{n+1}$ 個あり．各 $y_{n+1}$ に対して $y_{n+1}=x_{n+1}+x_{n+2}+(pの倍数)$ となる $(x_{n+1},\ x_{n+2})$ は $p-1$ 組ある．

なぜなら $x_{n+1}$ は$y_{n+1}$ と同じにはとれない(同じにとると$x_{n+2}$がとれない)が，逆に異なれば $y_{n+1}-x_{n+1}$と $p$ で割ったの余りが等しい$x_{n+2}$が一つ定まる．

この場合の個数は

$$(p-2)a_{n+1}$$

$$∴\quad a_{n+2}=(p-2)a_{n+1}+(p-1)a_n$$

解答 29 (問題29)  

(1)

$\alpha=\cos\dfrac{2\pi}{n}+i\sin\dfrac{2\pi}{n}$ とおく．

$$G=\{1,\ \alpha,\ \alpha^2,\ \cdots,\ \alpha^{n-1}\}$$

とする．この元はすべて異なり $n$ 次方程式 $x^n-1=0$ の $n$ 個の解の全体である．

$G$ の任意の2つの元 $\alpha^i,\ \alpha^j\ (0\le i,\ j\le n-1)$ に対して $\alpha^{i+j}$ も明らかに $x^n-1=0$ の解なので，再び $G$ の元である．

よって $G$ は題意を満たすちょうど $n$ 個の複素数からなる集合である．

(2)

$G$ の元 $z$ に対し， そのべき $z,\ z^2,\ z^3,\ \cdots$ もすべて $G$ の元である． $z\in G$ とし $z=r(\cos \theta+i\sin \theta)$ とする．

$$z,\ z^2,\ z^3,\ \cdots$$

が有限集合なので，すべてが異なることはありえない．ゆえに

$$z^i=z^j\ (i < j)$$

となる $i,\ j$ がある．両辺の絶対値をとり

$$r^i=r^j \quad ∴ \quad r=1$$

かつ

$$z^{j-i}=1$$

したがって $G$ の元はすべて１のべき根である．

$z\in G$ で $z^m=1$ なら $z^{-1}=z^{m-1}$なので$z^{-1}\in G$ である．つまり $z,\ w \in G$ なら $z^{-1}w \in G$ である．

$G$ の元 $z$ の偏角 $\arg z$ は $0 \le \arg z <2\pi$ でとるとする．

$G$ の元で偏角が正で最小であるものを $\alpha$ とする． $G$ の任意の元 $z$ をとる．

$$m \arg \alpha \le \arg z < (m+1)\arg \alpha$$

となる正整数 $m$ がある．

このとき $z\alpha^{-m}\in G$ であるが

$$0\le \arg(z\alpha^{-m})<\arg \alpha$$

となる．

もし $0\ne \arg(z\alpha^{-m})$なら偏角が正で $\arg \alpha$ の偏角より小さい 元 $z\alpha^{-m}$ が存在し，$G$ の元で偏角が正で最小であるものを $\alpha$ としたことと矛盾する．

ゆえに $0=\arg(z\alpha^{-m})$．つまり $z=\alpha^m$

ゆえに $G$ の元はすべて $\alpha$ のべきである． $\alpha$ のべきで初めて1になるものを $\alpha^m(=1)$ とすれば

$$G=\{\alpha,\ \alpha^2,\ \cdots,\ \alpha^{m-1},\ \alpha^m \}$$

となる．ゆえに $m=n$ で $G$ は(1)で作った例と一致した．

解答 30 (問題30)  

(1)

$$r{}_p\mathrm{C}_r=\dfrac{rp!}{r!(p-r)!}=\dfrac{p(p-1)!}{(r-1)!\{(p-1)-(r-1)\}!} =p{}_{p-1}\mathrm{C}_{r-1}$$

上の等式の右辺は $p$ の倍数であるが, $r$ と $p$ は互いに素なので ${}_p\mathrm{C}_r$ が $p$ の倍数である.

(2)

$$2^p=(1+1)^p=1+\sum_{r=1}^{p-1}{}_p\mathrm{C}_r+1$$

(1)より $2^p-2$ は$p$の倍数である．よって余りは$2\ (p>2)$，$0(p=2)$である．

(3)

$n^p-n$ が $p$ の倍数であると推測される. これを, 数学的帰納法で示す.

(i)

$n=1$ は明らか. $n=2$ のときは(2)より成立

(ii)

$n=k$ のとき成立するとする. つまり

$$k^p-k=pMと整数Mを用いて表される.$$

このとき

$$(1+k)^p=1+\sum_{r=1}^{p-1}{}_p\mathrm{C}_rk^r+k^p =1+\sum_{r=1}^{p-1}{}_p\mathrm{C}_rk^r+pM+k$$

ここで, $$\sum_{r=1}^{p-1}{}_p\mathrm{C}_rk^r$$ は $p$ の倍数なのでこれを整数 $N$ を用いて $pN$ とおく.

$$\begin{array}{c} (1+k)^p=1+pN+k\\ ∴\quad (k+1)^p-(k+1)=pN \end{array}$$

よって, $n=k+1$ のときも成立した.

(iii)

したがって, すべての自然数 $n$ に対して, $n^p$ と $n$ を $p$ で割った余りは等しい.

つまり, $n^p$ を $p$ で割った余りは $n$ を $p$ で割った余りである．

解答 31 (問題31)  

(1)

自然数 $m,\ n$ を7で割った商をそれぞれ $m',\ n'$, 余りをそれぞれ $i,\ j$ とおくと, $m=7m'+i,\ n=7n'+j$ と書けて

$$mn=(7m'+i)(7n'+j)=7(7m'n'+m'j+n'i)+ij$$

より, $f(mn)=f(ij)$ を得る. そこで, これを用いて, 自然数 $n$ を7で割った余りで分類し, $n^2,\ n^3,\ \cdots,\ n^7$ を7で割った余りを順に求めていくと, 下表のようになる.

$$\begin{array}{\vert c\vert\vert c\vert c\vert c\vert c\ver... ...ine n^7 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \end{array}$$

よって, すべての自然数 $n$ に対して

$$f(n^7)=f(n)$$

注意 9.2.4        これは言うまでもなく「フェルマの小定理」そのものである．文系入試問題であるので，実際に7で割った余りの表を作ることで論証した．

他の演習問題にあるように，$n^7-n$ が7の倍数になることを$n$ に関する数学的帰納法で示すことができる．

(2)

(1)の結果より, すべての自然数 $k$ に対して, $k^7-k$ は7の倍数であるから

$$\sum_{k=1}^7 k^{n+6}-\sum_{k=1}^7 k^n= \sum_{k=1}^7 k^{n-1}(k^7-k)=7l\quad (l\ は自然数)$$

$$∴\quad g(n+6)=g(n)$$

よって, $1\le n\le6$ の範囲で考えれば十分である. ここで, (1)の表を利用すると

$$\begin{eqnarray*} &&g(1)=3f(1+2+3+4+5+6+0)=3f(21)=0\\ &&g(2)=3f(1+4+2+2+4+1+0... ...f(1+4+5+2+3+6+0)=3f(21)=0\\ &&g(6)=3f(1+1+1+1+1+1+0)=3f(6)=18 \end{eqnarray*}$$

となるから, $n=6$ をとれば

$$g(6)=18$$

解答 32 (問題32)  

1. $x\le y \le z$ として良い．(2)で示されるように $n$ が8で割ったときの余りが7なら $x^2+y^2+z^2=n$ を満たす整数の組 $(x,\ y,\ z)$ は存在しないので， 他にあるか注意して表を作る．
   
   $$\begin{array}{r\vert r\vert r\vert r\vert\vert r\vert r\ve... ...2&5&30\\ -&-&-&7&-&-&-&15&-&-&-&23&-&-&-&31 \end{array}$$
   
   
   $3^2+3^2+3^2=27$なので$28$を作るためには$4$以上が入らねばならない． ところが $1^2+3^2+4^2=26$, $2^2+3^2+4^2=29$なので，4まででは出来ない． 一方， $1^2+1^2+5^2=27$, $1^2+2^2+5^2=30$なので，5を入れても不可能．

   ゆえに$28$は表せない． $x^2+y^2+z^2=n$ を満たす整数の組 $(x,\ y,\ z)$ が存在しないような 正の整数 $n$ は小さいものから順に
   

   $$7,\ 15,\ 23,\ 28,\ 31$$
   
   

2. 
   
   $$3^2\equiv 1 ,\ 4^2\equiv 0,\ 5^2\equiv 1,\ 6^2\equiv 4 ,\ 7^2\equiv 1\quad (\bmod.\ 8)$$
   
   
   従って整数 $x$ に対して $x^2$ を8で割った余りは$0,\ 1,\ 4$のみ．

   $x^2+y^2+z^2$が8で割って7余るのは $x^2,\ y^2,\ z^2$ 中に奇数か奇数個なければならない． その組合せは
   

   $$(0,\ 0,\ 1),\ (1,\ 1,\ 1),\ (0,\ 1,\ 4),\ (1,\ 4,\ 4)$$
   
   
   だが，これらに対する$x^2+y^2+z^2$はおのおの $8$を法として$1,\ 3,\ 1,\$ となって$7$が現れない．

   したがって「正の整数 $n$ を8で割ったときの余りが7ならば， $x^2+y^2+z^2=n$ を満たす整数の組 $(x,\ y,\ z)$ が存在しない」というのは， つねに正しい．

注意 9.2.5   本問の(2)は正整数$n$が3個の平方数の和とならないための十分条件を与えている． しかし(1)の28が示すように，これは必要条件ではない．

では正整数$n$が3個の平方数の和とならないための必要十分条件は何か． 実はそれもガウスが解決している．

$n$が正整数$a$と$b$で$4^a(8b-1)$と表されること

これが$n=x^2+y^2+z^2$となる正整数$x,\ y,\ z$が存在しないための必要十分条件である．

『数論講義』(J.P,Serre)に載っている．

解答 33 (問題33)       

(1)

$2x^3+5x^2-3x+7=(x-3)(2x^2+11x+30)+97$ である．

$$∴\quad Q(x)=2x^2+11x+30,\ \quad r-97$$

(2)

(i)

$F(x)$ を $x$ の $n$ 次の整式とし， $x^n$ の係数が $a_n$ であるとする．
ここで，

$$Q_1(x)=a_nx^{n-1},\ F_1(x)=F(x)-G(x)Q_1(x)$$

とおく．

$$G(x)Q_1(x)=(x-a)\cdot a_nx^{n-1}=a_nx^n-aa_nx^{n-1}$$

であるから $F_1(x)$の次数は $n-1$ 以下であり，明らかに題意を満たす．

(ii)

一次式，つまり$F(x)=px+q$のときは $Q(x)=p,\ r=ap+q$ とおけばよい．

$1〜n-1$ 次式のとき成立するとする．

$n$ 次式 $F(x)$ に対して

$$F(x)=G(x)Q(x)+F_1(x)$$

を満たす $x$ の整式 $Q_1(x), \ F_1(x),$ ただし $F_1(x)$ の次数は $F(x)$ の次数より小さい，が存在する．
帰納法の仮定から

$$F_1(x) =G(x)Q_1(x)+r$$

となる $Q_1(x)$ と $r$ が存在する．したがって，

$$F(x)=G(x)Q(x)+F_1(x) =G(x)Q(x)+G(x)Q_1(x)+r=G(x)\{Q(x)+Q_1(x)\}+r$$

$Q(x)+Q_1(x)$ を改めて $Q(x)$ に取り直せば， $n$ のときも題意が成立する ことがわかる．

したがって，任意の自然数 $n$ に対して題意が示された．

(3)

$$F(x)=(x-a)Q(x)+r$$

となる $Q(x)$ と $r$ が存在する．この等式に $x=a$ を代入する． $F(a)=r$ が得られる． $F(a)=0$ より $r=0$ ．したがって題意は示された．

(4)

方程式 $F(x)=0$ の相異なる実数解を $\alpha_1,\ \cdots,\ \alpha_j$ とする．

$F(\alpha_1)=0$ より

$$F(x)=(x-\alpha_1)Q_1(x)$$

とおける． $F(\alpha_2)=0$ で $\alpha_2-\alpha_1\ne 0$ より$Q(\alpha_2)=0$．

$$∴\quad Q_1(x)=(x-\alpha_2)Q_2(x)$$

とおける．つまり

$$F(x)=(x-\alpha_1)(x-\alpha_2)Q_2(x)$$

これを繰りかえすと，

$$F(x)=(x-\alpha_1)\cdots (x-\alpha_j)Q_j(x)$$

となる整式 $Q_j(x)$ がある．

もし $j>n$ なら右辺の次数は左辺の次数 $n$ より大きくなり不合理． よって $j\le n$ ．つまり題意が示せた．

解答 34 (問題34)       

(1)

$p(x)=1$とすれば$f(x)=f(x)p(x)$となるので， 整式$f(x)$は$f(x)$の約数である．

(2)

0と異なる整式$f(x)$が整式$g(x)$なので，(1)から $f(x)$は$f(x)$，$g(x)$の公約数である． $f(x)$の約数の次数は$f(x)$の次数以下であるから， $f(x)$は$f(x)$と$g(x)$の公約数のなかで次数最大である． つまり$f(x)$は$f(x)$，$g(x)$の最大公約数である．

(3)

整式$g(x)$を$f(x)$で割った商を$q(x)$とすると，

$$g(x)=f(x)q(x)+r(x)$$

である．整式$d(x)$が$r(x),\ f(x)$の公約数なので，$d(x)$は $g(x)$の約数ともなり，$d(x)$は$f(x)$，$g(x)$の公約数でもある．

ここで$f(x)$，$g(x)$の最大公約数を$D(x)$とすると，

$$d(x)の次数\le D(x)の次数$$

つぎに

$$r(x)=g(x)-f(x)q(x)$$

より$D(x)$は$r(x)$の約数にもなり，$D(x)$は$r(x),\ f(x)$の公約数となる． この結果

$$D(x)の次数\le d(x)の次数$$

あわせて

$$D(x)の次数=d(x)の次数$$

となり，$d(x)$が$f(x)$，$g(x)$の最大公約数でもあることが示された．

解答 35 (問題35)        解1      $(x+1)^3$を$x-1$で割って

$$(x+1)^3=(x-1)(x^2+4x+7)+8$$

これから

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

となる． $p(x)f(x)+q(x)g(x)=1$と辺々引いて

$$(x-1)\left\{p(x)+\dfrac{1}{8}x^2+\dfrac{1}{2}x+\dfrac{7}{8} \right\} +(x+1)^3\left\{q(x)- \dfrac{1}{8}\right\}=0$$

$x-1$と$(x+1)^3$は互いに素なので，ある整式$T(x)$を用いて

$$\begin{array}{l} p(x)+\dfrac{1}{8}x^2+\dfrac{1}{2}x+\dfr... ...=(x+1)^3T(x)\\ q(x)- \dfrac{1}{8}=-(x-1)T(x) \end{array}$$

と表され，またこの形のものは与式を満たす．ゆえに任意の解は

$$\begin{array}{l} p(x)=-\dfrac{1}{8}x^2-\dfrac{1}{2}x-\df... ...)T(x) \end{array} ,\ \left(T(x) は任意の整式\right)$$

と表される．

次数最小のものは$T(x)=0$のときである．

$$\begin{array}{l} p(x)=-\dfrac{1}{8}x^2-\dfrac{1}{2}x-\dfrac{7}{8}\\ q(x)=\dfrac{1}{8} \end{array}$$

である．最高次数の係数が1で次数最小のものは$T(x)=1$のときだから

$$\begin{array}{l} p(x)=x^3+\dfrac{23}{8}x^2+\dfrac{5}{2}x+\dfrac{1}{8}\\ q(x)=-x+\dfrac{7}{8} \end{array}$$

である．

解2      与式に$x=1,\ x=-1$を代入して

$$q(1)(1+1)^3=1,\ p(-1)(-1-1)=1$$

これから$p(x),\ q(x)$は，ある整式$P(x),\ Q(x)$を用いて

$$p(x)=(x+1)P(x)-\dfrac{1}{2},\ q(x)=(x-1)Q(x)+\dfrac{1}{8}$$

と表される．これを与式に代入して

$$(x-1)\left\{(x+1)P(x)-\dfrac{1}{2} \right\}+ (x+1)^3\left\{(x-1)Q(x)+\dfrac{1}{8} \right\}=1$$

これから

$$\begin{eqnarray*} (x^2-1)P(x)+(x^2-1)(x+1)^2Q(x)&=&1-\dfrac{(x+1)^3}{8}+\dfrac{x-1}{2}\\ &=&\dfrac{(x^2-1)(-x-3)}{8} \end{eqnarray*}$$

$$∴\quad P(x)=-(x+1)^2Q(x)-\dfrac{x+3}{8}$$

次数を小さくとるために，$Q(x)=0$とおく． $P(x)=-\dfrac{x+3}{8}$．

このとき

$$\begin{eqnarray*} p(x)&=&(x+1)\left(-\dfrac{x+3}{8} \right)-\dfrac{1}{2}\\ &=... ...rac{1}{8}x^2-\dfrac{1}{2}x-\dfrac{7}{8}\\ q(x)&=&\dfrac{1}{8} \end{eqnarray*}$$

逆にこれは与式を満たす．

次に与式を満たす任意の$p(x),\ q(x)$と，先に求めた一組の解を与式に代入し

$$\begin{array}{l} (x-1)p(x)+(x+1)^3q(x)=1\\ (x-1)\left... ...\right) +(x+1)^3\left( \dfrac{1}{8}\right)=1 \end{array}$$

の辺々を引く(以下は同じ)．

解答 36   問題36    

解1    (整式の除法を用いる方法)

$Q(x)$は2次式なので， 整式$P(x)$を$Q(x)$で割った余りは1次以下の整式である． 商を$A(x)$，余りを$ax+b$とする．

$$P(x)=Q(x)A(x)+ax+b$$

このとき

$$\begin{eqnarray*} &&\{P(x)\}^2=\{Q(x)A(x)\}^2\\ &&\quad+2(ax+b)Q(x)A(x)+(ax+b)^2 \end{eqnarray*}$$

ところが$\{P(x)\}^2$は$Q(x)$で割り切れるので $\{P(x)\}^2=Q(x)B(x)$とおける． これから

$$\begin{eqnarray*} &&Q(x)\left[B(x)-Q(x)\{A(x)\}^2\right.\\ &&\quad\left.-2(ax+b)A(x)\right]=(ax+b)^2 \end{eqnarray*}$$

$Q(x)$は2次式で，右辺は2次以下であるから， $B(x)-Q(x)\{A(x)\}^2-2(ax+b)A(x)$は定数である．これを$c$とする．

$P(x)$は$Q(x)$で割り切れないので右辺は定数0ではない． つまり$c\ne 0$である．よって$Q(x)$は

$$Q(x)=\dfrac{1}{c}(ax+b)^2$$

と表される．$Q(x)$は2次式だから$a\ne 0$である． このとき方程式$Q(x)=0$は重解 $x=-\dfrac{b}{a}$を持つ．

解2    (整式の整数論を用いる方法)

$Q(x)=0$の解を$\alpha$と$\beta$とし，

$$Q(x)=a(x-\alpha)(x-\beta)$$

とおく． $\alpha\ne \beta$と仮定する． このとき$x-\alpha$と$x-\beta$は互いに素である． よって任意の整式$f(x)$について$f(x)$が$Q(x)$で割りきれることと， $f(x)$が$x-\alpha$で割り切れかつ$x-\beta$で割り切れることが同値である． もし$P(x)$が因数$x-\alpha$をもたなければ，整式における素因数分解の一意性によって， $\{P(x)\}^2$も因数$x-\alpha$をもたない． よってもし$\{P(x)\}^2$が因数$x-\alpha$をもてば， $P(x)$が因数$x-\alpha$をもつ．

$\{P(x)\}^2$は$Q(x)$で割り切れるので， $\{P(x)\}^2$が因数$x-\alpha$と$x-\beta$をもち， その結果$P(x)$が因数$x-\alpha$と$x-\beta$をもつ．

ところがこれは$P(x)$が$Q(x)$で割りきれることを意味し，仮定と矛盾する． よって$\alpha=\beta$であり，2次方程式$Q(x)=0$は$x=\alpha$を重解にもつ．

解答 37   問題37    

解1    (整式の除法を用いる方法)

$A(x)$と$B(x)$を$C(x)$で割った商と余りをそれぞれ$a,\ p$と$b,\ q$とし，

$$\begin{eqnarray*} A(x)&=&aC(x)+p\\ B(x)&=&bC(x)+q \end{eqnarray*}$$

とおく． それぞれ1次式であるので，$ab \ne 0$である． $\{A(x)\}^2+\{B(x)\}^2=\{C(x)\}^2$より

$$a^2\{C(x)\}^2+2apC(x)+p^2+b^2\{C(x)\}^2+2bqC(x)+q^2 =\{C(x)\}^2\quad \cdots\maru{1}$$

$C(x)$を$cx+d$とすると，$c\ne 0$で，両辺の$x^2$の係数の比較より

$$a^2c^2+b^2c^2=c^2$$

これから

$$a^2+b^2=1$$

である． このとき$\maru{1}$は

$$2apC(x)+p^2+ 2bqC(x)+q^2=0$$

となる．両辺の$x$の係数比較から

$$2apc+2bqc=0$$

その結果， $ap+bq=0\quad \cdots\maru{2}$となり，さらに

$$p^2+q^2=0\quad \cdots\maru{3}$$

である．ここで$a\ne 0$なので$\maru{2}$から

$$p=-\frac{bq}{a}$$

これを$\maru{3}$に代入して

$$\dfrac{b^2q^2}{a^2}+q^2 =\dfrac{b^2+a^2}{a^2}q^2=\dfrac{1}{a^2}q^2=0$$

よって$q=0$となり，$\maru{3}$から$p=0$．

$A(x)$と$B(x)$はともに$C(x)$の定数倍であることが示された．

解2    (整式の整数論を用いる方法)

$\{A(x)\}^2+\{B(x)\}^2=\{C(x)\}^2$より

$$\{B(x)\}^2=\{C(x)+A(x)\}\{C(x)-A(x)\}$$

である． $C(x)+A(x)$も$C(x)-A(x)$も1次以下の整式であるから$\{B(x)\}^2$の定数倍になることはない． したがって定数$k\ (k\ne 0)$が存在して

$$\begin{eqnarray*} &&C(x)+A(x)=kB(x)\\ &&C(x)-A(x)=\dfrac{1}{k}B(x) \end{eqnarray*}$$

と表される． これから

$$A(x)=\dfrac{k^2-1}{2k}B(x),\ C(x)=\dfrac{k^2+1}{2k}B(x)$$

である． $A(x)$も$C(x)$も1次式なので$k^2\pm 1\ne 0$である．

$$A(x)=\dfrac{k^2-1}{k^2+1}C(x),\ B(x)=\dfrac{2k}{k^2+1}C(x)$$

となり，$A(x)$と$B(x)$はともに$C(x)$の定数倍であることが示された．

解答 38   問題38     解1    

$f(x)$ を $n\ (n \ge 0)$ 次， $g(y)\ (m \ge 0)$ を $m$ 次とし

$$\begin{eqnarray*} f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0\\ g(y)=b_my^m+b_{m-1}x^{m-1}+\cdots +b_0 \end{eqnarray*}$$

とおく． 条件は $f(x)$ と $g(y)$ で対称なので $n \ge m$ とする．

$y=\dfrac{1}{x}$ のとき条件は

$$\begin{eqnarray*} f(x)g(y)&=&f(x)g \left(\dfrac{1}{x} \right)\\ &=&(a_nx^n+... ...a_0)(b_m +b_{m-1}x+\cdots+b_0x^m)=x^m \quad \cdots \maru{1} \end{eqnarray*}$$

となる．

$$b_0,\ b_1,\ \cdots,\ b_m$$

のなかでこの順に見て最初に0でない係数を $b_{m-j}$ とする．上の条件は

$$\begin{eqnarray*} &&(a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0)(b_m +b_{m-1}x+\cdots+b_{m-j}x^j )=x^m\\ &\iff&a_nb_{m-j}x^{n+j}+\cdots=x^m \end{eqnarray*}$$

これから $n+j=m$ であるが $n \ge m$ より $j\ne 0$ なら$n+j>m$で不可．

$$∴ \quad j=0,\ n=m,\ a_nb_{m-j}=1$$

つまり $a_nb_n=1$ ．整数係数なので $a_n=b_n=\pm 1$ で $g(y)=b_ny^n$ ． このとき 1より

$$x^n+b_n(a_{n-1}x^{n-1}+\cdots+a_0)=x^n$$

$b_n\ne 0$ なので $a_{n-1}=\cdots =a_0=0$． ゆえに

$$f(x)=\pm x^n,\ g(y)=\pm y^n \quad (複号同順) \quad n \ 非負整数$$

解2    

$f(x)$ を $n\ (n \ge 0)$ 次， $g(y)\ (m \ge 0)$ を $m$ 次とし

$$\begin{eqnarray*} f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0\\ g(y)=b_my^m+b_{m-1}x^{m-1}+\cdots +b_0 \end{eqnarray*}$$

とおく． 条件は $f(x)$ と $g(y)$ で対称なので $n \ge m$ とする．

$y=\dfrac{1}{x}$ のとき条件は

$$\begin{eqnarray*} f(x)g(y)&=&f(x)g \left(\dfrac{1}{x} \right)\\ &=&(a_nx^n+... ...a_0)(b_m +b_{m-1}x+\cdots+b_0x^m)=x^m \quad \cdots \maru{1} \end{eqnarray*}$$

となる．

$a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$も $b_m +b_{m-1}x+\cdots+b_0x^m$も$x^m$ の約数となるが，$x$は既約なので，ともに$x^l$の定数倍という形をしている． 次数を考えると$n=m$で

$$a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0=a_nx^n,\ b_m +b_{m-1}x+\cdots+b_0x^m=b_m$$

である．さらに$a_nb_m=1$となり係数が整数なのでともに$\pm 1$である．ゆえに

$$f(x)=\pm x^n,\ g(y)=\pm y^n \quad (複号同順) \quad n \ 非負整数$$

解答 39 (問題39)        $p=2$ のとき．

$$(a+bi)^p=a^2-b^2+2abi$$

で, $a>0,b>0$ よりこれは実数とはなり得ない．

$p \ge 3$ とする．二項定理より

$$\begin{eqnarray*} (a+bi)^p&=&\sum_{k=0}^p{}_p \mathrm{C}_k a^{p-k}(ib)^k\\ &=... ...c{p-1}{2}}(-1)^m{}_p \mathrm{C}_{2m+1}a^{p-2m-1}b^{2m+1}\right) \end{eqnarray*}$$

$(a+bi)^p$ が実数とすると

$$\sum_{m=0}^{ \frac{p-1}{2}}(-1)^m{}_p \mathrm{C}_{2m+1}a^{p-2m-1}b^{2m+1}=0$$

である．ところが

$$\begin{eqnarray*} &&\sum_{m=0}^{ \frac{p-1}{2}}(-1)^m{}_p \mathrm{C}_{2m+1}a^{p... ...m{C}_{2m+1}a^{p-2m-2}b^{2m-1} \right) +(-1)^{\frac{p-1}{2}}b^p \end{eqnarray*}$$

ただし $p=3$ のとき中央の項は0とする．

一般に $1 \le k \le p-1$ に対して

$${}_p \mathrm{C}_k= \frac{p!}{k!(p-k)!}$$

であるが, $p$ が素数なので $k!(p-k)!$ は $p$ と互いに素である．しかも右辺は整数なので

$$\dfrac{(p-1)!}{k!(p-k)!}$$

が整数．つまり ${}_p \mathrm{C}_k$ は $p$ の倍数である． したがってある整数 $N$ が存在して

$$pa^{p-1}b+ab^2\cdot pN+(-1)^{\frac{p-1}{2}}b^p =0$$

$$pa^{p-1}+ab\cdot pN+(-1)^{\frac{p-1}{2}}b^{p-1} =0$$

となる．これからまず $b$ が $p$ の倍数である．そこで $b=pl$ とおく．

$$pa^{p-1}+apl\cdot pN+(-1)^{\frac{p-1}{2}}(pl)^{p-1}=0$$

つまり

$$a^{p-1}+al\cdot pN+(-1)^{\frac{p-1}{2}}p^{p-2}l^{p-1}=0$$

となる．これから $a$ も $p$ の倍数である．

$a$ も $b$ も $p$ の倍数となり, $a$ , $b$ が互いに素であることと矛盾した．

以上から $(a+bi)^p$ は実数ではあり得ないことが示された．

解答 40 (問題40)       

(1)

係数は実数なので，$a+bi$が解ならその共役$a-bi$も解である． 他の実数解を$\alpha$とする．解と係数の関係から

$$\left\{ \begin{array}{l} (a+bi)+(a-bi)+\alpha=2a+\alph... ...)(a-bi)\alpha =(a^2+b^2)\alpha=-60 \end{array} \right.$$

である．$\alpha=-8-2a$より $(a^2+b^2)(-8-2a)=-60$となるので

$$(a^2+b^2)(a+4)=30 \quad \cdots\maru{1}$$

である．30の約数で$a^2+b^2$の形の数， および$\maru{1}$となるようにそのとき$a+4$のとるべき値を書くと

$$\begin{array}{r\vert c\vert c\vert c\vert c} a^2+b^2&0^2... ...2+2^2=5&1^2+3^2=10\\ \hline a+4&30&15&6&3 \end{array}$$

である． 各$a^2+b^2$に対し，$a$と$b$の入れ替えと正負で4通り$a$がとれるが， そのうち$a+4$がとるべき値になるものを選ぶと

$$(a,\ b)=(-1,\ \pm 3),\ (2,\ \pm 1)$$

のみである．それぞれ $\alpha=-6,\ m=22$および $\alpha=-12,\ m=-43$である．

よって条件を満たす$m$は$-6,\ -43$である．

(2)

(1)から$f(x)=0$の解は

$$\begin{array}{ll} m=22のとき&-6,\ -1\pm 3i\\ m=-43&-12,\ 2\pm i \end{array}$$

解答 41 (問題41)  

(1)

$$(a+2c)^2+4c(b-a-c)=a^2+4bc$$

$(a,\ b,\ c)$は等式(Q)を満たすので$a^2+4bc=p$である．ゆえに $(a+2c,\ c,\ b-a-c)$ もまた等式(Q)を満たす．

(2)

$a=b-c$とする．

$$p=a^2+4bc=(b-c)^2+4bc=(b+c)^2$$

$b+c$ が自然数なので， $p$ が素数であることに反する．

$a=2b$とする．

$$p=a^2+4bc=(2b)^2+4bc=4b(b+c)$$

$b,\ b+c$ が自然数なので， $p$ が素数であることに反する．

ゆえに，$a=b-c$ や$a=2b$を満たすことはない．

(3)

手続きのうち，(i)と(iii)は，必ず変化する．変化しないときは手続き(ii)で

$$2b-a=a,\ a-b+c=c$$

となるときにかぎる．これから $a=b$ ．このとき

$$p=a(a+4c)$$

$p$ は素数，かつ $a+4c>1$ なので $a=1$． このとき

$$p=1+4c=4k+1$$

から $c=k$

したがって題意をみたすものは $(a,\ b,\ c)=(1,\ 1,\ k)$であり， これ以外には存在しない．

(4)

等式(Q)を満たす自然数の組$(a,\ b,\ c)$に対して上の手続きを1回行ったものを $(a',\ b',\ c')$，2回行ったものを $(a'',\ b'',\ c'')$と記す． これらは等式(Q)を満たす．

(i)

$a<b-c$ならば $a'=a+2c,\ b'=c,\ c'=b-a-c$．このときは$a'>2b'$なので

$$a''=a'-2b'=(a+2c)-2c=a,\ b''=a'-b'+c'=b,\ c''=b'=c$$

(ii)

$b-c<a<2b$ならば $a'=2b-a,\ b'=b,\ c'=a-b+c$．このときは $b'-c'=2b-a-c$なので$b'-c'<a'<2b'$となる．ゆえに

$$a''=2b'-a'=2b-(2b-a)=a,\ b''=b'=b,\ c''=a'-b'+c'=c$$

(iii)

$a>2b$ならば $a'=a-2b,\ b'=a-b+c,\ c'=b$．このときは$a'<b'-c'$なので

$$a''=a'+2c'=a,\ b''=c'=b,\ c''=b'-a'-c'=(a-b+c)-(a-2b)-b=c$$

したがって2回の操作で元の組に戻る．

したがって組の各元はたがいにこの操作で入れ替わるものの組に分けることができる．

この操作で変わらないものはただ一つなので，その他は2つずつの組になる．

したがって等式(Q)を満たす自然数3つの組の全体の個数は奇数である．

(5)

等式(Q)は $b$ と $c$ に関して対称である．したがって組$(a,\ b,\ c)$ が等式(Q)を満たせば，組$(a,\ c,\ b)$も満たす．

(3)から等式(Q)を満たす自然数3つの組は少なくとも一組は存在し， (4)からそのような組の全体の個数は奇数である．

もしすべての組が $b\ne c$ なら，2つずつが組になって そのような組の全体の個数は偶数になる．

したがって，そのような組のなかには $b=c$ となるものが存在する．このとき

$$p=a^2+(2b)^2$$

と表される．

注意 9.2.6  

この問題は定理47 の別証明になっている．

出典：
D. Zagier,
A one-sentence proof that every prime $p\equiv 1\ (\bmod.\ 4)$ is a sum of two squares,
Amer. Math. Monthly 97 (1990) 144.

またこれは次の書でも紹介されている．

『数論の３つの真珠』（ヒンチン著、蟹江訳、日本評論社）p.128

解答 42 (問題42)  

(1)

(i)

$(x,\ y)$ を任意の整数解とする．

$$\alpha x= \beta y$$

で $\alpha , \, \beta$ が互いに素な正の整数であるから， $x$ は $\beta$ の倍数である． $x=\beta t$ とおく．このとき $y=\alpha t$ となる． 逆にこの形をしている $(x,\ y)$ は方程式を満たす．

$$x=\beta t,\ y=\alpha t\quad (t\ \ は任意の整数)$$

(ii)

$\alpha$ を $\beta$ で割り商が $q$ 余りが $r_1$ とすると

$$\dfrac{\alpha}{\beta}=q+\dfrac{r_1}{\beta}\quad 0 \le \dfrac{r_1}{\beta}<1$$

一方

$$\dfrac{\alpha}{\beta} =a_1+\dfrac{1}{a_2 + \dfrac{1}{ a_... ... \le \dfrac{1}{a_2 + \dfrac{1}{ a_3 + \dfrac{1}{ a_4 }}}<1$$

正の有理数の整数部分と小数部分は一意だから

$$q=a_1,\ \dfrac{r_1}{\beta} =\dfrac{1}{a_2 + \dfrac{1}{ a_3 + \dfrac{1}{ a_4 }}}$$

次に

$$\dfrac{\beta}{r_1} =a_2 + \dfrac{1}{ a_3 + \dfrac{1}{ a_4 }}$$

なので，同様に $\beta$ を $r_1$ で割った商が $a_2$ で， 余りを $r_2$ とすると

$$\dfrac{r_1}{r_2}=a_3 + \dfrac{1}{ a_4 }$$

再び同様に考えると $r_1$ を $r_2$ で割った商が $a_3$ で，その余りを $r_3$ とすると

$$\dfrac{r_2}{r_3}=a_4$$

つまり

$$\begin{eqnarray*} \alpha&=&a_1\beta+r_1\\ \beta&=&a_2r_1+r_2\\ r_1&=&a_3r_2+r_3\\ r_2&=&a_4r_3 \end{eqnarray*}$$

ゆえに

$$\begin{eqnarray*} \alpha&=&a_1(a_2r_1+r_2)+r_1\\ &=&a_1a_2(a_3r_2+r_3)+a_1r... ..._1a_4r_3+a_3a_4r_3+r_3\\ \beta&=&a_2a_3a_4r_3+a_2r_3+a_4r_3 \end{eqnarray*}$$

$\alpha$ と $\beta$ は互いに素なので $r_3=1$

注意 9.2.7   ユークリッドの互除法の原理から$r_3=1$ であるが，ここは直接確認した．

したがって

$$\begin{eqnarray*} \alpha&=&a_1\beta+r_1\\ \beta&=&a_2r_1+r_2\\ r_1&=&a_3r_2+1 \end{eqnarray*}$$

という除法の系列ができる． このとき

$$\begin{eqnarray*} r_1&=&\alpha-a_1\beta\\ r_2&=&\beta-a_2r_1=\beta-a_2(\alp... ...quad \alpha-a_1\beta &=&a_3(-a_2\alpha+(1+a_1a_2)\beta)+1\\ \end{eqnarray*}$$

つまり

$$\begin{eqnarray*} &&(1+a_2a_3)\alpha-(a_1a_2a_3+a_1+a_3)\beta=1\\ ∴ &&\alpha q -\beta p=1 \end{eqnarray*}$$

(2)

$157と68$ は互いに素である．

$$\begin{eqnarray*} 157&=&2\cdot 68+21\\ 68&=&3\cdot21+5\\ 21&=&4\cdot5+1 \end{eqnarray*}$$

つまり

$$\dfrac{157}{68} =2+\dfrac{1}{3+\dfrac{1}{4+\dfrac{1}{5}}}$$

(1)より $p=2\cdot3\cdot4+2+4=30，\ q=3\cdot4+1=13$とおくと

$$157\cdot13-68\cdot30=1$$

したがって

$$157\cdot39-68\cdot90=3$$

$(x,\ y)$を $157 x-68y=3$ の任意の整数解とする．

$$157(x-39)-68(y-90)=0$$

ゆえに(1)より

$$x-39=68t,\ y-90=157t\quad (tは任意の整数)$$

と書ける．

$$∴\quad x=39+68t,\ y=90+157t\quad (tは任意の整数)$$

解答 43 (問題43)  

1. $$\begin{eqnarray*} a_n+b_n\sqrt{2}&=&(3+2\sqrt{2})^n\\ &=&(3+2\sqrt{2})(3+2\... ...rt{2})\\ &=&(3a_{n-1}+4b_{n-1})+(2a_{n-1}+3b_{n-1})\sqrt{2} \end{eqnarray*}$$
   
   
   もし $b_n\ne 2a_{n-1}+3b_{n-1}$なら
   
   $$\sqrt{2}=-\dfrac{a_n-3a_{n-1}-4b_{n-1}}{b_n- 2a_{n-1}-3b_{n-1}}$$
   
   
   となる．$\sqrt{2}$は無理数で右辺は有理数となり．矛盾．
   
   $$∴\quad \left\{ \begin{array}{l} a_n=3a_{n-1}+4b_{n-1}\\ b_n=2a_{n-1}+3b_{n-1} \end{array} \right.$$
   
   

2. $n\ge 2$のとき
   $$\begin{eqnarray*} {a_n}^2-2{b_n}^2&=&(3a_{n-1}+4b_{n-1})^2-2(2a_{n-1}+3b_{n-1})^2\\ &=&{a_{n-1}}^2-2{b_{n-1}}^2 \end{eqnarray*}$$
   
   
   
   
   $$∴\quad {a_n}^2-2{b_n}^2={a_1}^2-2{b_1}^2=9-2\cdot4=1$$
   
   

3. (2)から
   
   $$\dfrac{ {a_n}^2}{{b_n}^2}-2=\dfrac{1}{{b_n}^2}$$
   
   
   である．つまり
   
   $$\dfrac{a_n}{b_n}-\sqrt{2}=\dfrac{1}{{b_n}^2}\cdot\dfrac{1}{\dfrac{a_n}{b_n}+\sqrt{2}}$$
   
   
   ここで(1)から
   
   $$\vecarray{a_n}{b_n}=\matrix{3}{4}{2}{3}\vecarray{a_{n-1}}{b_{n-1}}$$
   
   
   なので，これを用いて$a_1=3,\ b_1=2$から$a_n,\ b_n$を順次求めると，
   
   $$\vecarray{a_2}{b_2}=\vecarray{17}{12},\ \vecarray{a_3}{... ...ecarray{99}{70},\ \vecarray{a_4}{b_4}=\vecarray{577}{408}$$
   
   
   である．したがって
   
   $$\dfrac{a_4}{b_4}-\sqrt{2}=\dfrac{1}{408^2}\cdot\dfrac{1}{\dfrac{577}{408}+\sqrt{2}} <\dfrac{1}{10000}$$
   
   

   求める有理数は $\dfrac{a_4}{b_4}=\dfrac{577}{408}$

解答 44 (問題44)  

1. 条件から
   $$\begin{eqnarray*} P_{n+1}Q_n-P_nQ_{n+1}&=&(P_{n-1}+k_nP_n)Q_n-P_n(Q_{n-1}+k_nQ... ... ∴&&P_nQ_{n-1}-P_{n-1}Q_n=(-1)^{n-1}(P_1Q_0-P_0Q_1)=(-1)^n \end{eqnarray*}$$
   
   

2. $P_n$ と $Q_n$ の最大公約数を $d$ とし $P_n=dP'_n,\ Q_n=dQ'_n$ とする.
   
   $$P_nQ_{n-1}-P_{n-1}Q_n=d(P'_nQ_{n-1}-P_{n-1}Q'_n)=(-1)^n$$
   
   
   
   
   $$∴\quad d=1$$
   
   
   つまり $n \ge 1$ のとき， $P_n$ と $Q_n$ の最大公約数は $1$ である．

3. $$\begin{eqnarray*} &&\dfrac{P_{n-1}+P_na_n}{Q_{n-1}+Q_na_n} =\dfrac{P_{n-1}+P... ...n}{a_{n+1}}} =\dfrac{P_n+P_{n+1}a_{n+1}}{Q_n+Q_{n+1}a_{n+1}} \end{eqnarray*}$$
   
   
   
   
   $$∴\quad \dfrac{P_{n-1}+P_na_n}{Q_{n-1}+Q_na_n}=\dfrac{P_0... ..._0+Q_1a_1} =\dfrac{1+k_0a_1}{a_1}=k_0+\dfrac{1}{a_1}=a_0=a$$
   
   

4. $$\begin{eqnarray*} a-\dfrac{P_n}{Q_n}&=&\dfrac{P_{n-1}+P_na_n}{Q_{n-1}+Q_na_n}-... ...}{(Q_{n-1}+Q_na_n)Q_n} =\dfrac{-(-1)^n}{(Q_{n-1}+Q_na_n)Q_n} \end{eqnarray*}$$
   
   
   
   
   $$∴\quad \left\vert a-\dfrac{P_n}{Q_n} \right\vert=\dfrac{1}{\vert(Q_{n-1}+Q_na_n)Q_n\vert}$$
   
   
   ここで $a_0$ 無理数なので，帰納的に定められた $\{ a_n \}$ はすべて正の無理数である. また $0<a_{n-1}-k_{n-1}=\dfrac{1}{a_n}<1$ から $a_n>1$ ．
   

   定め方から $Q_n>0\ (n\ge 1)$ なので

   $$\begin{eqnarray*} \vert(Q_{n-1}+Q_na_n)Q_n\vert&=&(Q_{n-1}+Q_na_n)Q_n\\ &\ge & a_nQ_n^2>Q_n^2 \end{eqnarray*}$$
   
   
   
   
   $$∴\quad \left\vert a-\dfrac{P_n}{Q_n}\right\vert<\dfrac{1}{Q_n^2}$$
   
   

解答 45 (問題45)       

(1)

四つの頂点を $(x-1,\ y-1),\ (x,\ y-1),\ (x,\ y),\ (x-1,\ y)$ とする．

$x$ を超えない最大の整数を $m$ とする． $m\le x <m+1$ であるから

$$x-1<m \le x$$

つまり区間 $[x-1,\ x]$ には整数 $m$ が存在する．

$y$ 方向についても同様に $[y-1,\ y]$ には整数 $n$ が存在する．

したがって，正方形(周をこめる)には少なくとも一つの 格子点 $(m,\ n)$ が存在した．

(2)

辺の長さが $\sqrt{2}$ の正方形には半径 $\dfrac{1}{\sqrt{2}}$ の円が 内接している． $\dfrac{1}{\sqrt{2}}$ の円には，1辺の長さが1の正方形が内接する．

したがって(1)から少なくとも一つの格子点を含むことが示された．

解答 46 (問題46)       

(1)

$xy$ 平面の点 $(x,\ y)$ に対して

$$\vecarray{u}{v}=\vecarray{ax+cy}{bx+dy}=\matrix{a}{c}{b}{d}\vecarray{x}{y}$$

で定まる点 $(u,\ v)$ を対応させる．このとき$ad-bc=1$ なので逆に

$$\vecarray{x}{y}=\vecarray{du-cv}{-bu+av}=\matrix{d}{-c}{-b}{a}\vecarray{u}{v}$$

と解ける．

この対応で $(x,\ y)$ が格子点なら $(u,\ v)$ も格子点であり，逆も成り立つ．

$S$ 内の任意の点 ${\rm P}$ は二つの実数 $0\le s,\ t\le1$によって

$$\overrightarrow{{\rm OP}} =s\overrightarrow{{\rm OA}}+t\overrightarrow{{\rm OB}}=\vecarray{sa+tc}{sb+td}$$

と表されるが

$$\vecarray{s}{t}=\matrix{d}{-c}{-b}{a}\vecarray{sa+tc}{sb+td}$$

なので，この対応で $S$ は $(0,\ 0),\ (1,\ 0),\ (0,\ 1),\ (1,\ 1)$ を頂点とする 正方形 $T$ に移る．

もし $S$ の内部に格子点があれば， この対応で $T$ 内部の格子点に移らなければならない． しかし $T$ の内部には明らかに格子点は存在しない．

したがって $S$ の内部にも格子点は存在しない．

(2)

(1)と同様の変換を考える．

$$\vecarray{2s}{2t}=\matrix{d}{-c}{-b}{a}\vecarray{sa+tc}{sb+td}$$

であり， $S$はこの変換で $(0,\ 0),\ (2,\ 0),\ (0,\ 2),\ (2,\ 2)$ を頂点とする 正方形 $U$ に移る． $S$内部の 点 $(sa+tc,\ sb+td)$が格子点であるとする．

$m=sa+tc,\ n=sb+td$とおくと，

$$\vecarray{2s}{2t}=\matrix{d}{-c}{-b}{a}\vecarray{m}{n}=\vecarray{dm-cn}{-bm+an}$$

なので，やはり $U$ の格子点に移る．

したがって$ad-bc=2$ のとき, $S$ の中に格子点があれば，この対応で $U$ 内部の 格子点に移らなければならない．$U$内部の格子点は正方形の対角線の交点$(1,\ 1)$のみ である．つまり $s=\dfrac{1}{2},\ t=\dfrac{1}{2}$ ．

したがって$S$内部の格子点は $(\dfrac{a+c}{2},\ \dfrac{b+d}{2})$である以外になく， これは平行四辺形の対角線の交点である．

解答 47 (問題47)       

(1)

整数 $m,\ n$ をとり，点$(x,\ y)$に対し点 $(x+m,\ y+n)$ を対応させると， $(x,\ y)$が格子点なら$(x+m,\ y+n)$も格子点であり，逆もなり立つ．

したがって線分を $x$ 方向と $y$ 方向がともに整数分だけ平行移動しても その上にある格子点の個数は変わらない．

格子点 $(k,\ l)$ がある． $k$ と $l$ の最大公約数を $d$ とし $k=dk',\ l=dl'$ とおく．

このとき原点と格子点 $(k,\ l)$を結ぶ線分上の両端を除く格子点は

$$(k',\ l'),\ (2k',\ 2l'),\ \cdots,\ ((d-1)k',\ (d-1)l')$$

と， $d-1$ 個ある．ゆえにこの個数が奇数なら $d$ は偶数．つまり $x$ 座標， $y$ 座標ともに偶数である．

三角形 ${\rm ABC}$ で $A$ を原点に平行移動しそれを三角形 ${\rm OB'C'}$ とする． このとき辺 ${\rm AB},\ {\rm AC}$ それぞれの上に両端をのぞいて奇数個の格子点が あるので，点 ${\rm B',\ C'}$ の双方の $x$ 座標と $y$ 座標はいずれも偶数である

${\rm B'}(2s,\ 2t)$ ， ${\rm C'}(2u,\ 2v)$ とおく．

${\rm B'}$を原点に平行移動すると，${\rm C'}$は $(2u-2s,\ 2v-2t)$ になる．

$x$ 座標，$y$ 座標ともに偶数であるから， 線分${\rm B'C'}$上に両端を除いて奇数個の格子点があり， 辺 ${\rm BC}$ 上にも両端を除いて奇数個の格子点がある．

(2)

三角形 ${\rm ABC}$ で $A$ を原点に平行移動し それを三角形 ${\rm OB'C'}$ とする． このとき辺 ${\rm AB},\ {\rm AC}$ それぞれの上に両端をのぞいて ちょうど3個ずつの格子点があるので， 点 ${\rm B',\ C'}$ の双方の $x$ 座標と $y$ 座標はいずれも4の倍数である

${\rm B'}(4s,\ 4t)$ ， ${\rm C'}(4u,\ 4v)$ とおく．

$$\bigtriangleup {\rm ABC}=\dfrac{1}{2}\vert 4s\cdot4v-4t\cdot4u\vert=8\vert sv-tu\vert$$

ゆえに，三角形 ${\rm ABC}$ の面積は8で割り切れる整数である．

解答 48 (問題48)       

(1)

3頂点を $(a_1,\ b_1),\ (a_2,\ b_2),\ (a_3,\ b_3)$ とする． このとき面積 $S$ は

$$S=\dfrac{1}{2}\vert(a_2-a_1)(b_3-b_1)-(a_3-a_1)(b_2-b_1)\vert$$

である．ゆえに $2S$ は整数である．

(1)

3頂点の座標がすべて整数の組であるような正三角形が存在するとし， その正三角形の面積を $S$ とする．(1)から $S$ は有理数である．

一方正三角形の1辺を $t$ をすると $t^2=(a_2-a_1)^2+(b_2-b_1)^2$ なので面積 $S$ は

$$S=\dfrac{1}{2}\sin \dfrac{\pi}{3}t^2 =\dfrac{\sqrt{3}}{4}\{(a_2-a_1)^2+(b_2-b_1)^2\}$$

これは無理数である． したがって(1)の結果と矛盾した． ゆえに3頂点の座標がすべて整数の組であるような正三角形は存在しない．

(3)

平面上で，5頂点の座標がすべて整数の組であるような正五角形は存在するとし， 正五角形の中心を原点に平行移動する．

隣りあう二つの頂点を ${\rm P},\ {\rm Q}$ とする． ${\rm P},\ {\rm Q}$ は 格子点であるから(1)と同様に $\bigtriangleup {\rm OPQ}$ の面積は有理数である．

一方

$$S=\dfrac{1}{2}\sin\dfrac{2\pi}{5}{\rm OP}^2$$

ここで $\theta=\dfrac{2\pi}{5}$とすると， $2\theta+3\theta=\pi$なので $\sin 2\theta=\sin 3\theta$．つまり

$$2\sin\theta\cos\theta=-4\sin^3\theta+3\sin\theta$$

$\sin \theta \ne 0$ なので

$$2\cos\theta=-4\sin^2\theta+3=-4(1-\cos^2\theta)+3$$

$\theta$は鋭角なので $\cos\theta=\dfrac{1+\sqrt{5}}{4}$ ．ゆえに $\sin^2\theta=\dfrac{10-2\sqrt{5}}{16}$．これは無理数であり，したがって $\sin \theta$も無理数である．

(2)と同様の矛盾が生じた． よって，平面上で5頂点の座標がすべて整数の組であるような正五角形は存在しない．

解答 49 (問題49)       

(1)

$\sqrt{3}=\dfrac{p}{q}$となる整数 $p,\ q$ が存在したとして矛盾を示す． 以下特に断らなければ文字は整数を表す．

証明法1

$\sqrt{3}$が無理数でない，つまり有理数とする． $\sqrt{3}=\dfrac{q}{p}$ とおく．ここで$p$と$q$ は互いに素であるとできる．

$$∴ \quad 3p^2=q^2$$

数$q$が3の倍数でなければ$q=3k\pm 1$とおける． $q^2=(3k\pm1)^2=k^2\pm6k+1$より3の倍数でない数$q$の平方$q^2$は3の倍数でない． ところが左辺が3の倍数なので $q$ は3の倍数でなければならない． $q=3q'$ とおける．すると

$$3p^2=(3q')^2 \quad \Rightarrow \quad p^2=3{q'}^2$$

これから $p$ も3の倍数となり， $p$ と $q$ が互いに素であることと矛盾した．

ゆえに $\sqrt{3}$は無理数である．

証明法2

$\sqrt{3}$が無理数でない，つまり有理数とする． $\sqrt{3}=\dfrac{q}{p}$ とおく(既約である必要はない)．

$$∴ \quad 3p^2=q^2$$

左辺の因数分解における因数3の個数は奇数である． 右辺の因数分解における因数3の個数は偶数である

これは矛盾である．ゆえに $\sqrt{3}$は無理数である．

証明法3

$\sqrt{3}$が無理数でない，つまり有理数とする． $\sqrt{3}=\dfrac{q}{p}$とおく(既約である必要はない)．．

$$∴ \quad 3p^2=q^2$$

証明法1と同様に3の倍数でない数の平方は3の倍数でない． ところが左辺が3の倍数なので $q$ は3の倍数でなければならない． $q=3q'$ とおける．すると

$$2p^2=(2q')^2 \quad \Rightarrow \quad p^2=2{q'}^2$$

これから $p$ も3の倍数となり$p=3p'$ とおける．

再び

$$3{p'}^2={q'}^2$$

となる．同様にして$p',\ q'$とも3の倍数である．これは何回でも繰り返される．

つまり $p$ も $q$ も3で無限回割れる．これは $p=q=0$ 以外では不可能である．

ゆえに $\sqrt{3}$は無理数である．

(2)

$a\omega+b$が有理数$q$であるとする．$a\omega+b=q$において $a\ne 0$なので

$$\omega=\dfrac{q-b}{a}$$

有理数の和，差，積，商は再び有理数なので，これは$\omega$が無理数であることに矛盾した．

よって$a\omega+b$は無理数である．

(3)

$p,q,r,s$がすべて有理数と仮定する．

$\bigtriangleup \mathrm{OAB}$の面積を二通りの方法で求める．

$$\bigtriangleup \mathrm{OAB}=\dfrac{1}{2}\mathrm{OA}^2\sin 60^{\circ} =\dfrac{\sqrt{3}}{4}(p^2+q^2)$$

一方

$$\bigtriangleup \mathrm{OAB}=\dfrac{1}{2}\vert ps-qr\vert$$

である．ゆえに

$$\dfrac{\sqrt{3}}{4}(p^2+q^2)=\dfrac{1}{2}\vert ps-qr\vert$$

が成り立たねばならない．つまり

$$\dfrac{\sqrt{3}}{4}(p^2+q^2)-\dfrac{1}{2}\vert ps-qr\vert=0$$

である．ここで(2)から左辺は無理数である．一方，右辺0は有理数で矛盾である．

よって $p,q,r,s$のうち少なくとも1つは有理数とならないことが示された．

解答　（追加問題）

解答 50 (問題50)  

(1)

$$\begin{eqnarray*} &&(xz+nyt)^2-n(xt+yz)^2\\ &=&x^2z^2+2nxzyt+n^2y^2t^2-n(x^... ...z^2)\\ &=&x^2(z^2-nt^2)-ny^2(z^2-nt^2)=(x^2-ny^2)(z^2-nt^2) \end{eqnarray*}$$

(2)

$x^2-2y^2=-1$ の自然数解 $(x,\ y)$ の集合を $A$ とする． 一組の解 $(1,\ 1)$ が存在するので $A$ は空集合ではない．

$A$ が有限集合であったとすると，$x$が最大のものが存在する． それを $(x_0,y_0)$ とする．

(1)で $z=t=1,\ n=2$ とすると

$$(x_0+2y_0)^2-2(x_0+y_0)^2=(x_0^2-2y_0^2)(1^2-21^2)\pm 1$$

であるから $(x_0+2y_0,\ x_0+y_0)$ も $A$ の元である．ところがこの元の 値 $x_0+2y_0$ は明らかに値$x_0$より大きい．

$(x_0,y_0)$が $A$ の元で値$x$が最大のものであることに矛盾した．

ゆえに $A$ は無限個の元をもつ．

$n=2$ で(1)を用いることにより $A$ の二つの元 $(x,\ y)$と$(z,\ t)$に対して $(xz+2yt,\ xt+yz)$も$A$の元である．

$(1,\ 1)\in A$ から $(1+2,\ 1+1)=(3,\ 2)\in A$ ． 同様に $(9+2\cdot 4,\ 6+6)=(17,\ 12)\in A$ ． 同様に $(17^2+2\cdot 12^2,\ 17\cdot12+12\cdot17)=(577,\ 408)\in A$ ． これが題意をみたしている．□

解答 51 (問題51)  

(1)

$\mathrm{P}(x,\ y)$ が曲線 $C_+,\ C_-$上の整数点のとき，

$$\begin{eqnarray*} u^2-2v^2&=&(-x+2y)^2-2(x-y)^2\\ &=&x^2-4xy+4y^2-2(x^2-2xy+y^2)\\ &=&-(x^2-2y^2)=-(\pm 1)=\mp1\\ &&(複号同順) \end{eqnarray*}$$

$x=y=1$ を除くので

$$\begin{eqnarray*} (2y)^2-x^2&=&4y^2-(2y^2\pm1)\\ &=&2y^2\mp1>0\\ ∴&&u=... ...-y^2\\ &=&y^2\pm1>0\\ ∴&&v=x-y>0\\ &&(複号同順) \end{eqnarray*}$$

ゆえに $\mathrm{Q}(u,\ v)$ は曲線 $C_-,\ C_+\ (複号同順)$ 上の整数点である．

(2)

(1)より $u>0,\ v>0$ で

$$\begin{eqnarray*} y-v&=&y-(x-y)\\ &=&-x+2y=v>0\\ ∴&&0<v<y \end{eqnarray*}$$

(3)

数学的帰納法で示す． $(x_1,\ y_1)=(1,\ 1)$ は $C_-$ 上の整数点である．

$n=k$ のとき$(x_k,\ y_k)$が $C_+,\ C_-$上の整数点であるとする．

$$\begin{eqnarray*} x_{k+1}+y_{k+1}\sqrt{2}&=&(\sqrt{2}+1)^{k+1}\\ &=&(\sqrt{... ...rt{2}+1)(x_k+\sqrt{2}y_k)\\ &=&(x_k+2y_k)+(x_k+y_k)\sqrt{2} \end{eqnarray*}$$

$\sqrt{2}$が無理数で他は整数なので

$$\vecarray{x_{k+1}}{y_{k+1}}=\vecarray{x_k+2y_k}{x_k+y_k} =\matrix{1}{2}{1}{1}\vecarray{x}{y}$$

これから $(x_{k+1},\ y_{k+1})$は明らかに第1象限の整数点で，

$$\begin{eqnarray*} {x_{k+1}}^2-2{y_{k+1}}^2&=&(x_k+2y_k)^2-2(x_k+y_k)^2\\ &=&-({x_k}^2-2{y_k}^2)=-(\pm 1)=\mp1 \end{eqnarray*}$$

より$C_+,\ C_-$上の整数点である．

したがってすべての自然数 $n$ に対し， 点 $\mathrm{P}(x_n,\ y_n)$ は曲線 $C_+$ または $C_-$上にある．

(4)

曲線 $C_+$ または$C_-$上の整数点で $\mathrm{P}(x_n,\ y_n)\ (n\ は自然数)$ と書き表せないもの集合 $S$ を考える．

$S$ が空集合であることを示せばよい． $S$ が空集合でないと仮定し， $S$ の元の $y$ 座標を考える． それは自然数の部分集合であるからその中に最小のものが存在する． それを $(X,Y)$ とする．

$C_+$ または $C_-$上の整数点で $Y=1$ なら $X=1$ となり，これは $(x_1,y_1)$ である．したがって $Y\ne 1$ ．

(1)(2)から

$$\vecarray{U}{V}=\vecarray{-X+2Y}{X-Y} =\matrix{-1}{2}{1}{-1}\vecarray{X}{Y}$$

とおくと$V<Y$ である． $(U,\ V)$ は $C_+$ または $C_-$上の整数点であるが， $S$ の元で$y$座標が最小である$(X,Y)$ より $y$ 座標が小さいので， $(U,\ V)$ は$S$の元ではない．したがって $\mathrm{P}(x_n,\ y_n)\ (n\ は自然数)$ のどれかに一致する．

$$(U,\ V)=(x_j,\ y_j),\ (j は自然数)$$

とする．

(3)から $(x_{j+1},\ y_{j+1})$も $C_+$ または $C_-$上にある．ところが

$$\begin{eqnarray*} \vecarray{x_{j+1}}{y_{j+1}}&=&\matrix{1}{2}{1}{1}\vecarray{x... ...1}\matrix{-1}{2}{1}{-1}\vecarray{X}{Y}\\ &=&\vecarray{X}{Y} \end{eqnarray*}$$

これは $(X,Y)$ が $\mathrm{P}(x_n,\ y_n)\ (n\ は自然数)$ と書き表せない整数点の集合 $S$ の元であることと矛盾した．

したがって $S$ は空集合であり， $C_+$ または $C_-$上の整数点で $\mathrm{P}(x_n,\ y_n)\ (n\ は自然数)$ と書き表せないものは存在しない．

つまり曲線 $C_+$ または $C_-$上の整数点は $\mathrm{P}(x_n,\ y_n)\ (n\ は自然数)$ に限ることが示された．

(5)

$(x_{n+1},\ y_{n+1})=(x_n+2y_n,\ x_n+y_n)$より

$$\begin{eqnarray*} \dfrac{y_{n+1}-y_n}{x_{n+1}-x_n}&=&\dfrac{x_n}{2y_n}\\ &=... ...}{{y_n}^2}}\\ &=&\dfrac{1}{2}\sqrt{2\pm \dfrac{1}{{y_n}}^2} \end{eqnarray*}$$

数列 $\{ y_n \}$は $y_{n+1}>y_n$である自然数列なので $$\lim_{n \to \infty}y_n=\infty$$ である．

$$∴\quad \displaystyle \lim_{n \to \infty}\dfrac{y_{n+1}-y_n}{x_{n+1}-x_n} =\dfrac{\sqrt{2}}{2}$$

次: 出典と文献 上: 解答 前: 演習問題解答