『整数問題一発勝負！！ Part４』解答

◆滋賀県　一平　さんからの解答。

【問題２−１】

Ｂ=2･3･…(p-1)+3･4･…･(p-1)+…+2･3･…(p-2)
　≡-1･(p-2)＋(-2)･1　(mod p)
　≡-p
　≡0（mod p）

◆神奈川県　三島　久典　さんからのコメント。

2-2 は Wolstenholme の定理ですね。
１乗だけでなく、２、３、４乗でも同様のことが成り立ちます。

http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/ の８番目に、この数の素因数分解の結果を載せています。

この定理は、１にあるような変数の置き換えをやってから、二項係数がｎで割り切れることを利用して証明するもので、かなりテクニカルな証明なのですが、このように誘導があると、割と容易に証明できるのだということを知って驚きました。

◆埼玉県　\aleph_0　さんからの解答。

問題を少し一般化して, 次のことを示したいと思います.
以下ではpを奇素数とします.

定理1.

1≦r≦p-2である整数rに対して次が成り立つ:

(1)

p-1 Σ k=1

kr≡0 (mod p).

定理2.

1≦r≦p-2である整数rに対して次が成り立つ:

(2)

p-1 Σ k=1

k-r≡0 (mod p).

定理3.

3≦r≦p-1である奇数rに対して次が成り立つ:

(3)

p-1 Σ k=1

kr≡0 (mod p2).

定理4.

1≦r≦p-3である奇数rに対して次が成り立つ:

(4)

p-1 Σ k=1

k-r≡0 (mod p2).

定理1の証明.

rに関する帰納法により示す.

まずr=1ならば,

(3)

p-1 Σ k=1

k＝

1 ― 2

p(p-1)≡0 (mod p).

次に1＜r≦p-2とし, 1≦s＜rである整数sに対して

(3)

p-1 Σ k=1

ks≡0 (mod p).

と仮定する.

このとき整数kに対して二項展開により

(k+1)^r+1
=k^r+1+(r+1)k^r+_r+1Ｃ₂k^r-1+...+(r+1)k+1

であるから,
この式をk=0,1,...,p-1に対して加え合わせれば,

pr+1=(r+1)

p-1 Σ k=1

kr+r+1Ｃ2

p-1 Σ k=1

kr-1+...+(r+1)

p-1 Σ k=1

k+p.

したがって, 帰納法の仮定より,

(r+1)

p-1 Σ k=1

kr≡0 (mod p).

仮定より, r+1≡0 (mod p)ではないから,

(1)

p-1 Σ k=1

kr≡0 (mod p).

q.e.d.

定理2の証明.

写像σ: k mod p→k^-1 mod pは
(Z/pZ)^*上の置換を引き起こすから, 定理1より,

(1)

p-1 Σ k=1

k-r≡

p-1 Σ k=1

kr≡0 (mod p).

q.e.d.

定理3の証明.

次に示す定理4と同様に示されるので, 省略.

定理4の証明.

まず2≦r+1≦p-2であるから, 定理2より,

(2)

p-1 Σ k=1

k-(r+1)≡0 (mod p).

一方, 整数kに対して,

(p-k)(p+k)
＝p²-k²
≡-k² (mod p²),

すなわち,

(p-k)^-1≡-k^-2(p+k) (mod p²)

であるから,

(p-k)^-r
≡-k^-2r(p+k)^r
≡-k^-2r(rpk^r-1+k^r)
=-(rpk^-(r+1)+k^-r) (mod p²).

したがって,

(2)

p-1 Σ k=1

k-r

＝

1 ― 2

｛

p-1 Σ k=1

k-r+

p-1 Σ k=1

(p-k)-r｝

≡

1 ― 2

｛

p-1 Σ k=1

k-r-

p-1 Σ k=1

(rpk-(r+1)+k-r｝

＝-

1 ― 2

rp

p-1 Σ k=1

k-(r+1)≡0 (mod p2).

q.e.d.

この定理4でr=1とおけば, 問題2-2(Wolstenholmeの定理)が直ちに導かれます.
ちなみに, このWolstenholmeの定理から次の定理が従います.

定理5.

素数p≧5に対して次が成り立つ:

(5) _2p-1Ｃ_p-1≡1 (mod p³).

◆茨城県　小川　康幸　さんからの解答。

【問題１】

Ai*Bi≡

p-1 2

(mod p) となるように、Ai,Biを選ぶ。

A_i≡A_j (mod p) ⇔ B_i≡B_j (mod p) を示す。

A_i≡A_j (mod p) のとき、
A_i≡A_j≡a (mod p)とおく。

　a*B_i
≡A_i*B_i
≡A_j*B_j
≡a*B_j (mod p) である．

a*(B_i-B_j)≡0 (mod p)
aとpは互いに素だから、B_i≡B_j (mod p) が示せた。

逆に、B_i≡B_j (mod p) のとき、
A_i≡A_j (mod p) となることも、同様に示せる。

よって、A₁、A₂･･･、A_p-2はすべて異なる。
また、B₁、B₂、･･･B_p-2もすべて異なる。

よって、

p-2 Σ i=1

(Ai*Bi)≡

(p-1)(p-2) 2

≡

p(p+3) 2

+1≡1 (mod p)

となる。よって示せた。

【問題２−１】

p-1 Σ i=1

1 i

=

(p-1)/2 Σ i=1

(

1 i

+

1 p-i

)=p

(p-1)/2 Σ i=1

1 i(p-i)

=

pM N

∵

1 i

+

1 p-i

=

p i(p-i)

だから

また、分母は明らかにpと互いに素だから、よって問題１は正しい。
問題２−１終了

【問題２−２】

まず、zを整数としたとき、z²は、mod p で、
0²、1²、2²、･･･、{(p-1)/2}²のどれかと合同になる事を示す。

これを、命題１とする。

z=pq+r，0≦r＜p とかける。

0≦r≦

p-1 2

のとき z2≡r2 (mod p)

p+1 2

≦r≦p-1 のとき z2≡r2≡(p-r)2 (mod p)

1≦p-r≦

p-1 2

より、このときも正しい。

よって、命題１は示せた。

問題２−１より、

M N

=

(p-1)/2 Σ i=1

1 i(p-i)

の分子がpで割り切れる事を言えば良い。

(p-1)/2 Σ i=1

1 i(p-i)

=

(p-1)/2 Σ i=1

(p-1)! i

*

(p-1)! p-i

/(p-1)!2

xi=

(p-1)! i

、yi=

(p-1)! p-i

とおくと、

=

(p-1)/2 Σ i=1

xi*yi (p-1)!2

(分子)=

(p-1)/2 Σ i=1

xi*yi

(p-i)(y_i)=(p-1)!
-i*y_i≡(p-1)! (mod p) より、

yi≡-

p-1 i

=xi (mod p) だから、

(p-1)/2 Σ i=1

xi*yi≡-

(p-1)/2 Σ i=1

xi2

iとjが異なるとき、x_i²≡x_j² (mod p)となったと仮定すると、

i²*x_i²≡j²*x_j²≡(p−1)!² (mod p)

x_i²≡x_j²≡s (mod p) とおくと、
sとpは互いに素だから、i²≡j² (mod p)

(i+j)(i-j)≡0 (mod p) 　0＜i，j＜

p-1 2

より、

0＜i+j＜p-1だから、i≡j (mod p)

i=jとなって、仮定に反する。

命題１より

-

(p-1)/2 Σ i=1

xi2≡-

(p-1)/2 Σ i=1

i2

≡-

p-1 2

*

p+1 2

*p/6 (mod p)

pは5以上の素数より、pは6と互いに素ゆえ、

-

p-1 2

*

p+1 2

*p/6≡0 (mod p)

よって、分子がpで割り切れるのが言えた。
M=pKと書ける。

p-1 Σ i=1

1 i

=

p2*K N

明らかに、Nとpは互いに素なので、問題２−２は証明された。

問題２−２終了

pを5以上の素数とすると、
_2p-1C_p-1≡1 (mod p³)が成立すると言う定理を拡張した

【定理６】

kを2以上の整数、pを5以上の素数とする。
_kp-1C_p-1≡1 (mod p³)を示します。

証明

まず、(x-1)*(x-2)*(x-3)*･･･*{x-(p-1)}を展開した
x^p-1-･･･-Dx³+Bx²-Ax+(p-1)!を考える。

B≡0 (mod p)を示す。

B=

(p-1)! 1*2

*

(p-1)! 1*3

*

+･･･+

(p-1)! (p-2)*(p-1)

(p-1)!･B=

(p-1)! 1

*

(p-1)! 2

+

(p-1)! 1

*

(p-1)! 3

+･･･+

(p-1)! p-2

*

(p-1)! p-1

xi=

(p-1)! i

とおくと、

(p-1)!･B=x₁*x₂+x₁*x₃+･･･+x_p-2*x_p-1

よって、

2(p-1)!･B=

p-1 Σ i=1

xi*

p-1 Σ j=1

xj-

p-1 Σ i=1

xi2

ここで、x_i≡x_j (mod p) ならば、i=j となる事を示す。

i*x_i=j*x_j=(p-1)!である。

x_i≡x_j≡a (mod p)とおくと、
i*a≡j*a≡(p-1)! (mod p)

よって、(i-j)*a≡0 (mod p)

(p-1)!はpと互いに素だから、aもpと互いに素。
よって、i≡j (mod p)

よって、i=jとなる事が示せた。

よって、この対偶の、i≠j ならば x_iとx_jも mod p では異なる。

よって、

p-1 Σ i=1

xi*

p-1 Σ j=1

xj-

p-1 Σ i=1

xi2

≡

p-1 Σ i=1

i*

p-1 Σ j=1

j-

p-1 Σ i=1

i2

≡

1 2

*p*(p-1)*

1 2

*p*(p-1)-

1 6

*(p-1)*p*(2p-1)

pは5以上の素数だから、
≡0-0≡0 (mod p)

よって、2･(p-1)!･B≡0 (mod p)

2･(p-1)!は2と互いに素だから、B≡0 (mod p)

また、A=

p-1 Σ i=1

xiは問題２−２より、A≡0 (mod p2)

(p-1)!*_kp-1C_p-1
=(pk-1)*(pk-2)*･･･*{pk-(p-1)}
=(pk)^p-1+･･･-(pk)³*D+(pk)²*B-pk*A+(p-1)!(mod p³)

で考えると、p³で割り切れる項は無視できるから、

≡(pk)²*B-pk*A+(p-1)! (mod p³)

問題２−２より、A≡0 (mod p²)
よって、pk*A≡0 (mod p³)

また、B≡0 (mod p)が成立するので、
(pk)²*B≡0 (mod p³)

よって、(pk)²*B-pk*A+(p-1)!≡(p-1)! (mod p³)

これより、(p-1)!*_kp-1C_p-1≡(p-1)! (mod p³)

(p-1)!とp³は互いに素だから、
_kp-1C_p-1≡1 (mod p³) となる。

定理６は示された。

証明終

　『整数問題一発勝負！！ Part４』へ

　数学の部屋へもどる