(3) a= 3e5fとおく．条件から1<=e, f <= 5である．
3a= 3e+15f =b3, 5a= 3e5f+1=c2
これからe+ 1, fは3の倍数，e, f+ 1は2の倍数である．1<=e, f <= 5の範囲でこれを満 たすのはe= 2, f = 3．したがってa= 32·53= 1125．
解答 10 問題10
(1) 5以上の素数pは奇数でありかつ3の倍数ではない．従って6で割った余りは1か5である．
pは5以上なので，ある自然数nを用いて6n+ 1または6n−1の形で表される．
(2) Nが自然数なので6N−1>= 5である．6N −1は3の倍数でないのでその因数分解に3は 表れない．従ってすべての素因数は6n+ 1または6n−1の形で表される．すべての素因数 が6n+ 1型のものばかりと仮定し，それらを6n1+ 1, · · ·, 6nl+ 1とする．
一般に6で割って1余る二数6u+ 1, 6v+ 1の積は
(6u+ 1)(6v+ 1) = 6(6uv+u+v) + 1
より再び6で割って1余る．これを繰りかえし用いることにより，6n1+ 1, · · ·, 6nl+ 1の べきの積
(6n1+ 1)e1· · ·(6nl+ 1)el · · ·⃝1 も6で割って1余る数であることが分かる．
これは6N−1が6で割って−1つまり5余る数であることと矛盾する．
よって6N−1は，6n−1 (nは自然数)の形で表される素数を約数にもつ．
(3) 6n−1 (nは自然数)の形で表される素数の個数が有限でk個であるとする．それらをp1, · · ·, pk
とする．
L= 6p1· · ·pk−1
とおく．Lはp1, · · ·, pkのいずれでも割っても−1余り，割り切れない．一方Lは6N−1 型なので(2)から6n−1型の素因数をもつ．その素数はp1, · · ·, pkのいずれとも異なる．
これは6n−1 (nは自然数)の形で表される素数の個数が有限でk個であるという仮定と矛 盾する．ゆえに有限個ではありえない．
(2) （イ）が成り立っているとする．Sの要素で正で最小のものをdとする．
Sのdと異なる正の任意の要素aをとる．
qd <=a <(q+ 1)d
となる自然数qをとる．r=a−qdとおく．r >0とする．a−d∈Sであり，自然数1<=j < q に対してa−jd∈Sならa−jd−d=a−(j+ 1)d∈Sなので，数学的帰納法でr=a−dq∈S である．dがSの要素で正で最小のものであるという仮定に反する．よってr= 0である．S のすべての要素はdの倍数である．
Sに属する最大の要素をmdとおく，1 < j <= mの整数に対してjd ∈ S ならjd−d = (j−1)d∈Sなので
md, (m−1)d, · · ·, d
はすべてSに属する．要素の個数は，0がSにあるかどうかを考えm=nかm=n−1で あり
S={nd, (n−1)d, · · ·, d}, {(n−1)d, (n−2)d, · · ·, d, 0}
のいずれかである．a1, a2, · · ·, an の順序を適当に変えれば初項がdまたは0，公差dの等 差数列になる．
（ロ）の場合，すべての要素の絶対値をとって考えれば同様である．
※ 大小の順で並べ替えて示してもよい．
解答 12 問題12
自然数jに対してjd∈Gならd+jd= (j+ 1)d∈Gなので，数学的帰納法によって {kd|kは自然数} ⊂G
Gの任意の要素aをとり，aをdで割り商がq，余りがrとする．
a=dq+r
dq ∈Gなのでr=a−dq∈Sである．ここでr >0とするとdがGに属する正で最小の整数とい う仮定に反する．よってr= 0である．Gのすべての要素はdの倍数である．
G⊂ {kd|kは自然数} が示され，題意が証明された．
解答 13 問題13
(1) x >=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),· · ·, C(999n)はすべて異なる．
つまり，集合{C(0), C(n), C(2n),· · ·, C(999n)}は1000個の要素からなる．この集合は，集 合{0,1,· · ·,999} に含まれ，ともに1000個の要素からなる．
∴ {C(0), C(n), C(2n),· · ·, C(999n)}={0,1,· · ·,999}
つまり，要素C(0), · · ·, C(999n)のどれかは1に一致する．すなわちC(nx) = 1となる0 以上の整数xが存在する．
(3) 379x= 1 + 1000yとなる整数解(x, y)を一組求める．
1 = 397x−1000y= 397x−(397·2 + 206)y
= 397(x−2y)−206y= (206 + 191)(x−2y)−206y
= 206(x−3y) + 191(x−2y) = (191 + 15)(x−3y) + 191(x−2y)
= 191(2x−5y) + 15(x−3y) = (15·12 + 11)(2x−5y) + 15(x−3y)
= 15(25x−63y) + 11(2x−5y) 15·3 + 11·(−4) = 1なので {
25x−63y= 3 2x−5y=−4 とおき，これを解く．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·397) =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)に対して
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 ゆえに対偶が示されたので，
k̸=l ならば r(k)̸=r(l) である．
(4) 二つの集合
A={1, 2, · · ·, b−1}
B ={r(k)|k= 1, 2, · · ·, b−1}
このkに対してr(k) = 0ならakがb の倍数．aとb は互いに素なのでkがbの倍数とな るが，k= 1, 2, · · ·, b−1 よりあり得ない．したがってr(k)はbで割った余りでしかも0 でないので
B⊂A 一方(3)より
k̸=l ならば r(k)̸=r(l)
なので，k= 1, 2, · · ·, b−1に対してr(k)はすべて異なる．つまり集合B の個数はb−1 で，集合Aの個数と等しい．
∴ A=B したがってB の元のなかに
r(k) = 1
となるものがある．このとき
ak−1がbの倍数 つまりak−1 =blとなる (k, l)が存在した．
(m, n) = (k, l)という解が存在した．
解答 15 問題15 (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上の格子点も存在する．
解答 16 問題16
(1) kを整数とし 3x+ 2y = kとおく．これを満たす 0 以上の整数解(x, y)の個数を k = 0, 1, · · ·, 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 >= 0, y >= 0という条件は
k 3 <=t <=
k 2
と同値である．よってkに対しこの範囲にある整数tの個数が，3x+ 2y=kとなる0以上 の整数の組(x, y)の個数である．負でない整数mを用いてkを場合に分け，個数を求める．
tの範囲 tの個数
k= 6mのとき 2m <=t <= 3m m+ 1個 k= 6m+ 1のとき 2m+13 <=t <= 3m+12 m個 k= 6m+ 2のとき 2m+23 <=t <= 3m+ 1 m+ 1個 k= 6m+ 3のとき 2m+ 1<=t <= 3m+32 m+ 1個 k= 6m+ 4のとき 2m+43 <=t <= 3m+ 2 m+ 1個 k= 6m+ 5のとき 2m+53 <=t <= 3m+52 m+ 1個
一つのmに対し個数は6m+ 5個ある．2008 = 6·334 + 4なのでm= 0, 1, · · ·, 334につ いて6m+ 5を加え，2009のときの個数335 個を除けばよい．
∴
∑334
m=0
(6m+ 5)−335 = 6·167·335 + 5·335−335
= (1002 + 4)·335 = 337010 (個)
(2) 不等式は3x+ 2y+z <= 60と同値である．3x+ 2y =kとなる一組の(x, y)に対し，zは 0<=z <= 60−kの範囲に60−k+ 1個とれる．組(x, y)の個数にzの個数を乗じたものが，
3x+ 2y=kかつ3x+ 2y+z <= 60となる整数の組(x, y, z)の個数である．
k= 6mのとき (m+ 1)(60−6m+ 1)個 k= 6m+ 1のとき m(60−6m)個
k= 6m+ 2のとき (m+ 1)(60−6m−1)個 k= 6m+ 3のとき (m+ 1)(60−6m−2)個 k= 6m+ 4のとき (m+ 1)(60−6m−3)個 k= 6m+ 5のとき (m+ 1)(60−6m−4)個
これを加える．
(m+ 1)(300−30m−9) +m(60−6m) =−36m2+ 321m+ 291
m= 0, · · ·, 9についてこれを加え，3x+ 2y= 60とき(このときzは0のみ)の11個を加 える．
∴
∑9
m=0
(−36m2+ 321m+ 291) + 11 = −6·9·10·19 + 321·45 + 2910 + 11
= −10260 + 14445 + 2921 = 7106 (個) 解答 17 問題17 (1) f(m, n) =k，つまり
m2−mn+n2−k= 0
はmの2次方程式である．mが実数となることが必要なので，mの2次式としての判別式をDと するとnは
D=n2−4(n2−k) =−3n2+ 4k >= 0 を満たさなければならない．これから0<=n2<=
4k
3 となり，nは有限個である．整数nに対して 整数mは多くても2個しかないのでX(k)は有限集合である．
k= 1のとき，0<=n2<= 4
3 よりn= 0, ±1．それぞれmを求めることにより次のようになる．
X(1) ={(1, 0), (−1, 0), (0, 1), (0, −1), (1, 1), (−1, −1)} (2)
f(m, n) =m2−mn+n2=k
においてkが偶数とする．mとnがともに奇数ならf(m, n)は奇数，mとnの一方が奇数，一方 が偶数ならf(m, n)は奇数となるので，整数解があればそれはともに偶数である．
k= 2のとき0<=n2<= 8
3．この範囲の偶数はn= 0のみで，このときm2= 2より解なし．X(2) の個数は0である．
k= 4のとき．mもnも偶数なのでm= 2p，n= 2qとおくと m2−mn+n2= 4p2−4pq+ 4q2= 4
つまりp2−pq+q2= 1．(1)からこれを満たす整数の組(p, q)は6組あり，それに対する(2p, 2q) のみがf(m, n) = 4の解なので，X(4)の個数は6である．
(3) (2)からf(m, n) = 2r (r自然数)の解はともに偶数である．m= 2p，n= 2qとおくと f(m, n) =m2−mn+n2= 2r
⇐⇒ f(2p, 2q) = 4p2−4pq+ 4q2= 2r
⇐⇒ f(p, q) =p2−pq+q2= 2r−2
である．これより，集合X(2r)の要素の個数と集合X(2r−2)の要素の個数は等しい，(2)から集合 X(2)の要素の個数は0，集合X(22)の要素の個数は6個なので，X(2r)の要素の個数はrが奇数
なら0，偶数なら6である．
注意1 rが奇数のときX(2r)の要素の個数が0であることは次のように直接示せる．
整数nに対してmが整数になるために，判別式Dが平方数であることが必要である．k= 2rの とき，
D=n2−4(n2−k) =−3n2+ 2r+2=N2 · · ·⃝1 とおく．⃝1 の両辺を3で割った余りを考える．
右辺N2を3で割ると，Nが3の倍数なら余りは0，N= 3s±1と表せるとき余りは1である．
一方，2のべきは，偶数べきなら22l= (3 + 1)lより二項定理から３で割った余りは1である．こ れから奇数べきなら余りは2である．よってrが奇数なら⃝1 となるn，Nは存在しない．
注意2 方程式x2−xy+y2= 22lで定まる曲線は図のような 楕円である．これは曲線を π 4 回転することによってわかる．
そしてそのうえにある格子 点は6個あり，それは図のよ う配置されている．
O y
x x2−xy+y2= 22l
2l 2l
−2l
−2l