解答 21 問題21
(1) 15と互いに素な15以下の数は
1, 2, 4, 7, 8, 11, 13, 14 である．よってf(15) = 8．
(2) 1<=m <=pqの範囲にあるpqと互いに素でない数はpの倍数とqの倍数でありそれぞれ，
{p, 2p, · · ·, pq}, {q, 2q, · · ·, pq} である．pqが共通なので，互いに素でない数が
q+p−1 よって
f(pq) =pq−(q+p−1) = (p−1)(q−1)
(3) 1からpe までの数のなかで pe と互いに素では ないものは，pで割り切れるものに他なら
ず，それは
1·p, 2·p, · · ·, pe−1·p のpe−1個だけある．よって
f(pe) =pe−pe−1=pe (
1−1 p
)
である．
解答 22 問題22
(1) (i) gcd(N, n)̸= 1となるものは，pまたはqの倍数である．したがってNより小さい自然 数nでは
p, 2p, 3p, · · ·, (q−1)p q, 2q, 3q, · · ·, (p−1)q である．
(ii) 1<=n < Nの範囲でgcd(N, n)̸= 1となるものが(i)より (q−1) + (p−1)個
ある．同じ範囲でgcd(N, n) = 1となるものはそれらを除いたものである．
∴ ϕ(N) =pq−1−(q−1)−(p−1) = (p−1)(q−1) (2) N =pqなので(ii)から
ϕ(N) =N−(p+q) + 1 つまり，
p+q=N+ 1−ϕ(N), pq=N
よって，pとqを解としてもつ二次方程式は未知数をxとすれば次のようになる．
x2− {N+ 1−ϕ(N)}x+N = 0
(3)
N+ 1−ϕ(N) = 18426 = 2·9213 である．よって
p, q= 9213±√
92132−84754668 = 9213±√
106276 = 9539, 8887 解答 23 問題23
(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で割った余りで分類し, n2, n3, · · ·, n7 を7で割った余りを順に求めていくと,下表のようになる.
n 0 1 2 3 4 5 6
n2 0 1 4 2 2 4 1 n3 0 1 1 6 1 6 6 n4 0 1 2 4 4 2 1 n5 0 1 4 5 2 3 6 n6 0 1 1 1 1 1 1 n7 0 1 2 3 4 5 6 よって,すべての自然数nに対して
f(n7) =f(n)
注意7 これは言うまでもなく「フェルマの小定理」そのものである．文系入試問題であ るので，実際に7で割った余りの表を作ることで論証した．
他の演習問題にあるように，n7−nが7の倍数になることをn に関する数学的帰納法で示 すことができる．
(2) (1)の結果より,すべての自然数kに対して,k7−kは7の倍数であるから
∑7
k=1
kn+6−
∑7
k=1
kn=
∑7
k=1
kn−1(k7−k) = 7l (l は自然数)
∴ g(n+ 6) =g(n)
よって, 1<=n <= 6の範囲で考えれば十分である. ここで, (1)の表を利用すると g(1) = 3f(1 + 2 + 3 + 4 + 5 + 6 + 0) = 3f(21) = 0 g(2) = 3f(1 + 4 + 2 + 2 + 4 + 1 + 0) = 3f(14) = 0 g(3) = 3f(1 + 1 + 6 + 1 + 6 + 6 + 0) = 3f(21) = 0 g(4) = 3f(1 + 2 + 4 + 4 + 2 + 1 + 0) = 3f(14) = 0 g(5) = 3f(1 + 4 + 5 + 2 + 3 + 6 + 0) = 3f(21) = 0 g(6) = 3f(1 + 1 + 1 + 1 + 1 + 1 + 0) = 3f(6) = 18
となるから,n= 6をとれば
g(6) = 18 解答 24 問題24
(1) 集合{rk |k∈A}をBとする．nとpが互いに素なので
rk= 0 ⇐⇒ nkがpの倍数 ⇐⇒ kがpの倍数
1<=k <=p−1よりこれはない．よって0̸∈Bである．従ってB ⊂A．次にi, j ∈Aに対 して
ri =rj ⇐⇒ n(i−j)がpの倍数 ⇐⇒ i−jがpの倍数
−p+ 2<=i−j <=p−2なのでi−j= 0．つまりi̸=jならri̸=rj．
よってBはp−1個の要素からなり，Aの要素の個数と一致する．よってB=Aである．
(2) k∈Aに対してある整数qkを用いてnk=pqk+rkとおける．
(ni)(nj) =p(pqiqj+qirj+qjri) +rirj であるから，
n·2n· · · · ·(p−1)n=pN+r1r2· · ·rp−1
とある整数Nを用いて表せる．B=Aより
r1r2· · ·rp−1= (p−1)!
なので
np−1(p−1)!−(p−1)! =pN (p−1)!とpは互いに素なのでnp−1−1はpの倍数である．
解答 25 問題25 (1)
rpCr= rp!
r!(p−r)!= p(p−1)!
(r−1)!{(p−1)−(r−1)}! =pp−1Cr−1
上の等式の右辺はpの倍数であるが,rと pは互いに素なのでpCr がpの倍数である.
(2)
2p= (1 + 1)p= 1 +
p−1
∑
r=1
pCr+ 1
(1)より2p−2はpの倍数である．よって余りは2 (p >2)，0(p= 2)である．
(3) np−nがpの倍数であると推測される. これを,数学的帰納法で示す. (i) n= 1は明らか.n= 2のときは(2)より成立
(ii) n=kのとき成立するとする. つまり
kp−k=pMと整数M を用いて表される.
このとき
(1 +k)p= 1 +
p−1
∑
r=1
pCrkr+kp= 1 +
p−1
∑
r=1
pCrkr+pM+k
ここで,
p−1
∑
r=1
pCrkrはpの倍数なのでこれを整数N を用いてpN とおく.
(1 +k)p= 1 +pN+k
∴ (k+ 1)p−(k+ 1) =pN よって,n=k+ 1 のときも成立した.
(iii) したがって,すべての自然数nに対して,np とnをpで割った余りは等しい. つまり,np をpで割った余りはnを pで割った余りである．
解答 26 問題26
(1) (x1+x2+· · ·+xr)pの展開式は，式(x1+x2+· · ·+xr)をp個並べ，それぞれからx1, x2, · · ·, xr
のいずれかを取り出してかけあわせ，加えたものである．そのうち単項式x1p1x2p2· · ·xrpr となるものは，x1, x2, · · ·, xrがそれぞれp1, p2, · · ·, pr個取り出される場合だけあり，そ れらを加えた係数N は，その取り出し方の場合の数である．
N はx1, x2, · · ·, xrをそれぞれp1, p2, · · ·, pr個ずつを並べる場合の数である．その一 つの並べ方に対して，p1, p2, · · ·, pr個ずつあるx1, x2, · · ·, xrの一つ一つを区別すると p1!p2!· · ·pr!個でき，それらの並べ方の総数がp!である．よって
p1!p2!· · ·pr!N =p! ． つまりx1p1x2p2· · ·xrpr の係数N は
p!
p1!p2!· · ·pr! · · ·⃝1
である．ここではpが素数であることは用いていないので，p1+p2+· · ·+pr=pであるよ うな非負整数p1, p2, · · ·, prに対して⃝1 は上記の場合の数として整数である．
(2) p1, p2, · · ·, prの中に0でないものがある．それをpjとする．
p!
p1!p2!· · ·pr! = p
pj · (p−1)!
p1!· · ·(pj−1)!· · ·pr! より
pj· p!
p1!p2!· · ·pr! =p· (p−1)!
p1!· · ·(pj−1)!· · ·pr!
(1)の注意より両辺整数で右辺はpの倍数である．ここでpが素数とする．pj< pであるな らpとpjは互いに素なのでこのとき p!
p1!p2!· · ·pr! はpの倍数である．
式
(x1+x2+· · ·+xr)p−(x1p+x2p+· · ·+xrp) · · ·⃝2
に現れる単項式x1p1x2p2· · ·xrprは，そのすべての指数pjがpj < pである．よってその係 数はpの倍数であり，x1, x2, · · ·, xrの正の整数を代入したならばその値はpの倍数になる．
(3) 式⃝2 のx1, x2, · · ·, xrにすべて1を代入する．(2)の結論からrp−r=r(rp−1−1)はp の倍数である．rがpと互いに素なのでrp−1−1はpで割り切れる．