どの2つも相異なる剰余|思考力を鍛える数学

この問題はJMO2016年度本選第一問の類題です.

問題文の意味を補足しましょう.「任意の」というのは「どのような」という意味です.つまり,$1$ 以上 $p$ 未満のどのような整数$m$ をとってきても,$m$ が $kp+1$ の約数となるような $1$ 以上 $m$ 以下の整数 $k$ が存在するということです.ここで,$k$ は $m$ をひとつ決めるごとにひとつ定まると主張していることに注意してください.つまり,$k$ はとってきた $m$ ごとに決まる数です.

具体例で確認してみる

$p$, $m$, $k$ など,なにやら抽象的な文字が羅列されていてわかりにくいので,まずは具体例で問題の主張が本当に成り立つのか確認してみましょう.$kp+1$ を $m$ で割ったあまりを確かめるために,次のような表を考えます. \begin{array}{c|cccc} &p+1&2p+1&\cdots&(p-1)p+1 \\ \hline 1&&&& \\ 2&&&& \\ \vdots&&&& \\ p-1&&&& \end{array} ここで,表の一番左の列は$m$だと思ってください.$m$ は $1$ から $p-1$ の値をとります.表には,一番上に書かれた数を一番左の数 (つまり $m$) で割った剰余を書きます.ただし,$1 \le k \le m$ なので,$m$ 行目の $m$ 列目以降は考える必要が無いので空白にしておきます.以下で例を見てみましょう.

・$p=3$のとき \begin{array}{c|ccc} &4&7&10 \\ \hline 1&\color{red}{0} \\ 2&\color{red}{0}&1 \end{array} $4$ を $1$ で割ったあまりは $0$,$4$ を $2$ で割ったあまりは $0$, $7$ を $2$ で割ったあまりは $1$ なので,$p=3$ のときは上の表のようになります.

・$p=5$のとき \begin{array}{c|cccc} &6&11&16&21 \\ \hline 1&\color{red}{0} \\ 2&\color{red}{0}&1 \\ 3&\color{red}{0}&2&1 \\ 4&2&3&\color{red}{0}&1 \end{array}

・$p=7$のとき \begin{array}{c|cccccc} &8&15&22&29&36&43 \\ \hline 1&\color{red}{0} \\ 2&\color{red}{0}&1 \\ 3&2&\color{red}{0}&1 \\ 4&\color{red}{0}&3&2&1 \\ 5&3&\color{red}{0}&2&4&1 \\ 6&2&3&4&5&\color{red}{0}&1 \end{array}

さて,これらの表の赤字の $\color{red}{0}$ を見てください.表の各列ごとに,$\color{red}{0}$ がただひとつ存在することがわかります.これはつまり,$m$ をひとつとるごとに,$m$ が $kp+1$ の約数であるような$k$ $(1 \le k \le m)$ がただひとつ存在することを言っています.したがって,$p$ が $3,5,7$ のときは問題の主張が成り立つことが確認できました.さて,一般の場合にはどうすればよいでしょうか.上の各表を見て何か気づくことはないでしょうか.

ヒント

表の各行を見てください.$m$ 行目には $0$ から $m-1$ までの整数が $1$ つずつ表れていることがわかります.これはつまり,$p+1,2p+1,…,mp+1$ の $m$ 個の整数を $m$ で割ったあまりは全て異なるということです.これを示せば問題文の主張が正しいことがいえます.以下,そのことを証明しています.この証明方法は剰余に関する問題でよく見かける方法なので知っておくとよいと思います.つまり,$m$ 個の整数の剰余がすべて異なることを示すとき,相異なる$2$ つをとってきて,その $2$ つの剰余が異なることを示すという手法です.

補題

補題: $p$を奇素数とする.$m$ を $1$ 以上 $p$ 未満の整数とすると,$p+1,2p+1,…,mp+1$ の $m$ 個の整数を $m$ で割ったあまりは全て異なる.

証明: $p+1,2p+1,…,mp+1$ から相異なる $2$ つの整数 $ip+1,jp+1$ をとってくる (ただし,$1 \le i < j \le m$ とする) . $$(jp+1)-(ip+1)=(j-i)p$$ である.仮にこれが $m$ の倍数だとすると,整数 $n$ を用いて, $$(j-i)p=mn$$ とかける.ここで,$1 \le m < p$ なので,$p$ は $n$ を割り切る.したがって,整数 $n’$ を用いて, $$j-i=mn’$$ となるが,$j-i < m$ なのでこれは矛盾である.よって,$(j-i)p$ は $m$ の倍数でないから,$ip+1$ と $jp+1$ の $m$ での剰余は異なる.$i,j$ は任意にとってきていたので,結局,$p+1,2p+1,…,mp+1$ の $m$ 個の整数を $m$ で割ったあまりは全て異なる.

少し長くなりましたが結局,$p+1,2p+1,…,mp+1$ の $m$ 個の整数を $m$ で割ったあまりは全て異なるので,$m$ が $kp+1$ の約数であるような$k$ $(1 \le k \le m)$ がただひとつ存在することがいえました.

$p$が奇素数であることが効いています.

Copied title and URL