続・鳩の巣原理

おはこんばんちは、ハトスです！

先週に引き続き、鳩の巣原理を続けていくよ！

‥え？早くもネタ切れだって？そ、そんなわけないだろっ！

今回はなかなかの難問にチャレンジしてみましょう。

（今週の１問）

（解説）

さて、鳩の巣原理を使うことは（タイトルからして）確定なのですが、何が鳩で何が鳩の巣なんでしょうか。「p+1」個の整数と「p」で割り切れるという1差の文字が怪しそうなので、p+1個の整数が鳩っぽいが、一体巣はどこに‥

世の中の整数、自然数は当然、無限に存在します。しかし、あるものに注目することで有限として扱うことができるのです。実は皆さんも何気な〜く日常で使っていたりするんですが、こういったとこに着目したことはおそらくないでしょう。

単純です。偶数、奇数。これで世の中の整数、自然数はたった二種類に分けることができているのです。偶数、奇数は言い換えると、2で割った余りが0か1である整数ということ。

つまり、剰余に注目するのです。自然数nで割った余りに注目すれば、余りは0,1,2,・・・,n-1のいずれかより、n種類に分けることができるのです。

（京都大学なんかはこれが大好きで、数年に一度、3で割った余りに注目させる整数問題を入試問題として出してきます。笑）

さらにもう１つ大事な考え方を。

なんてことない式に見えて整数問題においては超重要なカタチの式です。

3と5の最大公約数は1です。この関係性を互いに素と言います。

左辺の3xは3の倍数であるので、等号で結ばれている5yも3の倍数と言えます。しかし、3との公約数を1以外持たない5が3の倍数にはなり得ないので、yが3の倍数とならざるを得ません。

同様にxが5の倍数であるという結果を得ます。

準備が整いました。では行きます！

＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞

pで割った整数の余りはp種類存在するので、p+1個の整数の中には余りが等しい整数が少なくとも1組存在する。（鳩の巣原理）

すなわち、

と書ける整数が存在。ただし、rは0,1,2,・・・,p-1のいずれかであり、m>nとする。

ここで、両辺引けば、

すなわち、

とできる。

今、pは2,5でない素数、すなわちpと10は互いに素より、

となるので、題意は示せた。

＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞＜＞

んん！お疲れ様でした。

また来週！