19727：2.5でない素数pの倍数が 1,11,111,...という数の中に必ず存在する。...定番 ^^

問題19727・・・http://hibiyastudy.hatenablog.com/entry/math/pigeonhole_principle より 引用 Orz〜

pを2,5でない素数とする。1,11,111,…という数の中に、必ずpで割り切れるものが存在することを示せ。

(数検1級2次)

1,11,111,...,111・・・111

1がp+1個並ぶ,p+1種類のものを考えると...

解答

・わたしの...

pで割った余りは(0〜p-1)のp個

so...いずれかの2個は同じ余りがあることになり、

それらを1(m個)<1(n個)のものとすると...

1(n個)-1(m個)=1(n-m個)*10^m

はpで割り切れることとなり、pは2,5出ないので、p(n-m個)がpで割り切れることを意味する ^^

or

10^(p-1)≡1 (mod p)・・・フェルマーの小定理

つまり...99...99(9がp-1個)並ぶものは、pで割り切れる...

pが3なら、111で明らかで,3以外の場合は11...11(1がp-1個)並ぶものはpの倍数

^^