1節演習問題解答
解答 1 (問題1)
(1) 2x3+ 5x2−3x+ 7 = (x−3)(2x2+ 11x+ 30) + 97である．
∴ Q(x) = 2x2+ 11x+ 30, r−97 (2) (i) F(x)を xの n次の整式とし，xn の係数がan であるとする．
ここで，
Q1(x) =anxn−1, F1(x) =F(x)−G(x)Q1(x)
とおく．
G(x)Q1(x) = (x−a)·anxn−1=anxn−aanxn−1 であるからF1(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) +F1(x)
を満たすxの整式 Q1(x), F1(x),ただし F1(x)の次数はF(x)の次数より小さい，が 存在する．
帰納法の仮定から
F1(x) =G(x)Q1(x) +r となるQ1(x)と rが存在する．したがって，
F(x) =G(x)Q(x) +F1(x) =G(x)Q(x) +G(x)Q1(x) +r=G(x){Q(x) +Q1(x)}+r
Q(x) +Q1(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の相異なる実数解を α1, · · ·, αj とする．
F(α1) = 0より
F(x) = (x−α1)Q1(x) とおける．F(α2) = 0 でα2−α16= 0よりQ(α2) = 0．
∴ Q1(x) = (x−α2)Q2(x) とおける．つまり
F(x) = (x−α1)(x−α2)Q2(x) これを繰りかえすと，
F(x) = (x−α1)· · ·(x−αj)Qj(x) となる整式Qj(x)がある．
もしj > nなら右辺の次数は左辺の次数nより大きくなり不合理．よってj <=n．つまり 題意が示せた．
2節演習問題解答
解答 2 (問題2)
［注］内容的には本文の中にあるが，入試問題の解答として改めて解いておく．
(1)
a1= 1998 b1= 185 1998 = 185×10 + 148より a2= 185 b2= 148 185 = 148×1 + 37より a3= 148 b3= 37 148 = 37×4 + 0より a4= 37 b4= 0
a5= 37 b5= 0 (2) bn6= 0 のときbn+1は an をbn で割った余りであるから余りの定義より，
bn+1< bn
bn= 0のとき 数列{bn}の定義からbn+1=bn ．よって 任意のk, l, nについてbn >=bn+1
(等号はbn= 0のときに限る)が成立する．
(3) もしbn= 0となる nが存在しないとすると，すべてのbn は自然数でしかも bn> bn+1
が成り立つ．このことは 集合{bn}に最小値が存在しないことになり，自然数の性質と矛盾 する．
(4) (a, b)で aとbの最大公約数を表すことにする．bk 6= 0のとき (ak, bk) = (bk, bk+1)
を示す．
ak=bk·qk+bk+1 とかける．ak とbk の公約数はbn+1 の約数になる．ゆえに(ak, bk)<= (bk, bk+1) .
bk とbk+1 の公約数はak の約数になる．ゆえに(ak, bk)>= (bk, bn+1) .
∴ (ak, bk) = (bk, bk+1) つまり(ak, ak+1) = (ak+1, ak+2)．
(3)からある自然数N でbN−16= 0, bN = 0となるものがある．このとき (k, l) = (a1, a2) =· · ·= (aN−1, aN) = (aN, bN) =aN
N <=nの nで同様なので題意が示された．
解答 3 (問題3)
(1) rn−1>0のとき,
rn−2=rn−1qn−1+rn, 0<=rn< rn−1
したがって,
r1=a >=r2=b > r3> r4>· · ·>= 0
となり, 各rn は自然数または0であるから, 高々a+ 1回この操作を繰り返すとこれは0 となる. つまり,
rN−1> rN >0 =rN+1
となる整数N が存在する.
(2) kについての帰納法で示す.
(i) k= 1のとき,
rN+2−k =rN+1= 0, fk=f1= 0 なので, 不等式は成り立つ. 次に, k= 2のとき,
rN+2−k=rN >= 1, fk =f2= 1 よって, 不等式は成り立つ.
(ii) k=m−1, m(m >= 2) のときの不等式の成立, すなわち, rN+2−(m−1)>=fm−1, rN+2−m>=fm
を仮定する. このとき,
rN+2−(m+1) = rN+2−m·qN+2−m+rN+2−(m−1)
>= fmqN+2−m+fm−1
>= fm+fm−1 (なぜなら, qN+2−m>= 1)
= fm+1
となるので, k=m+ 1 のときも成立する.
(iii) よって, (i), (ii)より, k= 1, 2, · · ·, N+ 1のすべてのkに対して不等式が成り立つ.
(3) nに関する帰納法で示す.
(i) n= 1のとき,
fn+1=f2= 1, µ3
2
¶n−2
= µ3
2
¶1−2
= 2 3 n= 2のとき,
fn+1=f3=f2+f1= 1, µ3
2
¶n−2
= µ3
2
¶2−2
= 1 よって,いずれの場合も不等式は成り立つ.
(ii) n=k−1, k(k >= 2)のときの不等式の成立, すなわち fk >=
µ3 2
¶k−3
, fk+1>= µ3
2
¶k−2
を仮定する. このとき
f(k+1)+1 = fk+1+fk
>= µ3
2
¶k−2 +
µ3 2
¶k−3
= µ3
2
¶k−3
· 5 2
>= µ3
2
¶k−1 µ
なぜなら, 5 2 >=9
4
¶
= µ3
2
¶(k+1)−2
よって, n=k+ 1 のときも不等式は成り立つ.
(iii) よって, (i), (ii)より, すべての自然数nに対して不等式が成り立つ.
(4) (2)より, k=N+ 1 のとき,
a=r1=rN+2−(N+1)>=fN+1
よって, (3)より,
a >= µ3
2
¶N−2
で, 両辺の底を 3
2 とする対数をとれば, log3
2a >=N−2 ∴ N <= 2 + log32a
［注意］この入試問題は，ユークリッドの互除法で割り算をどれくらい行えばよいかを評価するもの である．いちばん長くなるのが，割り算での商が常に1になるときで，あまりの列を逆にた どればいわゆるフィボナッチ数列になるときである．このことを問う本格的な問題である．
3節演習問題解答
解答 4 (問題4)
(1) aとbが互いに素であるから，b
axが整数となるのはxがaの倍数であるときにかぎる.
したがって0< k < aの整数k に対し，直線x=kとOA, CBの交点はいずれも格子点で はない.
したがって, OABCの内部にある直線x=kの上には，ちょうど一つの格子点がある．
よって,
OABCの内部にはa−1個の格子点がある.
O y
x C(0,1)
B(a, b+ 1)
A(a, b)
(2) OABCの内部の格子点をPi(pi, qi)とおく.
4OPiA= 1
2|aqi−bpi| である．Pi(pi, qi)は領域y > b
axにあるので, aqi−bpi>= 1 よって,
4OPiA >=1 2 である．ここで等号が成立するiが存在することを示す.
まず，Pi(pi, qi)に対し，aqi−bpi がすべて異なることを示す.
0< i, j < a に対してaqi−bpi=aqj−bpj ならば, a(qi−qj) =b(pi−pj)
となる．aと bが互いに素であるから，pi−pj はaの倍数である.
ところが，0< pi, pj< aより,
1−a < pi−pj < a−1 であるから，aの倍数はpi−pj= 0以外にないことがわかる.
よって，qi=qj も成り立ち，Pi = Pj がわかる.
したがって，集合{aqi−bpi}の要素の個数はa−1 である.
一方,
b
api< qi< b
api+ 1 ⇐⇒ 0< aqi−bpj < a
なので，集合{aqi−bpi}は集合{1, 2, · · ·, a−1}に含まれ，かつ要素の個数が一致する．
よって二つの集合は一致し，かならずaqi−bpi= 1となる番号iがある.
したがって，求める最小値は,
1 2
参考
・等号成立の別証
J={aq−bp|(p, q)はすべての格子点} とする． J の要素で正で最小のものをaq0−bp0とする.
任意のJ の要素aq−bpをaq0−bp0 で割る.
aq−bp= (aq0−bp0)Q+r, 0<=r < aq0−bp0
ここで,
r=a(q−q0Q)−b(p−p0Q)∈J であるから，aq0−bp0 の最小性によって,
r= 0 である．つまりaq−bpは，aq0−bp0の倍数である.
ところが
a=a·1 +b·0∈J 同じく bもJ の要素であるから,
aq0−bp0は aと bの約数 となり，aとb が互いに素であるから,
aq0−bp0= 1 この(p0, q0)に対して整数nを用いて,
p1=p0+an, q1=q0+bn
とおくと，aq1−bp1= 1であり，nを適当にとると0< p1< aにできる.
このとき q1= b ap1+1
a より,
b
ap1< q1< b ap1+ 1 となるので，(p1, q1)は, OABCの内部にある.
解答 5 (問題5)傾きが 2
5 である直線2x−5y−u= 0を lu と表すことにする.
このとき，lu と格子点(m, n)との距離は,次の式で与えられる．
|2m−5n−u|
√22+ 52 · · ·°1
m, nが変化するとき，2m−5nは任意の整数値をとりうる．実際，任意の整数k に対して 2·3k−5·k=k
が成り立つ． uを整数部分と小数部分に分けて
u=k+α (k は整数, 0<=α <1)
と書くことにする．したがって上に述べたことからm, nが変化するとき，
|2m−5n−u|>= min(α, 1−α) ゆえに°1 は
|2m−5n−u|
√22+ 52 >= min µ α
√29, 1−α
√29
¶
そしてこの等号が成立する m, nが必ず存在する．したがって r >= min
µ α
√29, 1−α
√29
¶
に円の半径をとれば，直線 lu は円のいずれかと共有点をもつ．
uの値に関わらず共有点をもつためにはuを動かしたときのmin µ α
√29, 1−α
√29
¶
の最大値以上 に rをとればよい．
明らかに 1
2 >= min µ α
√29, 1−α
√29
¶
で等号は α=1
2 のときである．
したがって
r >= 1 2
√29
であれば，uに関わらず直線lu は円のいずれかと共有点をもつ．求めるrの最小値は 1
2√ 29
［注意］論証の根幹に，m, nが変化するとき，2m−5nは任意の整数値をとりうる，事実がある．
解答 6 (問題6)
(1) (i) (x, y)を任意の整数解とする．
αx=βy
でα, β が互いに素な正の整数であるから，xはβ の倍数である．x=βtとおく．こ のときy=αtとなる．逆にこの形をしている(x, y)は方程式を満たす．
x=βt, y=αt (t は任意の整数) (ii) αを β で割り商がq余りがr1とすると
α
β =q+r1
β 0<=r1
β <1
一方 α
β =a1+ 1 a2+ 1
a3+ 1 a4
, quad0<= 1 a2+ 1
a3+ 1 a4
<1
正の有理数の整数部分と小数部分は一意だから q=a1, r1
β = 1
a2+ 1 a3+ 1
a4
次に β
r1 =a2+ 1 a3+ 1
a4
なので，同様にβ をr1で割った商が a2 で，余りをr2とすると r1
r2 =a3+ 1 a4
再び同様に考えるとr1 をr2 で割った商がa3 で，その余りをr3 とすると r2
r3 =a4
つまり
α = a1β+r1
β = a2r1+r2
r1 = a3r2+r3 r2 = a4r3
ゆえに
α = a1(a2r1+r2) +r1
= a1a2(a3r2+r3) +a1r2+ (a3r2+r3)
= a1a2a3a4r3+a1a2r3+a1a4r3+a3a4r3+r3
β = a2a3a4r3+a2r3+a4r3
αと β は互いに素なのでr3= 1
(［注］ユークリッドの互除法の原理からr3= 1 であるが，ここは直接確認した．)
したがって
α = a1β+r1
β = a2r1+r2
r1 = a3r2+ 1 という除法の系列ができる．
このとき
r1 = α−a1β
r2 = β−a2r1=β−a2(α−a1β)
= −a2α+ (1 +a1a2)β
∴ α−a1β = a3(−a2α+ (1 +a1a2)β) + 1
つまり
(1 +a2a3)α−(a1a2a3+a1+a3)β= 1
∴ αq−βp= 1 (2) 157と68は互いに素である．
157 = 2·68 + 21 68 = 3·21 + 5 21 = 4·5 + 1
つまり 157
68 = 2 + 1 3 + 1
4 +1 5 (1)よりp= 2·3·4 + 2 + 4 = 30，q= 3·4 + 1 = 13とおくと
157·13−68·30 = 1 したがって
157·39−68·90 = 3 (x, y)を157x−68y= 3の任意の整数解とする．
157(x−39)−68(y−90) = 0 ゆえに(1)より
x−39 = 68t, y−90 = 157t (tは任意の整数) と書ける．
∴ x= 39 + 68t, y= 90 + 157t (tは任意の整数) 解答 7 (問題7)
(1)
ax0+by0=c, al+bm=c の辺々を引くと
a(x0−l) +b(y0−m) = 0
ここでa, bは互いに素なので，x0−l がb の倍数．これをbu(uは整数)とおく．このと きy0−m=−auとなる．つまり，
l=x0+bu, m=y0−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=x0+bu, m=y0−au と書ける．
l >0, m >0となるためには
l=x0+bu >0, m=y0−au >0 となる整数uがとれねばならない．つまり
y0
a > u >−x0
b ところがc > abのとき
y0
a − µ
−x0
b
¶
= ax0+by0
ab = c
ab >1
従って題意を満たす整数uが必ずとれる．つまりc > ab のときax+by=c を満たす正の 整数の組(x, y)が存在する．
(4) 0< k < abに対し二組の正の整数(x0, y0)と(x1, y1)があるとする．これは図の斜線領域 内の格子点である．
O y
b x a
ax+by=ab
ax+by=k (1)から
x1=x0+bu, y1=y0−au となる整数uがある．ところがこのとき
x1−x0=bu, y0−y1=au
となり，明らかに2点がともに斜線領域に存在することはできない．
逆に言えば斜線領域の各格子点(x, y)に対するax+byの値はすべて異なる．
格子点は (a−1)(b−1) 2 個あるから，正の整数の組(x, y)が存在しないkは
ab−(a−1)(b−1)
2 =(a+ 1)(b+ 1)
2 −1（個）
ある．
解答 8 (問題8) (1)
a(−ak) + (a2+ 1)k=k · · ·°1 であるから，格子点(−ak, k)はL上にある．
(2) (m, n)をL上の任意の格子点とする．つまり
am+ (a2+ 1)n=k · · ·°2 である．° −2 °1 をとる．
a(m+ak) + (a2+ 1)(n−k) = 0 · · ·°3
aの約数はa2の約数であり，a2+ 1の約数ではありえないのでaとa2+ 1は互いに素である．
したがって°3 よりm+akはa2+ 1の倍数である．整数tを用いてm+ak= (a2+ 1)tと おける．このときn−k=−atとなる．
つまりL上の格子点は整数tによって，
( m=−ak+ (a2+ 1)t n=k−at
と表される．逆にこのように表されるものがL上にあることは明らかである．
題意をみたす格子点が存在するのは，
( m=−ak+ (a2+ 1)t >0 n=k−at >0
をみたすt が存在することと同値である．つまり k
a > t > ak
a2+ 1 · · ·°4 ここでk=a(a2+ 1)のとき°4 は
a2+ 1> t > a2
となる．よって条件をみたす整数t が存在せず，題意をみたすL上の格子点も存在しない．
(3) k > a(a2+ 1)のとき°4 の左辺から右辺を引くと，
k a− ak
a2+ 1 = k
a(a2+ 1) >1
したがって条件をみたすtがつねに存在し，題意をみたす L上の格子点も存在する．
解答 9 (問題9)xをひとつ固定する．m= 2x, n=−xはx= 3m+ 5nを満たす．
x= 3m+ 5nを満たす任意の解を(m, n)とする．
3m+ 5n = x 3(2x) + 5(−x) = x この辺々を引いて，
3(m−2x) + 5(n+x) = 0
3 と5 は互いに素なので，ある整数tによってつぎのようにおけなければならない．
m−2x = −5t n+x = 3t
つまり xを表す(m, n)は整数 tによって次のように表される．
(m, n) = (2x−5t, −x+ 3t) この(m, n)が xを表すことも明らかである．
m= 2x−5t >= 0, n=−x+ 3t >= 0 なので 1
3x <=t <=2 5x
したがってこの範囲に整数t が存在することと，xが非負整数m, nを用いて表わせることが同 値である．
2 5x−1
3x >= 1
つまり x >= 15なら必ず条件を満たす整数t がとれる．したがって 1<=x <= 14
について調べればよい．
x= 1 0< 1 3 < 2
5 <1 なし x= 8 2< 8
3 <3<16
5 あり
x= 2 0< 2 3 < 4
5 <1 なし x= 9 9
3 = 3 あり
x= 3 3
3 = 1 あり x= 10 20
5 = 4 あり
x= 4 1< 4 3 < 4
5 <2 なし x= 11 11
3 <4<22
5 あり
x= 5 10
5 = 2 あり x= 12 12
3 = 4 あり
x= 6 6
3 = 2 あり x= 13 13
3 <5<26
5 あり
x= 7 2< 7 3 < 14
5 <3 なし x= 14 14
3 <5<28
5 あり
したがって表せないものはつぎの四つである．
x= 1, 2, 4, 7 xを3で割った余りで分類して考える．
x= 3k x= 3·k+ 5·0より k >= 0のとき（m, n) = (k, 0)で表せる．
x= 3k+ 1 x= 3·(k−3) + 5·2より k >= 3のとき（m, n) = (k−3, 2)で表せる．
x= 3k+ 2 x= 3·(k−1) + 5·1より k >= 1のとき（m, n) = (k−1, 1)で表せる．
したがってのこるのは1，2，4，7 である．ところが 3mのとりうる値は0，3，6，9，…
5nのとりうる値は0，5，10，15，…
であるから，明らかに1，2，4，7は 3m+ 5nの形で表せない．
解答 10 (問題10)
(1) 4m+ 6n= 7においてどのような整数m, nに対しても左辺は2で割り切れる．一方右辺は つねに2で割ると1余る．ゆえにこの等式を満たす整数m, nは存在しない．
(2) 3m+ 5n= 2を満たすひと組の(m, n)として (−1, 1)がとれる．
任意の解(m, n)に対して
3m+ 5n= 2 3(−1) + 5(1) = 2 で辺々引くと，
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) (tは任意の整数) (3) 背理法で示す．
r(k) =r(l) ⇐⇒ ak−alがbの倍数 (aとbは互いに素なので) ⇐⇒ k−lがbの倍数
ところが1<=k, l <=b−1より −(b−2)<=k−l <=b−2
∴ k−l= 0 ゆえに対偶が示されたので，
k6=l ならば r(k)6=r(l) である．