自作問題　整数

問題

　$p$を$2p+1$が素数であるような素数とする．$2p$以下の正の整数の並べ替え$(a_1,a_2,\cdots,a_{2p})$であって，以下の条件を満たすような$2p$以下の相異なる正の整数$i,j$が存在するものの個数を求めよ．ただし，$a_{2p+1}=a_1$とする．

• 任意の$2p$以下の正の整数$n$について，$a_na_{n+1}$を$2p+1$で割った余りは$i$または$j$である

解説

整数$a,b$に対し，$a$と$b$を$2p+1$で割った余りが等しいことを単に$a\equiv b$で表し，$a_0=a_{2p}$とする．また，問題文の条件を満たす$2p$以下の正の整数の並べ替え$(a_1,a_2,\cdots,a_{2p})$のうち，$a_1=1$であるものを良い並べ替えと呼ぶ．このとき，求める値は良い並べ替えの個数を$2p$倍したものであり，良い並べ替えにおいて問題文の条件を満たす$i,j$は$i=a_0,j=a_2$と$i=a_2,j=a_0$である．
　$(a_1,a_2,\cdots,a_{2p})$が良い並べ替えであるとき，ある$2p$以下の正の整数$k$が存在して$a_{k-1}a_k\equiv a_ka_{k+1}$が成り立つと仮定すると，$2p+1$と$a_k$は互いに素なので$a_{k-1}=a_{k+1}$となり矛盾する．したがって，$k$が偶数のとき$a_ka_{k+1}\equiv a_0$，奇数のとき$a_ka_{k+1}\equiv a_2$である$(\because a_0a_1\equiv a_0,a_1a_2\equiv a_2)$．このときウィルソンの定理より$a_1a_2\cdots a_{2p}=2p!\equiv-1$であり，$a_1a_2\cdots a_{2p}=(a_1a_2)(a_3a_4)\cdots (a_{2p-1}a_{2p})\equiv a_2^{p}, a_1a_2\cdots a_{2p}=a_1(a_2a_3)(a_4a_5)\cdots (a_{2p-2}a_{2p-1})a_{2p}\equiv a_0^{p}$で$a_0^{p}\equiv a_2^{p}\equiv -1$なので，オイラーの規準より $a_0$と$a_2$はどちらも法$2p+1$で平方剰余でない．ここで，$2p$以下の正の整数からなる数列$b_0,b_1,\cdots$を以下のように定める．

• 任意の非負整数$n$について，$n$が偶数のとき$b_nb_{n+1}\equiv b_0$，$n$が奇数のとき$b_nb_{n+1}\equiv b_2$

このとき，$b_1=1$である．また，任意の$2p$以下の正の整数$a,b$について$ac\equiv b$を満たす$2p$以下の正の整数$c$はちょうど一つ存在するため，$b_1,b_2,\cdots$は$b_0,b_2$によって一意に定まる．良い並べ替えの定義から，$(b_1,b_2,\cdots,b_{2p})$が良い並べ替えであることと，以下の条件を満たすことは同値である．

• $b_{2p}= b_0$，すなわち$b_{2p+1}= 1$
• $b_1,b_2,\cdots,b_{2p}$はどの$2$つも異なる

$b_0,b_2$が相異なり，法$2p+1$で平方剰余でないとき，$b_1,b_2,\cdots$は上の条件を満たすことを示す．

　$x\gt y,b_x=b_y$を満たす正の整数$x,y$であって，$x-y$が最小になるものの$1$つを$X,Y$とする．$b_1,b_2,\cdots,b_{2p+1}$がどの$2$つも異なることはないので，$X-Y\lt 2p+1$である．$X$と$Y$の偶奇が異なるとすると，$b_{X-1}b_X\equiv b_Yb_{Y+1}$なので，$b_X=b_Y$，$b_X$と$2p+1$は互いに素だから$b_{X-1}=b_{Y+1}$で，帰納的に任意の$X$未満の正の整数$n$について$b_{X-n}=b_{Y+n}$が成り立つ．$X-Y$は奇数なので$\frac{X-Y+1}{2}$は正の整数であり，$n=\frac{X-Y+1}{2}$を代入すると$b_\frac{X+Y-1}{2}=b_\frac{X+Y+1}{2}$だが，$b_\frac{X+Y-1}{2}b_\frac{X+Y+1}{2}\equiv b_0$または$b_\frac{X+Y-1}{2}b_\frac{X+Y+1}{2}\equiv b_2$なので，$b_0,b_2$が法$2p+1$で平方剰余でないことに矛盾する．よって，$X$と$Y$の偶奇は等しい．すなわち$Y\gt 1$のとき $b_Xb_{X-1}\equiv b_Yb_{Y-1}$なので，帰納的に任意の$Y$未満の正の整数$m$について$b_{X-m}=b_{Y-m}$が成り立つ．$m=Y-1$を代入すると，$b_{X-Y+1}=b_1$が分かる．これは$Y=1$でも成り立つ．$X-Y$は$2$以上の偶数なので，$Z$を正の整数として$X-Y=2Z$とおくと，$b_{2Z+1}=1,b_{2Z}b_{2Z+1}\equiv b_0$より$b_{2Z}=b_0$である．また，$b_1b_2\cdots b_{2Z}=(b_1b_2)(b_3b_4)\cdots (b_{2Z-1}b_{2Z})\equiv b_2^Z, b_1b_2\cdots b_{2Z}=b_1(b_2b_3)(b_4b_5)\cdots (b_{2Z-2}b_{2Z-1})b_{2Z}\equiv b_0^Z$で$b_0^Z\equiv b_2^Z$なので，$b_0^p\equiv b_2^p$($\because b_0,b_2$は法$2p+1$で平方剰余でない)とあわせて考えると$b_0^{\gcd{(p,Z)}}\equiv b_2^{\gcd{(p,Z)}}$が分かる．よって，$Z$と$p$が互いに素であるとすると，$b_0=b_2$となり矛盾する．$p$は素数なので$Z$は$p$の倍数であり，$X-Y\lt 2p+1$より$Z\leq p$だから，$Z=p$である．よって$b_{2p+1}=1$であり，$X-Y=2p$なので，$b_1,b_2,\cdots,b_{2p}$のうちいずれか$2$つが等しいとすると$X-Y$の最小性に矛盾するため$b_1,b_2,\cdots,b_{2p}$はどの$2$つも異なるから，$b_1,b_2,\cdots$は提示された条件を満たす．(証明終わり)

　以上から，任意の法$2p+1$で平方剰余でない相異なる$2p$以下の正の整数の組$(b_0,b_2)$に対し$(b_1,b_2,\cdots,b_{2p})$が一意に定まり，それが良い並べ替えになる．ゆえに，$2p$以下の正の整数の並べ替え$(a_1,a_2,\cdots,a_{2p})$において，$a_2,a_{2p}$が法$2p+1$で平方剰余でないとき，それぞれの$(a_2,a_{2p})$に対し良い並べ替えがちょうど$1$つ存在する．これは，$b_2=a_2,b_0=a_{2p}$としたときの$(b_1,b_2,\cdots,b_{2p})$に対応する．$2p$以下の正の整数であって，法$2p+1$で平方剰余でないものは$p$個あり，$a_2$と$a_{2p}$は相異なるので良い並べ替えは$p(p-1)$個存在する．よって，求める値は$2p^2(p-1)$である．
　なお，$b_0^Z\equiv b_2^Z,b_0^p\equiv b_2^p$ならば$b_0^{\gcd{(p,Z)}}\equiv b_2^{\gcd{(p,Z)}}$は，以下のように導ける．
　$p$を$Z$で割った余りを$r$とすると，$Z\leq p$より正の整数$k$を用いて $p=kZ+r$と表せる．よって$b_0^{kZ+r}\equiv b_2^{kZ+r}$より$(b_0^Z)^k\cdot b_0^r\equiv (b_2^Z)^k\cdot b_2^r$で，$b_0^Z\equiv b_2^Z$から $b_0^r\equiv b_2^r$が分かる．これの$Z$または$p$を$r$に置き換えて同様に考えることを繰り返すと，ユークリッドの互除法と同じ要領で$b_0^{\gcd{(p,Z)}}\equiv b_2^{\gcd{(p,Z)}}$が分かる．