『ｎ！の素因数分解』解答

◆兵庫県の中学校１年生 ドラメッド三世 さんからの解答。

まず，
n=a₀+a₁p+……+a_mp^m とし，

それぞれのaに対し，a＜p　が成り立つとする。

すると，B(n)=a₀+a₁+……+a_m　となる。

A(n)=[

n ― p

]+[

n ―― p2

]+……+[

n ―― pm

]

と置くことができ、また，任意のkに対し、

[

n ―― pk

]=ak+ak+1p+……+ampm-k

が成り立つ。

よって，

(p-1)A(n)
=(p-1){a₁+(1+p)a₂+……+(1+p+……+p^m)a_m}
=(p-1)a₁+(p²-1)a₂+……+(p^m-1)a_m

ここで，

1+p+…+pj=

pj-1 ――― p-1

を使った。

これらから，

(p-1)A(n)+B(n)
={(p-1)a₁+(p²-1)a₂+……+(p^m-1)a_m}+{a₀+a₁+……+a_m}
=a₀+a₁p+a₂p²+……+a_mp^m
=n

よって、成り立つ。

◆東京都 ジュン☆ さんからの解答。

まず、k,j,S,aを自然数または０,pを素数とすると、
題意より、Vとpとが互いに素の時
B(k)=k (k＜p)

B(p^a*j)=B(j) -------＜1＞

V=p*S+k (0＜k＜p)の時、j≦kとすると

B(p*S+k)
=B(p*S+k-j)+B(j)
=B(p*S+k-j)+j -------＜2＞

となる。

今、n=1の時
A(1)=0,B(1)=1より、任意の素数pに対し

(p-1)A(1)+B(1)=1

が成り立つ。 --------------＜3＞

n=kのとき、任意の素数pに対し

(p-1)A(k)+B(k)=k ----------＜4＞

が成り立つとしたとき

n=k+1のとき

(p-1)A(k+1)+B(k+1)=k+1 ----＜5＞

が成り立つことを証明する。

まず、題意より
k!=p^A(k)*Y　(pとYは互いに素)である。

同様に

(k+1)!
=p^A(k+1)*Z　(pとZは互いに素)
=k!*(k+1)
=p^A(k)*Y*(k+1)

整理すると

p^A(k+1)-A(k)=Y/Z*(k+1)

Yとpとは互いに素であるから

(k+1)=p^Q *R　(pとRは互いに素,R＞0)

と置くと

p^{A(k+1)-A(k)-Q}=Y/Z*R=p⁰

よって
A(k+1)=A(k)+Q　---------------＜6＞

B(k+1)
=B(p^Q*R)
=B(R) --------＜1＞より
=B(R-1)+1 ------R＞0よりR=p*T+U+1と置け、＜2＞より(T,U自然数または0)

B(k) =B(p^Q*R-1)=C(Q)　と置くと

C(Q)
=B(p(p^Q-1*R-1)+(p-1))
=B(p(p^Q-1*R-1)) +p-1 --------＜2＞より
=B(p^Q-1*R-1) +p-1 --------＜1＞より
=C(Q-1)+p-1
=C(1)+(p-1)(Q-1)
=B(p*R-1)+(p-1)(Q-1)
=B(p*(R-1)+p-1)+(p-1)*(Q-1)
=B(p*(R-1))+(p-1)*Q --------＜2＞より
=B(R-1)+(p-1)*Q --------＜1＞より
=B(k+1)-1+(p-1)*Q
=B(k) --------------＜8＞

＜6＞より

(p-1)A(k+1)+B(k+1)
=(p-1)*(A(k)+Q)+B(k+1) ----------＜7＞より
=(p-1)*(A(k)+Q)+B(k)+1-(p-1)*Q ----------＜8＞より
=(p-1)*A(k)+B(k)+1
=k+1 -----------＜4＞より

よってn=k+1の時も
＜5＞は成り立つ----------＜9＞

＜3＞＜9＞より、数学的帰納法により題意は証明された。

◆宮城県　アンパンマン さんからの解答。

Let n=d_r*p^r+d_r-1*p^r-1+...+d₁*p+d₀;
0＜d_i＜p-1 are integers.

A(n)＝[

n ― p

]+[

n ―― p2

]+…

＝	n-B(n) ――――― p-1

　where [x]=the largest integer less than or equal to x.

Therefore (p-1)A(n)+B(n)=n.

　『ｎ！の素因数分解』へ

　数学の部屋へもどる