2016年 日本数学オリンピック本選　第１問 解答例

$${p}$$を奇素数とする。
$${1}$$以上$${p-1}$$以下の整数$${k}$$に対し、$${kp+1}$$の約数のうち、$${k}$$以上$${p}$$未満となるものの個数を$${a_k}$$とおく。
このとき、$${a_1+a_2+\cdots+a_{p-1}}$$の値を求めよ。

公益財団法人　数学オリンピック財団HP第26回(2016年)JMO本選の問題 (imojp.org)

考え方：

条件が複雑なのでピンとこないうちはまず実験してみることになります。
$${p=3}$$のとき、
$${k=1}$$だと$${kp+1=4}$$の約数のうち条件を満たすのは$${1, 2}$$
$${k=2}$$だと$${kp+1=7}$$の約数のうち条件を満たすのはない。
よって求める値は$${2}$$

$${p=5}$$のとき、
$${k=1}$$だと$${kp+1=6}$$の約数のうち条件を満たすのは$${1, 2, 3}$$
$${k=2}$$だと$${kp+1=11}$$の約数のうち条件を満たすのはない。
$${k=3}$$だと$${kp+1=16}$$の約数のうち条件を満たすのは$${4}$$
$${k=4}$$だと$${kp+1=4}$$の約数のうち条件を満たすのはない。
よって求める値は$${4}$$

$${p=7}$$のとき、
$${k=1}$$だと$${kp+1=8}$$の約数のうち条件を満たすのは$${1, 2, 4}$$
$${k=2}$$だと$${kp+1=15}$$の約数のうち条件を満たすのは$${3, 5}$$。
$${k=3}$$だと$${kp+1=22}$$の約数のうち条件を満たすのはない。
$${k=4}$$だと$${kp+1=29}$$の約数のうち条件を満たすのはない。
$${k=5}$$だと$${kp+1=36}$$の約数のうち条件を満たすのは$${6}$$
$${k=6}$$だと$${kp+1=43}$$の約数のうち条件を満たすのはない。
よって求める値は$${6}$$

ここから、答えは$${p-1}$$であることが察せます。
また、$${kp+1}$$の約数として条件を満たす数値として
$${p-1}$$以下の正の整数が１回ずつ出てくることに気づきけば、
これを示せば完成です。

解答例：

$${k \leqq l \leqq p-1}$$であり$${l}$$が$${kp+1}$$の約数になるような
正の整数の組$${(k, l)}$$の個数が求める値である。
$${l \leqq p-1}$$なので、$${l}$$と$${p}$$は互いに素である。
よって、各$${l}$$に対して$${kp+1}$$が$${l}$$の倍数となる正の整数$${k}$$が
$${k\leqq l}$$の範囲にただ１つ存在する*。
よって求める答えは$${p-1}$$となる。

コメント：

*の部分は基本定理なので証明不要で使っていいと思いますが、
以下で紹介しておきます。

<定理>
$${a}$$と$${b}$$が互いに素であるとき、
$${a, 2a, \cdots, (b-1)a}$$を$${b}$$で割った余りは
$${1, 2, \cdots, b-1}$$を並べ替えたものになる。

<証明>
$${1\leqq m \leqq n \leqq b-1}$$で$${ma}$$と$${na}$$をそれぞれ$${b}$$で割った余りが等しいとすると
$${(n-m)a}$$は$${b}$$の倍数となる。
$${0 < n-m < b}$$かつ$${a}$$と$${b}$$は互いに素なのでこれはあり得ない。

元の問題では$${p}$$と$${l}$$が互いに素なので、
$${kp \equiv -1 (\text{mod  } l)}$$となる$${k}$$が$${0 \leqq k \leqq l-1}$$に１つだけあることが言えます。

お知らせ：

少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)