与えられた奇素数に対してが全射(従って全単射)になるような正整数を特定せよ
これは
第17回近大数学コンテスト(2014)の最終問
であり、解けなかったので検索などすると
Q&A
に行き当たり、
そこで紹介されていた論文
のSection 4に証明があった。文脈としては射影平面に関する性質を示すための補題的な位置づけのようだった。(なるほどそういうところからコンテストの題材を見つけてくるのかなどと感心した。)
さて、のときはは線形で明らかに全単射である。また、は周期を持つので、のときも全単射であることはすぐにわかる。それ以外のときに決して全単射にならないことを示すのが難しかった。
は周期を持つため、との場合を調べればよい。の場合は恒等的にで全射でないため、残りを考える。
以下の内容は上記の論文に書かれた証明を自分の言葉で整理したものになる。
とおく。つまり、
を満たす整数を取る。
最近の別ノート
でも登場した以下の性質を所々で利用する:
(A)がの倍数の場合は、のとき、のときであるため和はである。
(B)そうでない場合はとすると個の次剰余が回ずつ現れるが、これらは多項式の解であるため、と解と係数の関係より和は0となる。
の等号が成立するかどうかで証明の有効性が変わるので場合分けする。
場合1:の場合
この場合、個の次剰余が
を満たすことになる。特にであるから、を満たすが以外に少なくとも2個存在する。を満たすに対して、の逆元をとおくと、,すなわちが成り立つ。したがってそのようなが2個以上存在することからは全射でない。
場合2:、すなわち
この場合、次の和を考える:
よりであるから、もしが全単射であれば、この和は命題1の(B)に該当し、になるはずである。従ってを示せば良い。
二項展開して、
と表す。以下にだけが寄与してそれが非零であることを示す。
パート1:
をの多項式として展開した結果を考える。の定義より であるから、現れる最低次数は次より大きい。一方最高次数はで、これは場合分け条件よりより小さい。従って展開したすべての項は命題1の(B)に該当し、に関する和はとなる。
パート2:
と変数変換すると、パート1と同様に和が0と分かる。
パート3:
の展開結果を考える。なので二項係数にの倍数が現れない。よって展開結果はからまでの全ての次数でmod で非零な項を持つ。の定義によりこの次数範囲はを含み、場合分け条件よりには至らない。よって命題1(A)よりに関する和は非零である。
以上より、が示され、従っては全単射でないことが示された。