1

(x+1)^n - x^n mod pが全射になるnの特定

307
0

与えられた奇素数pに対してf(x)=(x+1)nxnmodpが全射(従って全単射)になるような正整数nを特定せよ

これは 第17回近大数学コンテスト(2014)の最終問 であり、解けなかったので検索などすると Q&A に行き当たり、 そこで紹介されていた論文
のSection 4に証明があった。文脈としては射影平面に関する性質を示すための補題的な位置づけのようだった。(なるほどそういうところからコンテストの題材を見つけてくるのかなどと感心した。)

さて、n=2のときはf(x)は線形で明らかに全単射である。また、xnは周期p1を持つので、n2(modp1)のときも全単射であることはすぐにわかる。それ以外のときに決して全単射にならないことを示すのが難しかった。

xnは周期p1を持つため、n=13np1の場合を調べればよい。n=1の場合は恒等的にf(x)=1で全射でないため、残り3np1を考える。

以下の内容は上記の論文に書かれた証明を自分の言葉で整理したものになる。
k=p1n
とおく。つまり、
knp1,(k+1)n>p1
を満たす整数kを取る。

最近の別ノート でも登場した以下の性質を所々で利用する:

x=0p1xr
(A) r0(modp1) のときは非零modp
(B) それ以外のときは0modp

(A)rp1の倍数の場合は、x=0のときxr=0x0のときxr1(modp)であるため和は1modpである。
(B)そうでない場合はd=gcd(p1,r),e=(p1)/dとするとe個のd次剰余がd回ずつ現れるが、これらは多項式Xe10(modp)の解であるため、e2と解と係数の関係より和は0となる。

knp1の等号が成立するかどうかで証明の有効性が変わるので場合分けする。

場合1kn=p1の場合
この場合、n個のk次剰余が
zn1(modp)
を満たすことになる。特に3np1であるから、zn1を満たすzz1以外に少なくとも2個存在する。zn1を満たすz1に対して、z1の逆元をxとおくと、(x+1)nxn(modp),すなわちf(x)0が成り立つ。したがってそのようなzが2個以上存在することからfは全射でない。

場合2knp1、すなわちkn<p1
この場合、次の和を考える:
S=x=0p1f(x)2k.
3np1より0<2k<p1であるから、もしf(x)が全単射であれば、この和は命題1の(B)に該当し、0modpになるはずである。従ってS0(modp)を示せば良い。

二項展開して、
S=a=02kx=0p1(2ka)(1)a(x+1)(2ka)nxan
と表す。以下にa=kだけが寄与してそれが非零であることを示す。

パート1ak+1

(x+1)(2ka)nxanxの多項式として展開した結果を考える。kの定義より p1<an であるから、現れる最低次数は(p1)次より大きい。一方最高次数は2knで、これは場合分け条件より2(p1)より小さい。従って展開したすべての項は命題1の(B)に該当し、xに関する和modp0となる。

パート2ak1

y=x+1と変数変換すると、パート1と同様に和が0と分かる。

パート3a=k
(x+1)knxknの展開結果を考える。knp1なので二項係数にpの倍数が現れない。よって展開結果はxknからx2knまでの全ての次数でmod pで非零な項を持つ。kの定義によりこの次数範囲はxp1を含み、場合分け条件よりx2(p1)には至らない。よって命題1(A)よりxに関する和modpは非零である。

以上より、S0(modp)が示され、従ってf(x)は全単射でないことが示された。

投稿日:514
更新日:515
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

aerile_re
aerile_re
17
5070
https://twitter.com/icqk3

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中