シルヴァーマン 「はじめての数論」第3版 第12章練習問題3

12.5

(a)

n!を割る2の冪乗の最高次をf₂(n)として、

f₂(1)=0, f₂(2)=1,  f₂(3)=1, f₂(4)=3, f₂(5)=3, f₂(6)=4, f₂(7)=4,

f₂(8)=7, f₂(9)=7, f₂(10)=8

(b)

Eulerの記号[x]=(xを超えない最大の整数)を用いると、

m≤log₂n<m+1なるmを用いて、

f₂(n)= [n/2]+ [n/2²]+…+[n/2^m]

なおn≡[n]_m (mod m)とすれば、[n/2^r]=(n-[n]₂^r)/ 2^rであるから、

f₂(n)=n(1-2^-m)-{ [n]₂/2+[n]₂²/2²+ …+ [n]₂^m/2^m}。

(c)

nまでの全ての2の倍数[n/2]個からn!へ因子2が1つずつ入り、

全ての2²の倍数[n/2²]個からn!へもう一つずつ因子2が入り、

以下同様に2^mの倍数[n/2^m]個まで繰り返すので、(b)の式が成り立つ。

(d)

2の冪の場合と全く同様に、m≤log₃n<m+1なるmを用いて、

f₃(n)= [n/3]+ [n/3²]+…+[n/3^m]= n(1-3^-m)/2-{ [n]₃/3+[n]₃²/3²+ …+ [n]₃^m/3^m}。

(e)

上と全く同様にして、m≤log_pn<m+1なるmを用いて、

f_p(n)= [n/p]+ [n/p²]+…+[n/p^m]= n(1-p^-m)/(p-1)-{ [n]_p/p+[n]_p²/p²+ …+ [n]_p^m/p^m}。

例えばf₇(1000)=164, f₁₁(5000)=498。

(f)

[n/p^m]≥1より、f_p(n)= [n/p]+ [n/p²]+…+[n/p^m] ≥m。

また、f_p(n)=n(1-p^-m)/(p-1)-{ [n]_p/p+[n]_p²/p²+ …+ [n]_p^m/p^m}≤ n(1-p^-m)/(p-1)<n/(p-1)

したがってm<n/(p-1)。

12.6

(a)

1338=2·3·223, 1115=5·223なので、n∈ℕ として1338+1115n≡0 (mod 223)だから、

素数にならない。

(b)

gcd(1438, 1115)=1なので、Dirichletの定理により無数に存在する。

例えば4783。