整数論の問題を紹介します。
二つの自然数を素数で割ったときの余りがどのようになっているのかを評価する問題になっています。
問題
\(a,b\)を正の整数とする。どんな素数\(p\)についても\(a\)を\(p\)で割った余りが\(b\)を\(p\)で割った余り以下であるとき、\(a=b\)を示せ
「この問題は1984年にハンガリーのとある数学コンテストで出題されたものです。これはもともとPálfyという数学者が予想し、ErdősがSylvester-Shurの定理から従うことを指摘したという経緯があります。しかしこれを数学コンテストに出題したところ、Szegedyという学生が簡潔でself-containdな解法を発見しました。その後、彼ら3人はその解法を共著論文にまとめています。」
https://kennji72019.blog.fc2.com/blog-entry-30788.html
論文にするということは、簡潔でありながら、簡単には思いつかない方法で解くことができるということの証ですね。
まあ、難しい問題ですが、こういった問題が整数問題では多くあります。もしかしたら、もっと簡単な解法があるのかもしれませんし、解法を研究しているとそこから新しい発見がでるかもしれません。
Sylvester-Shurの定理
この資料が参考になります。
http://puit578.web.fc2.com/sylvester.pdf
http://puit578.web.fc2.com/sylvester.pdf
問題の意味
整数の問題は、見た目が難しそうにみえる問題であっても、ある事に気が付くと、あっけなくというか、初等的に解けてしまう事があります。
この問題もその類といえるでしょう。
ただ、問題文を勘違いして、実際には解けていないのに解けたと思ってしまう場合もあります。
エレガントな解法も問題サイトに掲載されていますので、ここではこの問題がどういった問題なのかを説明します。
a=15,b=45を素数で割った時の余り
例として、１５と４５を素数で割ってみます。
15を2で割ると余り１で、45を2で割ると余り1です。
15を3で割ると余り0で、45を3で割ると余り0です。
同様にして、5で割ったあまり、7で割った余り、11で割ったあまりと順に余りを計算します。
その結果を表で表すと下記のようになります。
余りを比較し、大きいところに背景色をつけてあります。
| 割る 素数 | 15を 割った時の あまり | 45を 割った時の 余り |
|---|---|---|
| 2 | 1 | 1 |
| 3 | 0 | 0 |
| 5 | 0 | 0 |
| 7 | 1 | 3 |
| 11 | 4 | 1 |
| 13 | 2 | 6 |
| 17 | 15 | 11 |
| 19 | 15 | 7 |
| 23 | 15 | 22 |
| 29 | 15 | 16 |
| 31 | 15 | 14 |
| 37 | 15 | 8 |
| 41 | 15 | 4 |
| 43 | 15 | 2 |
| 47 | 15 | 45 |
このような結果になります。ここであまりの大小比較を行います。
素数11で割ったときの余りをみると、15の方が4、45の方は1になっています。
割る素数が47以上の場合は、余りが固定になりますが、それまでは、15を割った時の余りが大きい場合、45を割った時の余りが大きい場合とばらばらです。
つまり、背景色は15の列であったり、45の列であったりバラバラですね。
そこでこの問題が思いつきます。
aを割った時の余りより、bを割った時が常に等しいか大きい場合、つまり片方に偏っている場合があるだろうか？
結論をいうと、そういう場合は\(a=b\)を除いてありえないということなのですが、それを証明せよというのがここの問題です。
簡単そう(自明？)に見える問題ですが、数学コンテストに出題されたということは、そう簡単でもないという問題なんだとわかります。
すぐにわかること
下記の、(1)と(2)はすぐにわかります。
（１）\(a≦b\)
与えられた自然数\(a,b\)より大きい素数\(p\)で割った場合、余りはそれぞれ、\(a,b\)ですから、題意を満たす自然数があった場合、\(a≦b\)であることはすぐにわかります。
（２）\(a\)の素因数と\(b\)の素因数
\(b\)の素因数の一つを\(p\)とすると、\(b\)を\(p\)で割った時の余りは\(0\)です。\(a\)を\(p\)で割った時の余りが\(0\)でなければ、題意を満たさなくなるので、\(p\)は\(a\)の素因数でもなければなりません。
a=2,b=8を素数で割った時の余り
すぐにわかることから題意を満たす自然数\(a\)の素因数は、\(b\)の素因数であることがわかります。
指数部分を変えてみて反例がないかを探してみます（実際は反例はないのですが）。
すると、\(p=7\)の時だけ、\(a\)を\(p\)で割った時のあまりが\(b\)を\(p\)で割った時のあまりより大きくなってしまいます（実に惜しい）。
\(a=2,b=128\)の時は、\(p=127\)の時のみ\(a\)の余りが大きくなります(これまた惜しい)。
このあたりまで考察すると、この問題が意外に難しいんだなと実感してくるわけです。
解答
鮮やかな方法は下記のサイトで堪能してください。
