次: 5章 上: 解答 前: 3章

4章

解答 11   問題11

(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$の等差数列になる．

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

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

解答 12   問題12
　自然数$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\ は自然数\ \}$$

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

解答 13   問題13    

1. $x \ge y$ としてよい． $C(nx)=C(ny)$より$nx-ny$は1000の倍数である．
   
   $$nx-ny=n(x-y)$$
   
   で，$n$と1000が互いに素なので，$x-y$ が1000の倍数である．

   よって $C(x)=C(y)$ である．

2. (1)より， $C(0),C(n),C(2n),\cdots,C(999n)$はすべて異なる．

   つまり，集合 $\{C(0),C(n),C(2n),\cdots,C(999n)\}$は1000個の要素からなる． この集合は，集合 $\{0,1,\cdots,999 \}$ に含まれ，ともに1000個の要素からなる．
   

   $$∴\quad \{C(0),C(n),C(2n),\cdots,C(999n)\}=\{0,1,\cdots,999 \}$$
   
   つまり，要素 $C(0),\ \cdots,\ C(999n)$ のどれかは1に一致する． すなわち$C(nx)=1$ となる0以上の整数 $x$ が存在する．
3. $379x=1+1000y$となる整数解$(x,\ y)$を一組求める．
   $$\begin{eqnarray*} 1&=&397x-1000y=397x-(397\cdot2+206)y\\ &=&397(x-2y)-206y=... ...)=(15\cdot12+11)(2x-5y)+15(x-3y)\\ &=&15(25x-63y)+11(2x-5y) \end{eqnarray*}$$
   
   $15\cdot3+11\cdot(-4)=1$なので
   
   $$\left\{ \begin{array}{l} 25x-63y=3\\ 2x-5y=-4 \end{array} \right.$$
   
   とおき，これを解く． $x=-267,\ y=-106$である．つまり
   
   $$397(-267)-1000(-106)=1$$
   
   任意の解$(m,\ n)$，つまり$397m-1000n=1$を満たす整数の組に対し，
   
   $$397(m+267)-1000(n+106)=0$$
   
   が成り立つ．

   397と1000は互いに素なので$m+267$は1000の倍数，これを$m+267=1000t$とおくと， $n+106=397t$となる．つまりすべての整数解$(x,\ y)$は，整数$t$を用いて
   

   $$(x,\ y)=(-267+1000t,\ -106+397t)$$
   
   と表される．正で最小の$x$は$t=1$のとき．したがって $C(397x)=1$となる0以上の整数$x$で最小のものは $x=1000-267=733$である． 検算
   
   $$C(733\cdot397)=C(291001)=1$$
   
   

注意 4        受験数学でよく用いられる「引き出し論法」が(2)である． あわせてユークリッドの互助法によって解を構成する方法も(3)で行うので よく学んでおいてほしい．

解答 14   問題14   

(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)$ という解が存在した．

解答 15   問題15    

(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$ 上の格子点も存在する．

解答 16   問題16    

(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*}$$

解答 17   問題17    

(1)      $f(m,\ n)=k$，つまり

$$m^2-mn+n^2-k=0$$

は$m$の2次方程式である．$m$が実数となることが必要なので， $m$の2次式としての判別式を$D$とすると$n$は

$$D=n^2-4(n^2-k)=-3n^2+4k\ge 0$$

を満たさなければならない．これから $0\le n^2\le \dfrac{4k}{3}$となり， $n$は有限個である． 整数$n$に対して整数$m$は多くても2個しかないので$X(k)$は有限集合である．

$k=1$のとき， $0\le n^2\le \dfrac{4}{3}$より $n=0,\ \pm 1$． それぞれ$m$を求めることにより次のようになる．

$$X(1)=\{(1,\ 0),\ (-1,\ 0),\ (0,\ 1),\ (0,\ -1),\ (1,\ 1),\ (-1,\ -1)\}$$

(2)

$$f(m,\ n)=m^2-mn+n^2=k$$

において$k$が偶数とする． $m$と$n$がともに奇数なら$f(m,\ n)$は奇数， $m$と$n$の一方が奇数，一方が偶数なら$f(m,\ n)$は奇数となるので， 整数解があればそれはともに偶数である．

$k=2$のとき $0\le n^2\le \dfrac{8}{3}$．この範囲の偶数は$n=0$のみで， このとき$m^2=2$より解なし． $X(2)$の個数は0である．

$k=4$のとき．$m$も$n$も偶数なので$m=2p$，$n=2q$とおくと

$$m^2-mn+n^2=4p^2-4pq+4q^2=4$$

つまり$p^2-pq+q^2=1$．(1)からこれを満たす整数の組$(p,\ q)$は6組あり， それに対する$(2p,\ 2q)$のみが$f(m,\ n)=4$の解なので， $X(4)$の個数は6である．

(3)     (2)から $f(m,\ n)=2^r\ (r\ 自然数)$の解はともに偶数である． $m=2p$，$n=2q$とおくと

$$\begin{eqnarray*} &&f(m,\ n)=m^2-mn+n^2=2^r\\ &\iff&f(2p,\ 2q)=4p^2-4pq+4q^2=2^r\\ &\iff&f(p,\ q)=p^2-pq+q^2=2^{r-2} \end{eqnarray*}$$

である． これより，集合$X(2^r)$の要素の個数と集合$X(2^{r-2})$の要素の個数は等しい， (2)から集合$X(2)$の要素の個数は0，集合$X(2^2)$の要素の個数は6個なので， $X(2^r)$の要素の個数は$r$が奇数なら0，偶数なら6である．

注意1      $r$が奇数のとき$X(2^r)$の要素の個数が0であることは次のように直接示せる．

整数$n$に対して$m$が整数になるために， 判別式$D$が平方数であることが必要である． $k=2^r$のとき，

$$D=n^2-4(n^2-k)=-3n^2+2^{r+2}=N^2 \quad \cdots\maru{1}$$

とおく． $\maru{1}$の両辺を3で割った余りを考える．

右辺$N^2$を3で割ると，$N$が3の倍数なら余りは0， $N=3s\pm 1$と表せるとき余りは1である．

一方，2のべきは，偶数べきなら $2^{2l}=(3+1)^l$より二項定理から ３で割った余りは1である．これから奇数べきなら余りは2である． よって$r$が奇数なら$\maru{1}$となる$n$，$N$は存在しない．

次: 5章 上: 解答 前: 3章